Amazon, MIT Eye Delivery Routing Models
February 22, 2021
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
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
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
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.
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
The contest is open for registration beginning on February 22, and the research
period starts on March 15, 2021.