Local Search with Learned Constraints for Last Mile Routing

Keld Helsgaun, William Cook, Stephan Held

Publikation: Bidrag til bog/antologi/rapportBidrag til rapportForskning

Abstract

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.
OriginalsprogEngelsk
TitelTechnical Proceedings of the 2021 Amazon Last Mile Routing Research Challenge
RedaktørerMatthias Winkenbach, Steven Parks, Joseph Noszek
Antal sider12
ForlagMIT Libraries
Publikationsdatosep. 2021
SiderXXI.1–XXI.12
ArtikelnummerXXI
StatusUdgivet - sep. 2021
BegivenhedAmazon Last-Mile Routing Research Challenge -
Varighed: 22 feb. 202130 jul. 2021
https://routingchallenge.mit.edu

Andet

AndetAmazon Last-Mile Routing Research Challenge
Periode22/02/202130/07/2021
Internetadresse

Citer dette