C&O professor Bill Cook, Stephan Held (University of Bonn) and Keld Helsgaun (Roskilde University, Denmark) have been announced as winners of the "Amazon Last Mile Routing Research Challenge". Their team, Just Passing Through, received a cash prize of $100,000.
The Last Mile Routing Research Challenge was organized by Amazon and MIT's Center for Transportation & Logistics. The challenge was to design algorithms for solving a variant of the Travelling Salesman Problem (TSP), namely optimizing routes for drivers delivering packages where experienced drivers might deviate from their routes by using their knowledge of factors that were not captured by the original optimization algorithms. These factors include local traffic congestion, road construction, and the availability of parking. The challenge organizers envisioned that the algorithms would first use machine learning techniques to learn driver knowledge from 6100 historical routes, and then design new routes for about 3000 routing instances. The routes computed by the algorithms would be compared to the routes actually taken by drivers for the 3000 instances.
The competition commenced on March 15, 2021, and the submission deadline was June 18, 2021. More than 220 teams participated, drawn from 71 universities in 20 countries. On July 30, 2021, Just Passing Through was announced as the winning team, with a score that was 42% higher than the second-place team.
Interestingly, the algorithm designed by the Just Passing Through team used traditional methods from combinatorial optimization instead of machine learning techniques. Cook, Held and Helsgaun inspected the 6,100 routes are devised a new formulation of TSP with "hierarchical cluster" and "precedence" constraints. A research report with a detailed account of the work is in preparation.