A Branch-and-Cut Embedded Matheuristic for the Inventory Routing Problem

This paper presents an improved version of the solution method that won the inventory routing problemtrack of the 12th DIMACS Implementation Challenge. The solution method is a branch-and-cut embeddedmatheuristic where a matheuristic is called every time new primal solution is found in a branch-and-cutmethod. The matheuristic consists of a construction heuristic and an improvement heuristic. The constructionheuristic uses a giant tour method and a shifting assignments method to generate a set of promising routeswhich, in turn, are combined into a feasible solution to the problem by solving a route-based mathematicalprogram. The improvement heuristic then solves a series of extended route-based mathematical programswhere clusters of customers may be inserted and/or removed from the routes of the initial feasible solution.We have, to the best of our knowledge, gathered all detailed results from previously published methods forthe inventory routing problem and made this overview available online. Compared with these results, theproposed 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 proveoptimality for 458 of these solutions. The proposed method is also able to find the best-known solutionfor 116 out of 226 benchmark instances for the split delivery vehicle routing problem, and improve threebest-known solutions from the CVRPlib for the capacitated vehicle routing problem