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

Abstract

The talk will present an improved version of the solution method that won the inventory routing problem track of the 12th DIMACS Implementation Challenge. The solution method is a branch-and-cut embedded matheuristic where a matheuristic is called every time a new primal solution is found in a branch-and-cut method. The matheuristic consists of a construction heuristic and an improvement heuristic. The construction heuristic uses a giant tour method and a shifting assignments method to generate a set of promising routes which, in turn, are combined into a feasible solution to the problem by solving a route-based mathematical program. The improvement heuristic then solves a series of extended route-based mathematical programs where clusters of customers may be inserted and/or removed from the routes of the initial feasible solution. Compared with published state-of-the-art methods, the proposed method found the best-known solution for 741 out of 878 multi-vehicle inventory routing instances, where 247 of them are strictly better than the previously best-known solutions. Furthermore, we prove optimality for 458 of these solutions. The proposed method is also able to find the best-known solution for 116 out of 226 benchmark instances for the split delivery vehicle routing problem.

[Video]