Bruno Castro, Pontifical Catholic University of Rio de Janeiro

Abstract

Inventory Routing Problems (IRP) are among the hardest extension of a VRP. One of its challenges is how to grasp the connection among the periods where the inventory and routing take place. We extend a two-stage matheuristic which iteratively solves the routing problem in the first stage using a metaheuristic and the inventory problem in the second stage using an exact algorithm. After defining the visits of each route for each period, the inventory problem can be modeled as a network flow problem. Our approach’s main contribution is how to efficiently hot start the resolution of each network flow. The resulting algorithm performs promisingly on the classical benchmark set compared to other literature approaches. The algorithm was able to find 302 new best-known solutions out of the 1038 instances. This success suggests the highly efficient inventory stage resolution allows current metaheuristics to solve IRPs similarly to how they do on single period VRPs, obtaining solutions comparable in quality.

[Challenge Paper]   [Video]