动态订单下无人机辅助骑手外卖配送路径优化研究

doi:10.16381/j.cnki.issn1003-207x.2024.0074

Abstract

Abstract:

Due to the time-sensitive nature of distribution orders， each order is required to be completed within the shortest possible time， and considering the characteristics of large number of distribution orders during peak periods， geographically dispersed， and dynamic and random distribution of riders， it is extremely challenging to seek an order allocation and route optimization scheme with low delivery cost and high customer satisfaction. In order to solve the problems of dynamic generation of takeout orders and the continuous change of riders， a drone assisted riders delivery mode is proposed. The bimodal Gaussian function is used to simulate the generation of new orders in the distribution process， and a two-stage optimization model is constructed with the minimum distribution cost and the overall maximum customer satisfaction as the objective functions. In the first stage， an initial optimization model for rider delivery is established for static customers， and in the second stage， a dynamic adjustment model for drone assisted rider delivery is established for dynamically generated new orders. A two-stage heuristic algorithm is designed for this model to solve the problem， the first stage uses an AP （Affinity propagation） clustering algorithm improved based on K-means and KNN （K-Nearest Neighbor） classification algorithms for dynamic order allocation， and the second stage utilizes a taboo search algorithm improved by combining the insertion algorithm for route optimization. The effectiveness and feasibility of the model and algorithm are verified through case simulation. The results show that：（1） Compared with the traditional rider delivery mode， the drone assisted riders delivery mode can effectively reduce the number of riders and reduce the delivery cost. And with the larger scale of new orders， the advantages of the drone assisted rider delivery mode become more obvious. （2） Through real-time adjustment of delivery routes and optimization of order allocation， the empty load rate and transportation costs can be reduced， and operational efficiency can be improved. （3） The addition of drones can effectively optimize the distribution path and schedule of orders， avoiding delays caused by traffic congestion or unreasonable routes. It helps to reduce operating costs and further improve the overall efficiency and service quality of the logistics industry.

Key words: drone assisted riders, takeout delivery, dynamic route optimization, taboo search algorithm, AP clustering algorithm

CLC Number:

TP18

Fuqiang Lu,Runxue Jiang,Hualing Bi, et al. Routing Optimization of Drone Assisted Riders Takeout Delivery under Dynamic Orders[J]. Chinese Journal of Management Science, 2026, 34(2): 79-88.

Figures/Tables 12

实验参数	符号	取值	实验参数	符号	取值	实验参数	符号	取值
骑手平均车速	v_p	25千米/时	无人机自身加电池重	m_t+m_b	10.1千克	惩罚成本1	ω1	0.5
骑手的固定成本	c_p1	50元	无人机最大容量	W^u_max	5千克	惩罚成本2	ω2	1
骑手单位配送成本	c_p2	0.2元/千米	上升和阻力之比	$ϑ v$	3.5	幅值1	A₁	1149
骑手车辆最大容量	W^k_max	12千克	电池安全系数	μ	1.25	幅值2	A₂	-770
无人机平均速度	v_u	57.6千米/时	重力加速度	g	9.8千克/牛顿	中心点坐标1	μ₁	138
无人机固定成本	c_u1	10元	间隔时间	T	5分	中心点坐标2	μ₂	210
无人机单位配送成本	c_u2	0.3元/千米	顾客的平均服务时间	t_s	3分	标准方差1	$σ 1$	15.29
无人机充电的费用	c	0.66元/千瓦	能量转换效率	η	0.66	标准方差2	$σ 2$	-21.94

References 22

[1]	Li W， Li K， Ram Kumar P N， et al. Simultaneous product and service delivery vehicle routing problem with time windows and order release dates［J］. Applied Mathematical Modelling， 2021， 89： 669-687.
[2]	Ren T， Xu H B， Jin K N， et al. Optimisation of takeaway delivery routes considering the mutual satisfactions of merchants and customers［J］. Computers & Industrial Engineering， 2021， 162： 107728.
[3]	杨浩雄，高晶，邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题［J］. 计算机科学， 2022， 49（S1）： 191-198.
	Yang H X， Gao J， Shao E L. Vehicle routing problem with time window of takeaway food considering one-order-multi-product order delivery［J］. Computer Science， 2022， 49（S1）： 191-198.
[4]	Tang C， Liu C， Li C. Research on delivery problem based on two-stage multi-objective optimization for takeout riders［J］. Journal of Industrial and Management Optimization， 2023， 19（11）： 7881-7919.
[5]	李桃迎，吕晓宁，李峰，等. 考虑动态需求的外卖配送路径优化模型及算法［J］. 控制与决策， 2019， 34（2）： 406-413.
	Li T Y， Lyu X N， Li F， et al. Routing optimization model and algorithm for takeout distribution with multiple fuzzy variables under dynamics demand［J］. Control and Decision， 2019， 34（2）： 406-413.
[6]	Ulmer M W， Thomas B W， Campbell A M， et al. The restaurant meal delivery problem： Dynamic pickup and delivery with deadlines and random ready times［J］. Transportation Science， 2020， 55（1）： 75-100.
[7]	周成昊，吕博轩，周翰宇，等. 以商圈为中心的O2O动态外卖配送路径优化模型与算法［J］. 运筹学学报， 2022， 26（3）： 17-30.
	Zhou C H， Lyu B X， Zhou H Y， et al. Optimization model and algorithm for Online to Offline dynamic take-out delivery routing problem centered on business districts［J］. Operations Research Transactions， 2022， 26（3）： 17-30.
[8]	范厚明，咸富山，王怀奇. 动态需求下考虑订单聚类的外卖配送路径优化［J］. 系统仿真学报， 2023， 35（2）： 396-407.
	Fan H M， Xian F S， Wang H Q. Takeout distribution routes optimization considering order clustering under dynamic demand［J］. Journal of System Simulation， 2023， 35（2）： 396-407.
[9]	Xie F， Chen Z， Zhang Z. Research on dynamic takeout delivery vehicle routing problem under time-varying subdivision road network［J］. Mathematics， 2024， 12（7）： 962-983.
[10]	Lu F， Chen W， Feng W， et al. 4PL routing problem using hybrid beetle swarm optimization［J］. Soft Computing， 2023， 27（22）： 17011-17024.
[11]	Liu Y. An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones［J］. Computers and Operations Research， 2019， 111（C）： 1-20.
[12]	Das D N， Sewani R， Wang J， et al. Synchronized truck and drone routing in package delivery logistics［J］. IEEE Transactions on Intelligent Transportation Systems， 2021， 22（9）： 5772-5782.
[13]	Tamke F， Buscher U. A branch-and-cut algorithm for the vehicle routing problem with drones［J］. Transportation Research Part B： Methodological， 2021， 144： 174-203.
[14]	Zhen L， Gao J， Tan Z， et al. Branch-price-and-cut for trucks and drones cooperative delivery［J］. IISE Transactions， 2023， 55（3）： 271-287.
[15]	赵强柱，卢福强，王雷震，等. 无人机骑手联合外卖配送路径优化问题研究［J］. 计算机工程与应用， 2022， 58（11）： 269-278.
	Zhao Q Z， Lu F Q， Wang L Z， et al. Research on drones and riders joint take-out delivery routing problem［J］. Computer Engineering and Applications， 2022， 58（11）： 269-278.
[16]	Imran N M， Mishra S， Won M. A-VRPD： Automating drone-based last-mile delivery using self-driving cars［J］. IEEE Transactions on Intelligent Transportation Systems， 2023， 24（9）： 9599-9612.
[17]	Kuo R J， Edbert E， Zulvia F E， et al. Applying NSGA-II to vehicle routing problem with drones considering makespan and carbon emission［J］. Expert Systems with Applications， 2023， 221： 119777.
[18]	Pina-Pardo J C， Silva D F， Smith A E， et al. Dynamic vehicle routing problem with drone resupply for same-day delivery［J］. Transportation Research Part C： Emerging Technologies， 2024， 162： 104611.
[19]	张帅，刘思亮，张文宇. 电动车-无人机协同配送模式下带时间窗的车辆路径优化问题［J］. 中国管理科学， 2025， 33（4）： 131-141.
	Zhang S， Liu S L， Zhang W Y. Vehicle routing problems with time windows under the collaborative delivery mode of electric vehicle-drone［J］. Chinese Journal of Management Science， 2025， 33（4）： 131-141.
[20]	Lu F， Jiang R， Bi H， et al. Order distribution and routing optimization for takeout delivery under drone–rider joint delivery mode［J］. Journal of Theoretical and Applied Electronic Commerce Research， 2024， 19（2）： 774-796.
[21]	杨林. 基于LSTM-EMD-BP神经网络O2O外卖分类的订单量预测［D］. 大连：东北财经大学， 2022.
	Yang L. Order quantity prediction based on LSTM-EMD-BP neural network O2O takeout classification［D］. Dalian： Dongbei University of Finance and Economics， 2022.
[22]	Frey B J， Dueck D. Clustering by passing messages between data points［J］. Science， 2007， 315（5814）： 972-976.

符号	参数或变量说明	符号	参数或变量说明
V	商家与顾客点的集合V={0}∪V₀ ={0,1,2…n},0表示商家，V₀={1,2…n}表示顾客点	[ET_i,LT_i ]	顾客i时间窗限制，ET_i 预期到达时间，LT_i 最晚接受到达时间
K	骑手的集合K={1,2…k_max }	v_p	骑手的速度
d_ij	从节点i到节点j的距离	c_p1	骑手固定成本
W^k_max	电车的最大载货量	c_p2	骑手单位行驶成本
t_j^k	骑手到达节点j的时间	q_i^k	骑手k所接受订单i的外卖重量
x^k_ij	决策变量，若骑手k从节点i到节点j时为1，否则为0	t_ik^m	骑手k走过m个节点，到达顾客i的时间

符号	参数或变量说明	符号	参数或变量说明
H	划分的时间片段集合H={1,2…h}	A	无人机集合A={1,2…a_max }
G	无人机送餐点的集合G={g₁，g₂，…g_m },G∈V	t_j^a	无人机到达节点j的时间
V^h_new	h时间片内产生的新订单的集合，e表示新订单个数，V^h_new={n+1,n+2…n+e}	c_u1	无人机固定成本
V	V=V+V^h-¹_new={0,1,2…n},V^h-¹_new 上一个片段产生的新订单集合	c_u2	无人机单位行驶成本
V_h^k	骑手k在h时间片内，未加入新订单时未完成配送的顾客订单集合，V_h^k∈V	Q^a_max	无人机最大电池电量
V_h^a	无人机a在h时间片内的需要取送的顾客订单集合，V_h^a∈V^h_new	v_u	无人机的速度
q_i^a	无人机a所接受订单i的外卖重量	W^u_max	无人机的最大载货量
x^a_ij	决策变量，若无人机a从节点i到节点j时为1，否则为0。

R型	X	Y	ET	LT	重量
0	1400	1400	—	—	—
1	957.6	190.4	26	36	1.2
2	375.2	1064	22	32	1.3
3	448	2240	25	35	1.1
4	2458.4	1327.2	21	31	0.9
5	2111.2	2156	21	31	1.2
6	2514.4	2396.8	30	40	0.7
7	1915.2	2693.6	28	38	0.5
8	2609.6	834.4	27	37	1.2
9	464.8	1624	19	29	1.1
10	1405.6	352.8	21	31	1.4
11	1836.8	2749.6	28	38	0.5
12	1456	2643.2	25	35	1.4
13	1624	812	13	23	1.4

序号	X	Y	ET	LT	重量	序号	X	Y	ET	LT	重量
14	1489.6	1237.6	25	35	1.4	21	1920.8	1545.6	22	32	1.2
15	918.4	1792	13	23	1.4	22	582.4	1954.4	30	40	1.4
16	291.2	2307.2	8	18	0.9	23	156.8	2615.2	11	21	1.2
17	2716	582.4	12	22	0.6	24	509.6	2391.2	20	30	0.8
18	806.4	1853.6	29	39	0.7	25	2402.4	2665.6	30	40	1.1
19	2167.2	2206.4	30	40	1.0	26	1176	1545.6	27	37	0.6
20	2643.2	319.2	15	25	0.6	27	324.8	218.4	30	40	0.9

编号	无人机辅助骑手配送			骑手配送
编号	完成订单	骑手配送路径	无人机路径	完成订单	骑手配送路径
1	—	4-8-(17)-(20)	0-8-0	—	4-8
2	—	5-(19)-12-11-7-6-(25)	0-19-0	—	5-6-7-11-12
3	—	2-9-(15-18-22)-3-(24-23-16)	0-9-0	—	2-9-3
4	13	10-1-(27)	0-1-0	13	10-1
5	—	(26-14-21)	—	—	(22-24-16-23)
6				—	(17-20)
7				—	(21-19-25)
8				—	(14-26-15-18-27)

Routing Optimization of Drone Assisted Riders Takeout Delivery under Dynamic Orders

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 22

Related Articles 15

Metrics

Comments

Recommended 0

类型	结果	时间段(订单量)
		11:00-12:00 (352)		14:00-15:00 (73)		17:00-18:00 (167)
		无人机辅助骑手	传统骑手	无人机辅助骑手	传统骑手	无人机辅助骑手	传统骑手
C	骑手个数	30	44	8	11	14	20
	无人机个数	6	—	3	—	8	—
	配送成本	1600.62	2243.87	441.80	566.14	803.52	1025.11
	顾客整体满意度	97.87	95.42	99.79	100.00	99.69	99.80
	惩罚成本	43.52	90.03	1.30	0.00	4.81	2.52
	运行时间	8.27	4.74	2.39	1.89	4.43	2.51
	总配送成本	1644.13	2333.90	443.10	566.14	808.33	1027.63
R	骑手个数	28	35	8	10	14	17
	无人机个数	9	—	3	—	5	—
	配送成本	1531.91	1794.34	441.85	517.26	775.00	877.44
	顾客整体满意度	97.41	95.47	99.79	98.65	98.83	99.57
	惩罚成本	50.36	84.52	1.30	6.43	13.98	5.19
	运行时间	8.02	4.10	2.40	1.89	4.20	2.35
	总配送成本	1582.27	1878.86	443.15	523.70	788.98	882.63
RC	骑手个数	32	39	8	11	17	19
	无人机个数	7	—	3	—	7	—
	配送成本	1712.25	1997.85	445.72	566.63	947.53	977.80
	顾客整体满意度	98.61	97.04	99.85	97.53	97.52	97.74
	惩罚成本	25.75	109.16	1.32	8.36	22.93	27.01
	运行时间	7.01	4.24	2.47	1.92	4.80	2.47
	总配送成本	1738.01	2107.01	447.04	574.99	970.46	1004.81

[1]	Fulai Cui, Yidong Chai, Yuanchun Jiang, Yang Qian, Jianshan Sun, Yezheng Liu. Online Doctor Recommendation Considering the Uncertainty of Deep Learning Models [J]. Chinese Journal of Management Science, 2025, 33(11): 151-161.
[2]	Feng Shi, Yang Yang, Yun Yuan, Jianmin Jia. Marketing Transformation in the Age of Artificial Intelligence [J]. Chinese Journal of Management Science, 2025, 33(1): 111-123.
[3]	Guoquan Chen, Yanling Lin, Jingyi Wang, Qingye Luo, Yue Fu. Leader’s Buffering Mechanism Based on Space-Time Ratio and Case Study [J]. Chinese Journal of Management Science, 2024, 32(12): 1-14.
[4]	Shun Liu, Xiaoyu Huang, Zhengzheng Xian, Wenming Zuo. A Commodity Warehouse Allocation Model Based on Hypergraph Embedding [J]. Chinese Journal of Management Science, 2024, 32(11): 270-278.
[5]	Zihao Chu,Zhe Xu,Dongning Liu. Model and Algorithm on Stochastic Scheduling Problem with Activity Overlapping [J]. Chinese Journal of Management Science, 2024, 32(7): 84-94.
[6]	Xiaoyu Huang,Zhengzheng Xian,Xiongwen Yang,Wenming Zuo. Collaborative Filtering with Minority Report [J]. Chinese Journal of Management Science, 2024, 32(3): 20-27.
[7]	Jian-fei LI,Kun TANG,Yang SHEN. Price Resonance and the Security and Stability of Hog Industry Chain: A Prediction Based on Price Mode Dissipation [J]. Chinese Journal of Management Science, 2023, 31(12): 290-300.
[8]	YANG Shan-lin, LI Xiao-jian, ZHANG Qiang, JIAO Jian-ling, YANG Chang-hui. Artificial Intelligence and Management Transformation [J]. Chinese Journal of Management Science, 2023, 31(6): 1-11.
[9]	DONG Bing-jie, CHI Guo-tai. Study on Default Prediction Based on Sentiment Data [J]. Chinese Journal of Management Science, 2023, 31(4): 111-120.
[10]	WANG Yong, LUO Si-yu, ZHEN Lu, XU Mao-zeng. Multi-center Pickup and Delivery Network Alliance Optimization Considering Default Penalties and Loss Compensations for Breach of Contract [J]. Chinese Journal of Management Science, 2023, 31(3): 10-25.
[11]	GAO Jia-jing, ZHEN Lu. Research on Routing Problem for Joint Delivery System Based on Multiple Trucks and Robots [J]. Chinese Journal of Management Science, 2023, 31(3): 48-57.
[12]	CHEN Guo-quan, WANG Jing-yi, LIN Yan-ling, LIU Wei, ZHOU Qi-wei, XU Fen. A Study on the Model of Multi-individual Learning from Experience: From the Perspective of Matching between Information and Analytic Method [J]. Chinese Journal of Management Science, 2023, 31(3): 259-267.
[13]	CHEN Guo-quan, WANG Jing-yi, LIN Yan-ling, LIU Wei, ZHOU Qi-wei, XU Fen. A Study on the Model of Multi-individual Learning from Experience: From the Perspectives of Information Heterogeneity and Analytic Method Heterogeneity [J]. Chinese Journal of Management Science, 2023, 31(1): 187-199.
[14]	YAN Lan, LI Si-han, XIAO Yi, KOU Yu-xuan, LIU Dun-hu, XIAO Jin. Metacost Based Semi-supervised Heterogeneous Ensemble Model for Customer Credit Scoring [J]. Chinese Journal of Management Science, 2022, 30(12): 211-221.
[15]	YUAN Xianzhi, ZHOU Yun-peng, YAN Cheng-xing, LIU Hai-yang, QIAN Guo-qi, WANG Fan, WEI Li-jian, LI Zhi-yong, LI Bo, David Li, ZENGTu. The Framework for the Risk Feature Extraction Method on Corporate Financial Fraud George [J]. Chinese Journal of Management Science, 2022, 30(3): 43-54.