Séminaire conjoint CIRRELT-Chaire HEC en logistique et en transport
TITRE : A branch-and-cut embedded matheuristic for the inventory routing problem
CONFÉRENCIER : Simen Tung Vadseth, Norwegian University of Science and Technology
DATE et ENDROIT : 1er décembre 2022, Université de Montréal, Pavillon André-Aisenstadt, salle 5441
RESPONSABLE : Jean-François Cordeau
RÉSUMÉ : This seminar will introduce a new matheuristic for the inventory routing problem (IRP). In the IRP, a supplier is in charge of replenishing goods to several customers and can decide when and in what order these customers should be visited over a finite and discrete time horizon. The goal is to minimize transportation costs and inventory holding costs for both the supplier and the customers. The IRP is a hard combinatorial optimization problem. Our solution method, a branch-and-cut embedded matheuristic, is based on a state-of-the-art branch-and-cut method, where a matheuristic is called every time a primal solution is found. 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. When tested on benchmark instances from the literature, the proposed method found the best-known solution for 740 out of 878 multi-vehicle instances. The method also won the IRP track of the recent DIMACS vehicle routing implementation challenge. In this talk, we will focus on the process of developing the algorithm and discuss whether what we have learned from solving the IRP can be used on other routing problems.