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

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, 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
Pages252-253
Article numberXXI.12
ChapterXII
Publication statusPublished - Sep 2021
EventAmazon Last-Mile Routing Research Challenge -
Duration: 22 Feb 202130 Jul 2021
https://routingchallenge.mit.edu

Other

OtherAmazon Last-Mile Routing Research Challenge
Period22/02/202130/07/2021
Internet address

Cite this