A Two-Stage Matheuristic Algorithm for Classical Inventory Routing Problem

A Two-Stage Matheuristic Algorithm for Classical Inventory Routing Problem

Zhouxing Su, Shihao Huang, Chungen Li, Zhipeng Lü

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 3430-3436. https://doi.org/10.24963/ijcai.2020/474

The inventory routing problem (IRP), which is NP-hard, tackles the combination of inventory management and transportation optimization in supply chains. It seeks a minimum-cost schedule which utilizes a single vehicle to perform deliveries in multiple periods, so that no customer runs out of stock. Specifically, the solution of IRP can be represented as how many products should be delivered to which customer during each period, as well as the route in each period. We propose a two-stage matheuristic (TSMH) algorithm to solve the IRP. The first stage optimizes the overall schedule and generates an initial solution by a relax-and-repair method. The second stage employs an iterated tabu search procedure to achieve a fine-grained optimization to the current solution. Tested on 220 most commonly used benchmark instances, TSMH obtains advantages comparing to the state-of-the-art algorithms. The experimental results show that the proposed algorithm can obtain not only the optimal solutions for most small instances, but also better upper bounds for 40 out of 60 large instances. These results demonstrate that the TSMH algorithm is effective and efficient in solving the IRP. In addition, the comparative experiments justify the importance of two optimization stages of TSMH.
Keywords:
Multidisciplinary Topics and Applications: Transportation
Heuristic Search and Game Playing: Combinatorial Search and Optimisation
Heuristic Search and Game Playing: Meta-Reasoning and Meta-heuristics
Heuristic Search and Game Playing: Heuristic Search