Alexandre Florio, Amazon

Abstract

In the context of the Amazon Last-Mile Routing Research Challenge, in this talk we present a machine-learning framework for optimizing last-mile delivery routes. Contrary to most routing problems where an objective function is clearly defined, in the real-world setting considered in the challenge, an objective is not explicitly specified and must be inferred from data. Leveraging techniques from machine learning and classical traveling salesman problem heuristics, we propose a ``pool and select’’ algorithm to prescribe high-quality last-mile delivery sequences. In the pooling phase, we exploit structural knowledge acquired from data, such as common entry and exit regions observed in training routes. In the selection phase, we predict the scores of candidate sequences with a high-dimensional, pre-trained, and regularized regression model. The score prediction model, which includes a large number of predictor variables such as sequence duration, compliance with time windows, earliness, lateness, and structural similarity to training data, displays good prediction accuracy and guides the selection of efficient delivery sequences. Overall, the framework is able to prescribe competitive delivery routes, as measured on out-of-sample routes across several datasets. Given that desired characteristics of high-quality sequences are learned and not assumed, the proposed framework is expected to generalize well to last-mile applications beyond those immediately foreseen in the challenge.

[Video]