Shihao Huang, Huazhong University of Science and Technology

Abstract

The multi-vehicle inventory routing problem (MIRP) tackles the combination of inventory management and vehicle routing, which is a challenging NP-hard optimization problem. It seeks a minimum-cost solution which utilizes a fleet to perform deliveries in multiple periods, ensuring that no customer runs out of stock. We propose a three-stage matheuristic (TSMH) consists of three optimization stages to solve the MIRP. The first stage optimizes the global delivery schedule and generates a feasible initial solution by a relax-and-repair method. The second stage improves the initial solution by iteratively improving the local structure of the delivery schedule. The last stage adopts a solution-based tabu search for the MIRP to implement a detailed optimization. The experimental results on commonly-used instances show that the proposed algorithm can find new upper bounds on 100 out of the 640 small instances and 192 out of the 240 large ones. These results demonstrate that the TSMH is competitive in solving the large-scale MIRP.

[Challenge Paper]   [Video]