# Constrained Local Search for Last-Mile Routing

arXiv: https://arxiv.org/abs/2112.15192 · HTML: https://mlsanity.com/paper/2112.15192/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Dec 2021.

## Built on by (most cited first, 7 of 7)

- [Inverse Optimization for Routing Problems](https://mlsanity.com/paper/2307.07357/) (2023)
- [Learning from Drivers to Tackle the Amazon Last Mile Routing Research Challenge](https://mlsanity.com/paper/2205.04001/) (2022)
- [Predicting Drivers' Route Trajectories in Last-Mile Delivery Using A Pair-wise Attention-based Pointer Neural Network](https://mlsanity.com/paper/2301.03802/) (2023)
- [Probability estimation and structured output prediction for learning preferences in last mile delivery](https://mlsanity.com/paper/2201.10269/) (2022)
- [A Bi-Objective Approach to Last-Mile Delivery Routing Considering Driver Preferences](https://mlsanity.com/paper/2405.16051/) (2024)
- [A zone-based training approach for last-mile routing using Graph Neural Networks and Pointer Networks](https://mlsanity.com/paper/2601.04705/) (2026)
- [Just Initialize: A Training-Free Initialization Component for Large-Scale Routing Optimization](https://mlsanity.com/paper/2609.35443/) (2026)

## Abstract (arXiv)

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.