The goal of this competition was to develop algorithms that leverage the knowledge of experienced drivers, who often modify automatically computed routes based on their tacit knowledge about traffic congestion, ongoing road constructions or customer availability.
The mathematical approach of the problem is a new variant of the well-known traveling salesperson problem (TSP). The TSP asks for a shortest tour through a given set of points. The question if efficient algorithms for the TSP exist or not boils down to the open millennium problem P vs. NP.
In the first part of the competition, the algorithms´ should learn the driver knowledge from around 6000 historical routes using machine learning techniques. Then, for a different set of approximately 3000 historical instances with undisclosed routes, new routes should be computed. These computed routes were scored based on their differences to the actually driven routes.
The team by Stephan Held from the Research Institute for Discrete Mathematics and Hausdorff Center for Mathematics, William Cook (University of Waterloo, Canada), and Keld Helsgaun (Roskilde University, Denmark) tackled the contest by rather advancing traditional local search algorithms for the TSP. Indeed, by inspecting the driven routes they detected a two-level hierarchical cluster structure in most of the underlying routes. Adding these structures as a side-constraint leads to a new variant of the TSP with hierarchical cluster constraints. In addition, precedence constraints between clusters were derived from one of the known driver routes with the most similar cluster structure, leading to a new type of disjunctive precedence constraints.
Large gap to second place
Advancing existing combinatorial local search algorithms to efficiently handle the new constraint types, the team finished with a 42 percent better score than the runners-up. From the twelve hour time limit that was granted to learn from the historic routes the winning approach used approximately five minutes to extract the precedence constraints. “To compute the 3000 new routes the strict time limit of four hours was almost consumed to improve the score as much as possible,” say Stephan Held. “In retrospect, a ten minute computation time would probably have been sufficient to maintain the lead.”
Only a 35 percent minority of the participants pursued a machine learning approach for this learning competition. One reason might be that machine learning techniques did not yet prove particularly useful for the traditional TSP and other combinatorial optimization problems, despite great research efforts in this direction. “Of course, in the future better combinatorial optimization algorithms, possibly in combination with machine learning techniques, will likely lead to even better results for this contest problem,” says Stephan held, who is also a member of the Transdiciplinary research area “Modelling” at the University of Bonn.
The source code of the winning team is published under the MIT open source license to spark future progress in the area: https://github.com/heldstephan/jpt-amz. A technical report with a detailed description will soon appear in the MIT technical report series.
Stephan Held is also involved in a joint research project on route planning between the University of Bonn and Greenplan, a subsidiary of Deutsche Post DHL. In this project traffic forecasts, delivery time windows, driver breaks, and many other things are considered by the newly developed algorithms. Recently, this cooperation contract has been extended for an unlimited period.
More about the "Amazon Last Mile Routing Research Challenge": https://routingchallenge.mit.edu/