Routing is one of the most studied problems in computer science. The traveling-salesman problem, or determining the most efficient route for a salesman who has to visit several different destinations, is the most famous example of a problem that is NP-complete, meaning that in all but the simplest instances, it’s computationally intractable.
Nonetheless, the Amazon Last Mile team, which develops planning software for Amazon’s delivery fleet, finds approximate solutions to the traveling-salesman problem (optimizing for safety, experience, sustainability, and efficiency) on a regular basis. Given a delivery driver and a set of package destinations, the Last Mile team’s software tries to find the most efficient delivery route.
Drivers, however, frequently deviate from those computed routes. Drivers carry information about which roads are hard to navigate, when traffic is bad, when and where they can easily find parking, which stops can be conveniently served together, and many other factors that existing optimization models don’t capture.
Now, the Amazon Last Mile team is collaborating with MIT’s Center for Transportation & Logistics (MIT CTL) with the aim of incorporating driver know-how into route optimization models. The two groups are sponsoring a competition, called the Amazon Last Mile Routing Research Challenge, in which academic teams will train machine learning models to predict the delivery routes chosen by experienced drivers.
Amazon is providing the training data for the models and will be evaluating submissions, with technical support from MIT CTL scientists. MIT CTL will publish and promote technical papers about the top-performing models. The winners’ prizes are $100,000 for first place, $50,000 for second, and $25,000 for third. Top-performing teams may be interviewed by Amazon for research positions in the Last Mile organization and be invited to present their work at MIT CTL
The historical data provided by Amazon will include approximate delivery locations, package dimensions, and travel times and distances between locations — information used by existing route optimization algorithms.
But Amazon will also provide more than 4,000 traces of driver-determined routes, which encode the drivers’ know-how. Using both sources of information, contestants will be able to build models that identify and predict drivers’ deviations from routes computed in the traditional manner.
After the researchers have submitted their models, Amazon will release another 1,000 routes’ worth of historical data for evaluation purposes.
“We are encouraging participants to develop innovative approaches leveraging artificial intelligence, machine learning, deep learning, computer vision, and other non-conventional methods,” says Julian Pachon, director and chief scientist at Amazon Last Mile. “The contest is seeking to produce solutions to the route-sequencing problem that outperform traditional, optimization-driven operations research methods in terms of solution quality and computational cost.”
The contest is open for registration beginning on February 22, and the research period starts on March 15, 2021.
