Jørgen Skålnes, Norwegian University of Science and Technology

Abstract

In this paper, we propose a branch-and-cut (B&C) method for the inventory routing problem using an efficient matheuristic to warm-start it. The B&C part of the algorithm is based on the known customer schedule formulation, but where we propose a modification that drastically reduces the number of customer schedules. The matheuristic has already proved effective on the inventory routing problem, but we propose several extensions that further improve the solution quality. In the construction phase of the matheuristic, we propose a second method to generate more diverse routes used to create an initial feasible solution. In addition, we expand the solution space of the improvement phase of the matheuristic, leading to a better starting point for the B&C method. We have tested the proposed solution method on the 1038 DIMACS instances, proving optimality and finding new best-known solutions on 278 and 254 instances, respectively.

[Challenge Paper]   [Video]