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

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

摘要/Abstract

摘要：

针对外卖订单动态产生和骑手不断变化等问题，提出了无人机辅助骑手配送模式。利用双峰高斯函数模拟配送过程中新订单的生成，以最小配送成本和顾客整体最大满意度为目标函数构建了两阶段优化模型。其中，第一阶段针对静态顾客建立了骑手配送的初始优化模型，第二阶段针对动态产生的新订单，建立了无人机辅助骑手配送的动态调整模型。针对该模型设计了一个两阶段启发式算法进行求解，第一阶段采用基于K-means和KNN分类算法改进的AP聚类算法进行动态订单分配，第二阶段利用结合插入算法改进的禁忌搜索算法进行路径优化。通过算例仿真，验证模型和算法的有效性和可行性。结果表明，与传统的骑手配送模式相比，无人机辅助骑手配送模式能有效减少使用骑手数量、降低配送成本。

关键词: 无人机辅助骑手, 外卖配送, 动态路径优化, 禁忌搜索算法, AP聚类算法

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

中图分类号:

TP18

卢福强,蒋润雪,毕华玲, 等. 动态订单下无人机辅助骑手外卖配送路径优化研究[J]. 中国管理科学, 2026, 34(2): 79-88.

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.

图/表 12

图1

表 1

表2

图2

表 3

仿真实验参数设置"

实验参数	符号	取值	实验参数	符号	取值	实验参数	符号	取值
骑手平均车速	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

表 3

表 4

图3

表5

表6

图4

图5

表 7

参考文献 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)