An iterative matheuristic for the inventory routing problem

Abstract

The paper considers the inventory routing problem with the Maximum Level replenishment policy. Here, the supplier is in charge of replenishing goods to a number of customers and can decide when, and in what order, these customers should be visited over a defined time period. The goal is to minimize transportation costs and inventory holding costs at both the supplier and the customers. We present a matheuristic that uses a giant tour and simple operators to heuristically create routes that are used in a path-flow formulation. The proposed method iterates between solving a path-flow model with a small set of routes and updating the route set based on the optimal solution from the previous iteration. Computational results on known benchmark instances show that it outperforms state-of-the-art exact methods and heuristics on larger and more difficult instances. It finds the best-known solution on 179 out of 240 larger multi-vehicle benchmark instances, where 178 of them are strictly improving upon the previously best-known solution, and does so in considerably shorter time compared with other methods. In addition, when tested on another set of benchmark instances consisting of 798 smaller instances, the matheuristic finds the optimal solution in 44.7% of the 642 instances with known optima and has an average gap of 1.75% on the others. It also improves the best-known solution of 14 out of 156 open instances.