融合多源异质特征的最后一公里配送路线与时间并行预测

doi:10.3778/j.issn.1002-8331.2405-0309

摘要/Abstract

摘要： 最后一公里配送是指将包裹从仓库送至客户手中，是物流服务的关键一步。在最后一公里配送中进行路线和时间预测（route and time prediction，RTP），有利于提升物流系统效率并改善客户的体验。然而，实现准确的路线和时间预测面临巨大的挑战。快递员的配送路线和到达时间受到多源异质特征的影响，如快递员的个性化偏好、订单所在位置及下单时间、订单所在区域的类型及订单量等；当前很多研究先预测配送路线再预测配送时间，但不准确的路线预测结果往往会对时间预测造成误差累积。针对上述挑战，提出了一种基于多关系图神经网络的路线与时间并行预测方法（multi-relational graph model for route and time parallel prediction，MRG4RTPP）。构建包裹在位置和区域这两个层次上的时间、空间和转移模式多关系图，并设计双层次多关系图编码器提取多源异质特征，对包裹间的复杂时空关系进行建模。创新性地提出基于状态转移的路线与时间并行解码方式，用于缓解误差累计问题，在每步解码中，基于快递员当前状态并行预测下一配送包裹及其到达时间，并基于预测结果更新快递员状态。在三个城市的真实物流配送数据集上进行了实验，结果表明MRG4RTPP在路线预测和时间预测任务上均达到了当前最优效果。

关键词: 最后一公里配送, 路线预测, 时间预测, 图神经网络, 注意力机制

Abstract: Last-mile delivery refers to the process of transporting packages from the warehouse to the customer’s hands, which is a critical step in logistics services. Route and time prediction (RTP) in last-mile delivery can improve customer experience and reduce platform costs. However, achieving accurate route and time predictions presents significant challenges. Firstly, the delivery routes and arrival times of couriers are influenced by diverse and heterogeneous features such as the couriers’ personal preferences, the location and timing of the orders, the type of area where the orders are located, and the volume of orders. Secondly, in joint prediction methods, inaccurate route predictions can lead to the accumulation of errors in time prediction. To address these challenges, this paper proposes a multi-relational graph model for route and time parallel prediction (MRG4RTPP). Specifically, this paper constructs multi-relationship graphs of packages at two levels: location and area, incorporating time, space, and transfer patterns, and designs a dual level multi-relationship graph encoder to extract and model the complex relationships of multi-source heterogeneous features. In addition, a route-time parallel decoder is introduced for the joint parallel prediction of route and time. In each decoding step, the next delivery package and its arrival time are predicted in parallel based on the current status of the courier, and the courier’s status is updated based on the prediction results. This state-transition-based parallel decoding approach can effectively mitigate the error accumulation problem. Experiments conducted on real-world logistics delivery datasets in three cities demonstrate that MRG4RTPP achieves optimal results in both route and time prediction tasks.

Key words: last-mile delivery, route prediction, , time prediction, graph neural network, attention mechanism

侯云峰, 毛潇苇, 温浩珉, 郭晟楠, 林友芳, 万怀宇. 融合多源异质特征的最后一公里配送路线与时间并行预测[J]. 计算机工程与应用, 2025, 61(15): 310-317.

HOU Yunfeng, MAO Xiaowei, WEN Haomin, GUO Shengnan, LIN Youfang, WAN Huaiyu. Parallel Prediction of Last-Mile Delivery Routes and Times by Integrating Heterogeneous Multisource Features[J]. Computer Engineering and Applications, 2025, 61(15): 310-317.

参考文献

[1] DE ARAUJO A C, ETEMAD A. End-to-end prediction of parcel delivery time with deep learning for smart-city applications[J]. IEEE Internet of Things Journal, 2021, 8(23): 17043-17056.
[2] KANG P, SONG G, XU M, et al. Low-carbon pathways for the booming express delivery sector in China[J]. Nature Communications, 2021, 12(1): 450.
[3] VASWANI A, SHAZEER N, PARMAR N, et al. Attention is all you need[C]//Advances in Neural Information Processing Systems, 2017.
[4] KIPF T N, WELLING M. Semi-supervised classification with graph convolutional networks[J]. arXiv:1609.02907, 2016.
[5] ZHANG Y, LIU Y H, LI G J, et al. Route prediction for instant delivery[J]. Proceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies, 2019, 3(3): 1-25.
[6] CHEN T Q, GUESTRIN C. XGBoost: a scalable tree boosting system[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2016: 785-794.
[7] WEN H M, LIN Y F, WU F, et al. Package pick-up route prediction via modeling couriers’ spatial-temporal behaviors[C]//Proceedings of the 2021 IEEE 37th International Conference on Data Engineering. Piscataway: IEEE, 2021: 2141-2146.
[8] WEN H M, LIN Y F, MAO X W, et al. Graph2Route: a dyna-mic spatial-temporal graph neural network for pick-up and delivery route prediction[C]//Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM, 2022: 4143-4152.
[9] MAO X W, WEN H M, ZHANG H R, et al. DRL4Route: a deep reinforcement learning framework for pick-up and delivery route prediction[C]//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM, 2023: 4628-4637.
[10] WU F, WU L X. DeepETA: a spatial-temporal sequential neural network model for estimating time of arrival in package delivery system[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2019: 774-781.
[11] WANG Z, FU K, YE J P. Learning to estimate the travel time[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2018: 858-866.
[12] LI Y G, FU K, WANG Z, et al. Multi-task representation learning for travel time estimation[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2018: 1695-1704.
[13] HU J L, YANG B, GUO C J, et al. Stochastic origin-destination matrix forecasting using dual-stage graph convolutional, recurrent neural networks[C]//Proceedings of the 2020 IEEE 36th International Conference on Data Engineering. Piscataway: IEEE, 2020: 1417-1428.
[14] WANG D, ZHANG J B, CAO W, et al. When will you arrive? estimating travel time based on deep neural networks[C]// Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
[15] QIU J, DU L, ZHANG D W, et al. Nei-TTE: intelligent traffic time estimation based on fine-grained time derivation of road segments for smart city[J]. IEEE Transactions on Industrial Informatics, 2019, 16(4): 2659-2666.
[16] FU K, MENG F L, YE J P, et al. CompactETA: a fast inference system for travel time prediction[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York: ACM, 2020: 3337-3345.
[17] GAO C L, ZHANG F, WU G Q, et al. A deep learning method for route and time prediction in food delivery service[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. New York: ACM, 2021: 2879-2889.
[18] WEN H M, LIN Y F, WU F, et al. Enough waiting for the couriers: learning to estimate package pick-up arrival time from couriers’ spatial-temporal behaviors[J]. ACM Transactions on Intelligent Systems and Technology, 2023, 14(3): 1-22.
[19] CAI T Y, WAN H Y, WU F, et al. M2G4RTP: a multi-level and multi-task graph model for instant-logistics route and time joint prediction[C]//Proceedings of the 2023 IEEE 39th International Conference on Data Engineering. Piscataway: IEEE, 2023: 3296-3308.
[20] GRAVES A. Long short-term memory[M]//Supervised sequence labelling with recurrent neural networks. Berlin, Heidelberg: Springer, 2012: 37-45.
[21] POPESCU M C, BALAS V E, PERESCU-POPESCU L, et al. Multilayer perceptron and neural networks[J]. WSEAS Transactions on Circuits and Systems, 2009, 8(7): 579-588.
[22] CIPOLLA R, GAL Y, KENDALL A. Multi-task learning using uncertainty to weigh losses for scene geometry and semantics[C]//Proceedings of the 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE, 2018: 7482-7491.
[23] WU L, WEN H, HU H, et al. LaDe: the first comprehensive last-mile express dataset from industry[C]//Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2024: 5991-6002.
[24] KE G, MENG Q, FINLEY T, et al. LightGBM: a highly effi-cient gradient boosting decision tree[C]//Advances in Neural Information Processing Systems, 2017.