Amazon hosts Last Mile Routing Challenge
In early 2021, Amazon launched the Amazon Last Mile Routing Research Challenge in partnership with the Massachusetts Institute of Technology (MIT) Center for Transportation & Logistics. The competition aimed at optimized last-mile package delivery planning.
Despite enormous progress in tour optimization in recent years, there is still a noticeable gap between theoretical optimization and the actual implementation of tours. Particularly, in practice driver knowledge still primarily determines the course of a tour. The competition organized by Amazon, therefore, aimed to investigate how algorithms can learn the knowledge of experienced delivery and use these information for optimized last-mile delivery.
The mathematical approach to the problem is a new variant of the well-known Travelling Salesman Problem. This involves finding the shortest route through a large number of cities or parcel addresses. Whether efficient algorithms can be used for this problem or not directly relates to the “Millenium Problem P vs. NP”.
Stephan Held, a member of the Greenplan research team, and his team find the most efficient results
Professor Dr. Stephan Held of the Hausdorff Center for Mathematics and a member of the Greenplan development team at the University of Bonn participated in this year’s competition among 2,285 attendees. Together with his teammates Keld Helsgaun (Denmark) and William Cook (Canada), he tried to solve the problem by further developing known combinatorial local search algorithms – with success. Stephan Held’s team presented 42% better results than the runners-up from MIT. This exceptional achievement was rewarded with $100,000 in prize money.
The team recognized a two-level hierarchical cluster structure in the driven tours, which leads to a new variant of the Traveling Salesperson Problem. They also extracted so-called sequence constraints between clusters from a known tour with a similar cluster structure. Such sequence constraints define, for example, that cluster A should be approached before B and C. This resulted in new disjunctive sequence constraints stating that clusters must be visited either in the order A, B, C, or in the order B, C, A.
Machine learning is not the preferred solution
Interestingly, machine learning was not the preferred solution approach of the participants. Only 35% of all participating teams used machine learning techniques to solve the problem. According to Held, machine learning has not yet played a major role in combinatorial optimization problems such as the classical TSP, although much research on this topic is increasing.
Held comments on his own approach as follows: “The hype around machine learning means that nowadays one almost has to justify not using these methods in discrete optimization. For me, a key motivation was to demonstrate the strengths of optimization algorithms, especially in a machine learning competition, which is based on a combinatorial optimization problem.”
The mathematician suspects that combinatorial algorithms (like Greenplan) will continue to be the future for route planning and optimization – possibly in combination with machine learning algorithms.
A total of 220 teams from 22 countries participated in the competition. 45 teams made it to the final round.
Read the official press release from the Hausdorff Center for Mathematics here