  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.
