Constrained Local Search for Last-Mile Routing

William Cook, Stephan Held, Keld Helsgaun

Publikation: AndetUdgivelser på nettet - Net-publikationForskning

Abstract

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 straightfor- ward 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 devel- oped 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.
OriginalsprogEngelsk
Publikationsdato30 dec. 2021
UdgiverarXiv
Antal sider19
StatusUdgivet - 30 dec. 2021

Citer dette