Local Search with Learned Constraints for Last Mile Routing

Keld Helsgaun, William Cook, Stephan Held

Publikation: Bidrag til bog/antologi/rapportBidrag til rapportForskning


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, rst 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.
TitelTechnical Proceedings of the 2021 Amazon Last Mile Routing Research Challenge
RedaktørerMatthias Winkenbach, Steven Parks, Joseph Noszek
Antal sider12
ForlagMIT Libraries
Publikationsdatosep. 2021
StatusUdgivet - sep. 2021
BegivenhedAmazon Last-Mile Routing Research Challenge -
Varighed: 22 feb. 202130 jul. 2021


AndetAmazon Last-Mile Routing Research Challenge

Citer dette