  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%.
