Amazon, MIT Eye Delivery Routing Models

February 22, 2021

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.

At left is a delivery route computed by the Last Mile teamís optimization software, at right the route that a delivery driver actually chose to drive. (Map details have been omitted.) Green symbols (A and B) indicate the driverís starting locations, purple symbols (also A and B) the ending locations.

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.

Terms of Use | Copyright © 2002 - 2021 CONSTITUENTWORKS SM  CORPORATION. All rights reserved. | Privacy Statement