Abstract
In last-mile delivery, drivers frequently deviate from planned delivery routes because of their tacit knowledge of the road and curbside infrastructure, customer availability, and other characteristics of the respective service areas. Hence, the actual stop sequences chosen by an experienced human driver may be potentially preferable to the theoretical shortest-distance routing under real-life operational conditions. Thus, being able to predict the actual stop sequence that a human driver would follow can help to improve route planning in last-mile delivery. This paper proposes a pair-wise attention-based pointer neural network for this prediction task using drivers' historical delivery trajectory data. In addition to the commonly used encoder-decoder architecture for sequence-to-sequence prediction, we propose a new attention mechanism based on an alternative specific neural network to capture the local pair-wise information for each pair of stops. To further capture the global efficiency of the route, we propose a new iterative sequence generation algorithm that is used after model training to identify the first stop of a route that yields the lowest operational cost. Results from an extensive case study on real operational data from Amazon's last-mile delivery operations in the US show that our proposed method can significantly outperform traditional optimization-based approaches and other machine learning methods (such as the Long Short-Term Memory encoder-decoder and the original pointer network) in finding stop sequences that are closer to high-quality routes executed by experienced drivers in the field. Compared to benchmark models, the proposed model can increase the average prediction accuracy of the first four stops from around 0.2 to 0.312, and reduce the disparity between the predicted route and the actual route by around 15%.
Introduction
In the world of logistics, the "Last-Mile" is the most expensive and complex leg of the journey. Traditionally, companies use Traveling Salesman Problem (TSP) or Vehicle Routing Problem (VRP) solvers to find the mathematically optimal route—usually the one with the shortest distance or time.
However, experienced drivers frequently ignore these "optimal" plans. Drivers possess "tacit knowledge"—they know which streets have difficult parking, which intersections are congested during school hours, and which customers are only home at specific times. Because standard optimization models cannot easily encode this human intuition, planned routes often fail in real-world application. This paper seeks to bridge that gap by learning to predict the actual trajectories drivers follow, leveraging historical data to capture that elusive human expertise.
Methodology
The authors propose a Pair-wise Attention-based Pointer Neural Network. The architecture builds on the standard encoder-decoder framework but introduces two major innovations:
- ASNN-based Pair-wise Attention: Standard Pointer Networks use content-based attention to pick the next stop in a sequence. This paper replaces that with an Alternative Specific Neural Network (ASNN). This mechanism specifically looks at the relationship between pairs of stops (e.g., travel time, geographical distance, and zone IDs) to capture local "stop-to-stop" logic more effectively than a general global embedding.
- Iterative Sequence Generation: Neural networks are often great at predicting the "next step" (local view) but can struggle to maintain a coherent "best route" (global view). To fix this, the authors developed an algorithm that, during the inference phase, tests every possible stop as a potential "first stop." It generates a full route for each starting point and then selects the one that results in the lowest overall operational cost. This hybrid approach combines the predictive power of deep learning with the efficiency constraints of classical optimization.
Datasets and Case Study
The study uses data from the Amazon Last-Mile Routing Research Challenge (2021), encompassing 6,112 real-world trajectories from five major US cities: Austin, Boston, Chicago, Los Angeles, and Seattle. The data includes stop locations (lat/long), package counts, service times, and "zones" (clusters of stops). For the case study, the authors focused on predicting the sequence of zones rather than individual stops, as drivers typically finish one zone before moving to the next.
Key Results and Insights
The proposed model was tested against several benchmarks, including standard TSP solvers, LSTMs, and the original Pointer Network:
- Accuracy Boost: The model increased the average prediction accuracy of the first four stops from 0.229 to 0.312 (a ~36% improvement over benchmarks).
- Disparity Reduction: It reduced the "disparity score" (a metric measuring how much the predicted route deviates from the actual route) by approximately 15% compared to the best-performing benchmark.
- The Critical First Stop: The researchers found that the quality of the entire predicted sequence is highly sensitive to the first stop. If the model identifies the start correctly, the rest of the route often falls into place.
- Constraints and Predictability: Through regression analysis, the authors found that routes with tighter time windows or larger vehicles are actually easier to predict. When drivers have less flexibility, they stick closer to the planned or logical path.
Conclusion
This research demonstrates that a pointer neural network with pair-wise attention can effectively learn the tacit knowledge of experienced drivers. While the model currently focuses on predicting what a driver will do, future work could focus on making these "tacit" reasons more transparent and using Reinforcement Learning to directly minimize route disparity during training.
Summary updated