Exact Algorithms for Vehicle Routing advances, challenges, and perspectives

The vehicle Routing Problem (VRP) is among the most widely studied problems in operations research and combinatorial optimization. The current state-of-the-art exact VRP algorithms employ a combination of column generation and cut separation, known as Branch-Cut-and-Price (BCP) algorithms. This presentation examines notable recent contributions made by various researchers in the field. Additionally, the talk showcases VRPSolver, a very flexible package that implements a BCP algorithm that achieves outstanding performance for many routing, packing, and scheduling problems. Furthermore, VRPSolverEasy, a recent Python application built on top of VRPSolver, is introduced. While heuristic algorithms are likely to remain the dominant approach for practical routing, the availability of exact solutions for reasonably sized instances opens up new possibilities.