Winning the 2021 Amazon Last Mile Routing Research Challenge
December 2021
How can parcel delivery be optimized when given traces of driver-determined routes? In other words, how can algorithms learn and use the knowledge of experienced drivers?
Direct optimization of routes is not the focus of the challenge. Competing teams are asked to match, as best they can, the sequences of stops in actual routes driven by drivers, who may have taken into consideration warehouse operations, current road conditions, types and sizes of packages to be delivered, and other factors. In machine-learning fashion, models and algorithms developed with the help of provided training data are evaluated by their performance on an additional large set of routes that are kept hidden from competing teams. See https://routingchallenge.mit.edu/.
A team comprising William Cook (University of Waterloo), Stephan Held (University of Bonn), and me won first prize, winning $100,000. See MIT News, August 24, 2021.
The method we employ utilizes a simple and efficient penalty-based local-search algorithm, first developed by me to extend the LKH traveling salesman problem code to general vehicle-routing models (LKH-3). We further develop my technique to handle combinations of routing constraints that are learned from an analysis of historical data. Our solution method is described in the report “Local Search with Learned Constraints for Last Mile Routing” and the preprint "Constraint Local Search for Last-Mile Routing".
Our source code is published under the MIT open-source license at https://github.com/heldstephan/jpt-amz.