2021/12/30 by William R. Cook, Cook, William, Stephan Held +3 · 1 citation
Engineering · #Advanced Manufacturing and Logistics Optimization #FOS: Mathematics #Optimization and Control (math.OC) #Urban and Freight Transport Logistics #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2112.15192
openalex publication_date 2021/12/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Last-mile routing refers to the final step in a supply chain, delivering packages from a depot station to the homes of customers. At the level of a single van driver, the task is a traveling salesman problem. But the choice of route may be constrained by warehouse sorting operations, van-loading processes, driver preferences, and other considerations, rather than a straightforward minimization of tour length. We propose a simple and efficient penalty-based local-search algorithm for route optimization in the presence of such constraints, adopting a technique developed by Helsgaun to extend the LKH traveling salesman problem code to general vehicle-routing models. We apply his technique to handle combinations of constraints obtained from an analysis of historical routing data, enforcing properties that are desired in high-quality solutions. Our code is available under the open-source MIT license. An earlier version of the code received the 100,000 top prize in the Amazon Last Mile Routing Research Challenge organized in 2021.