TY - JOUR
T1 - Constrained Local Search for Last-Mile Routing
AU - Cook, William
AU - Held, Stephan
AU - Helsgaun, Keld
PY - 2024
Y1 - 2024
N2 - 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 Lin–Kernighan–Helsgaun algorithm for the traveling salesman problem to general vehicle routing problems. 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 Massachusetts Institute of Technology license. An earlier version of the code received the $100,000 top prize in the Amazon Last Mile Routing Research Challenge organized in 2021.
AB - 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 Lin–Kernighan–Helsgaun algorithm for the traveling salesman problem to general vehicle routing problems. 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 Massachusetts Institute of Technology license. An earlier version of the code received the $100,000 top prize in the Amazon Last Mile Routing Research Challenge organized in 2021.
KW - Last Mile
KW - Local Search
KW - Vehicle routing
U2 - 10.1287/trsc.2022.1185
DO - 10.1287/trsc.2022.1185
M3 - Journal article
SN - 0041-1655
VL - 58
SP - 12
EP - 26
JO - Transportation Science
JF - Transportation Science
IS - 1
ER -