Local Search with Learned Constraints for Last Mile Routing

William Cook, Stephan Held, Keld Helsgaun

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearch


We describe our submission to the Amazon Last Mile Routing Research Challenge. The optimization method we employ utilizes a simple and ecient penalty-based local-search algorithm, frst developed by Helsgaun to extend the LKH traveling salesman problem code to general vehicle-routing models. We further develop his technique to handle combinations of routing constraints that are learned from an analysis of historical data. On a target set of 1,107 training instances, our submitted code achieves a mean score of 0.01989 and a median score of 0.00752. The simplicity of the method may make it suitable for applications where machine learning can discover rules that are expected (or desired) in high-quality solutions.
Original languageEnglish
Title of host publicationTechnical Proceedings of the Amazon Last Mile Routing Research Challenge
EditorsMatthias Winkenbach, Steven Park, Joseph Noszak
PublisherMassachusetts Institute of Technology
Publication dateSep 2021
Article numberXXI.12
Publication statusPublished - Sep 2021
EventAmazon Last-Mile Routing Research Challenge -
Duration: 22 Feb 202130 Jul 2021


OtherAmazon Last-Mile Routing Research Challenge
Internet address

Cite this