Xiaotong Guo, Massachusetts Institute of Technology

Qingyi Wang, Massachusetts Institute of Technology

Abstract

Experienced drivers in last-mile delivery may follow stop sequences that are more efficient than the theoretically shortest-distance routing under real-life operational conditions, due to their knowledge on factors unique to the service area. Thus, predicting the actual stop sequence that a human driver would take can enhance route planning in last-mile delivery.

In this presentation, we propose two methods for predicting drivers' route trajectories in last-mile delivery. The first approach is an optimization-based method using a hierarchical Traveling Salesman Problem (TSP) optimization with a customized cost matrix that accounts for routing patterns beyond the shortest travel time. This approach won second place in the 2021 Amazon Last-Mile Routing Challenge.

The second approach is a deep learning-based method that uses a pair-wise attention-based pointer neural network. In addition to the common encoder-decoder architecture for sequence-to-sequence prediction, we introduce a novel attention mechanism to capture the local pair-wise information for each pair of stops. To further improve the global efficiency of the route, we iterative over multiple possible sequences to select the one with the lowest operational cost. Our extensive case study on real operational data from Amazon's last-mile delivery operations in the US demonstrates that our proposed method outperforms traditional optimization-based approaches and other deep learning methods, such as the Long Short-Term Memory encoder-decoder and the pointer network, in finding stop sequences that closely resemble high-quality routes executed by experienced drivers in the field.

Based on our analysis, optimization-based techniques produce reliable and predictable sequences while reducing overall operational costs, without the need for training. Nevertheless, they have limited adaptability in incorporating soft constraints and heavily rely on pre-existing knowledge embedded in the cost matrix. Conversely, deep learning models can capture complex patterns with automatic feature learning. However, they demand a significant amount of training data, and the quality of their outputs is strongly impacted by the quality of input data.

[Video]