Tepper Ph.D. Student Wins Best Student Paper Award from CPAIOR 2023 Conference

Anthony Karahalios(opens in new window), a doctoral student in operations research at Carnegie Mellon University’s Tepper School of Business(opens in new window), has won Best Student Paper at the 20th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2023)(opens in new window). The paper, which was co-authored by his adviser Willem-Jan van Hoeve(opens in new window), the Carnegie Bosch Professor of Operations Research at Tepper, is titled “Column Elimination for Capacitated Vehicle Routing Problems,” and will be published in the proceedings of the conference.

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.

The research outlined in the paper was supported, in part, by the Office of Naval Research and the National Science Foundation. 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.