In the paper, Karahalios and van Hoeve introduce a column elimination procedure for the capacitated vehicle routing problem (CVRP). This problem has become increasingly important in the last decade due to the increase in last mile delivery applications: the often most expensive, inefficient and time-consuming part of the delivery process.
Given a set of locations, each with a specified weight and a fleet of trucks with a specified capacity, the problem requires designing a route for each truck. Along such a route, each location would be visited by a truck, the total weight of each truck’s visited locations would not exceed the capacity, and the sum of the truck route lengths would be minimized.
The approach outlined in this paper works with a relaxed set of routes that are compactly represented in a decision diagram from which infeasible routes are removed. Experimental results show that column elimination is a viable alternative to column generation for the CVRP. As existing methods can only reliably prove optimal solutions for instances with up to 250 instances, column elimination is a new method that may give hope for solving even larger instances.
It is also based on work supported by the National Science Foundation (Graduate Research Fellowship).
The CPAIOR conference brings together interested researchers from constraint programming, artificial intelligence, and operations research to present new techniques or applications, and to provide an opportunity for researchers in one area to learn about techniques in the others. A main objective of the 2023 conference series is to give researchers the opportunity to show how integrating techniques from different fields can lead to interesting results on large and complex problems.
The award was presented to Karahalios at the conference, which took place from May 29 through June 1, 2023, in Nice, France.
