考虑骑手配送时效奖惩的外卖多目标路径优化研究

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

摘要/Abstract

摘要：

在外卖行业中，配送时效不仅影响着顾客满意度和平台的利润，还直接涉及对骑手的奖惩。因此，本研究从配送时效的角度，构建了考虑骑手奖惩的外卖配送多目标模型，并设计了改进NSGA-II算法进行求解。首先，利用软时间窗来构建线性顾客满意度函数，并结合基于配送时效的超时惩罚与绩效奖励，建立与距离相关的骑手收益目标，以及考虑订单抽成的平台利润目标。此外，设计了基于KNN分类的改进NSGA-II算法进行优化。先利用基于欧式距离与时间窗的KNN分类生成初始路径；再采用结合前向连续交叉策略的改进NSGA-II算法进行优化输出帕累托解。最后，经过算例验证，本研究提出的算法具有良好的性能，且经分析得出奖惩机制配置会对三方的效益产生不同影响。

关键词: 外卖配送, 配送时效, 骑手奖惩, 多目标优化, 改进NSGA-II算法

Abstract:

Presently， the takeaway industry continues to demonstrate robust growth， with takeaway services becoming increasingly entrenched in people's daily lives. Nevertheless， given the differences in focal points of platforms， consumers， and riders， a pronounced discord of interests has emerged among the three parties， even hindering the development of the industry. Distribution timeliness， a pivotal factor， impacts not only customer satisfaction and platform profits but also directly influences the rewards and punishments for riders. To address these challenges， a multi-objective routing optimization problem is proposed for takeout delivery， considering the rewards and punishments for riders based on the perspective of distribution timeliness. The primary aim of this study is to further balance the interests of all parties dynamically. A soft time window concept is adopted to portray customer expectations and tolerance of delivery time， and a linear time satisfaction function is constructed to assess customer satisfaction. Concurrently， the rider's rewards and penalties are designated， encompassing the rider's overtime penalty cost based on on-time rate， the order overtime penalty cost in step-pricing style， and the performance reward based on satisfaction. The functions of rider revenue， driving cost， waiting cost， and platform revenue are then combined to establish a complex objective optimization model for maximizing customer satisfaction， rider revenue， and platform profit. Secondly， an enhanced NSGA-II algorithm based on KNN classification is proposed. The proposed algorithm first allocates orders based on geographic distance and time window， generates high-quality and diverse initial populations， and subsequently outputs a Pareto solution using the enhanced NSGA-II algorithm. To assess the efficacy of the proposed algorithm， two ordinary region examples and one commercial region example are utilized for testing purposes. It then compares this algorithm with the traditional NSGA-II and MOPSO algorithms for validation purposes. The convergence of the algorithm and the diversity of the solution set are further verified by analyzing the iterative convergence curves of each objective function as well as the indicators of spacing and maximum spread of the solution set. Finally， a comparative analysis of customer satisfaction， rider revenue， and platform profit under different reward and punishment rules is conducted. It is indicated that the platform's punishment measures can enhance delivery efficiency， foster customer satisfaction and augment platform revenue. Equitable sanctions have the potential to engender a mutually beneficial scenario for all three parties. While the incentive mechanism may temporarily reduce platform revenue， it can enhance delivery efficiency and rider revenue. Consequently， a theoretical foundation is offered for the coordination of interests among multiple parties in the future of takeaway services and the establishment of a platform's reward and punishment mechanism for riders.

Key words: takeout delivery, distribution timeliness, rewards and penalties of riders, multi-objective optimization, the improved NSGA-II algorithm

中图分类号:

C931

熊浩,陈晓蝶,鄢慧丽. 考虑骑手配送时效奖惩的外卖多目标路径优化研究[J]. 中国管理科学, 2026, 34(9): 209-224.

Hao Xiong,Xiaodie Chen,Huili Yan. Multi-Objective Routing Optimization of Takeout Delivery Considering Rider Rewards and Penalties of Distribution Timeliness[J]. Chinese Journal of Management Science, 2026, 34(9): 209-224.

图/表 18

图1

表1

模型符号说明"

符号	定义	符号	定义
R	订单集合	$c 1$	骑手单位行驶成本
$r$	订单编号	$c 2$	骑手单位等待成本
S	商家坐标集合，可以表示为 $S = 1,2, …, s$	$N$	节点坐标的合集，可表示为 $N = S ⋃ C ∪ {O}$
C	顾客集合，可以表示为 $C = s + 1, s + 2, …, s + c$	$y k r$	0-1变量，若为1表示订单r分配给骑手k,否则为0
O	配送中心	$θ$	平台佣金比例
$φ i$	骑手配送收入， $i ∈ {1,2, 3}$	$b$	平台保底佣金
$K$	骑手集合	$α$	顾客满意度奖励标准
$k$	骑手编号	$β$	允许超时订单数量
$S r$	订单r对应的商家	$c 3$	超时惩罚成本
$C r$	订单r对应的顾客	$O r$	订单r的餐饮金额
$m k$	骑手k配送订单的平均满意度	$n k$	骑手k超时订单数量, $k ∈ K$
$Q$	电瓶车最大可承载容量	$d k$	骑手k激励补贴额
$D$	电瓶车最长可行驶公里数	$t r 0$	订单r商家出餐时间
$x i j$	由节点i到节点j所需行驶的距离， $i, j ∈ N$	$E r$	订单r允许车辆到达的最早时间
$w i j k$	0-1变量，若为1表示骑手k选择从商家点i至顾客点j,否则为0	$z j i k$	0-1变量，若为1表示骑手k从顾客点j至商家点i，否则为0
$e r$	订单r满意的最早到达时间	$L r$	订单r允许车辆到达的最晚时间
$H r$	平台赚取的订单r收入	$l r$	订单r满意的最晚到达时间
$D r$	订单r配送收入, $r ∈ R$	$t i j$	骑手从节点i到节点j的行驶时间
$a$	骑手绩效奖励	$t i k$	骑手k到达节点i的时间
$t S r k$	骑手k配送订单r时到达商家节点的时间	$c 4 i$	骑手超时单位时间惩罚成本， $i ∈ {1,2}$

表1

图2

图3

图4

图5

图6

图7

图8

表2

参数取值"

$c 1$	$c 2$	$c 3$	$φ 1$	$φ 2$	$φ 3$	$θ$	$a$	$b$	$α$	β	$c 41$	$c 42$	$λ$
0.3元/km	0.35元/min	2元/单	8元/单	10元/单	12元/单	21%	25元	12元	85%	1	0.1元/分钟	0.2元/分钟	0.1

表2

图9

图10

表3

图11

表4

图12

图13

图14

参考文献 32

[1]	中国互联网络信息中心. 第54 次中国互联网络发展状况统计报告［EB/OL］.（2024-08-29）［2025-04-28］. .
	China Internet Network Information Center. The 54th statistical report on China’s internet development［EB/OL］.（2024-08-29）［2025-04-28］..
[2]	美团新闻中心. 美团2024年第二季度财务报告［EB/OL］.（2024-08-28）［2025-04-22］..
	Meituan News Center. Meituan 2024 second quarter financial report［EB/OL］.（2024-08-28）［2025-04-22］..
[3]	阿里巴巴集团. 阿里巴巴2024年第二季度财务报告［EB/OL］.（2024-08-15）［2025-04-19］..
	Group Alibaba. Alibaba 2024 second quarter financial report［EB/OL］.（2024-08-15）［2025-04-19］. .
[4]	张力娅，张锦，肖斌. 考虑顾客优先级的多目标O2O外卖即时配送路径优化研究［J］. 工业工程与管理， 2021， 26（2）： 196-204.
	Zhang L Y， Zhang J， Xiao B. Multi-objective O2O take-out instant delivery routing optimization considering customer priority［J］. Industrial Engineering and Management， 2021， 26（2）： 196-204.
[5]	熊浩，郭昊颖，鄢慧丽，等. 外卖配送路径多目标实时优化研究［J］. 工业工程， 2023， 26（1）： 98-107.
	Xiong H， Guo H Y， Yan H L， et al. Multi-objective real-time optimization study of takeaway vehicle routes problem［J］. Industrial Engineering Journal， 2023， 26（1）： 98-107.
[6]	熊浩，鄢慧丽. 数据驱动外卖平台智能派单的实现机理研究［J］. 南开管理评论， 2022， 25（2）： 15-25.
	Xiong H， Yan H L. Research on the data-driven mechanism of intelligent order dispatching of takeaway platform［J］. Nankai Business Review， 2022， 25（2）： 15-25.
[7]	熊浩，鄢慧丽. 外卖智能派单的订单-骑手多目标匹配模型及其适应性算法研究［J］. 管理工程学报， 2024， 38（3）： 150-160.
	Xiong H， Yan H L. The multi-objective optimization model of order-driver matching and its online adaptive algorithm for the meal delivery platform［J］. Journal of Industrial Engineering and Engineering Management， 2024， 38（3）： 150-160.
[8]	邵乾虔，李冲，代广徽，等. 基于动态订单合并的滚动配取路径多目标优化［J］. 管理工程学报， 2024， 38（6）： 140-155.
	Shao Q Q， Li C， Dai G H， et al. Multi-objective optimization of pickup and delivery routing based on dynamic order combination［J］. Journal of Industrial Engineering and Engineering Management， 2024， 38（6）： 140-155.
[9]	余建军，程文琪，吴永忠. 考虑顾客满意度的生鲜外卖路径规划［J］.工业工程与管理，2021，26（4）： 158-167.
	Yu J J， Cheng W Q， Wu Y Z. Path planning of fresh takeout considering customer satisfaction［J］. Industrial Engineering and Management， 2021， 26（4）： 158-167.
[10]	于江霞，卞喆，罗太波. 基于均衡准则的多目标即时配送路径优化模型［J］. 管理现代化， 2022， 42（2）： 94-99.
	Yu J X， Bian Z， Luo T B. Research on optimization of multi-objective instant delivery based on equilibrium criterion［J］. Modernization of Management， 2022， 42（2）： 94-99.
[11]	熊浩，鄢慧丽. 外卖智能派单的多主体利益协调机理研究［J］. 软科学， 2024， 38（8）： 105-113.
	Xiong H， Yan H L. The mechanism of multi-agent cooperation on the food delivery platform［J］. Soft Science， 2024， 38（8）： 105-113.
[12]	余海燕，李红梅，王姝翔. O2O外卖众包即时配送平台的激励机制适用性［J］. 系统工程， 2022， 40（4）： 89-99.
	Yu H Y， Li H M， Wang S X. The applicability of incentive mechanism of O2O takeaway crowdsourcing real-time distribution platform［J］. Systems Engineering， 2022， 40（4）： 89-99.
[13]	马成颖，牟海波. 考虑路况、配送员与顾客满意度的冷链物流车辆配送路径优化方法［J］. 交通信息与安全， 2022， 40（5）： 156-168.
	Ma C Y， Mou H B. A route optimization method for cold chain logistics vehicles considering road conditions， satisfaction of deliverymen and customers［J］. Journal of Transport Information and Safety， 2022， 40（5）： 156-168.
[14]	王晓全，代存杰，李娟，等. 不确定运输风险下危险品绿色配送路径优化［J］. 计算机工程与应用， 2023， 59（14）： 323-332.
	Wang X Q， Dai C J， Li J， et al. Optimization of green distribution routes for hazardous materials under uncertain transportation risk［J］. Computer Engineering and Applications， 2023， 59（14）： 323-332.
[15]	Zhang J， Li Y. Collaborative vehicle-drone distribution network optimization for perishable products in the epidemic situation［J］. Computers & Operations Research， 2023， 149： 106039.
[16]	苟梦圆，王勇，罗思妤，等.带时间窗的多中心开闭混合式电动车配送路径优化问题研究［J］.中国管理科学， 2024. DOI： 10.16381/j.cnki.issn1003-207x.2023.2045 .
	Gou M Y， Wang Y， Luo S Y， et al. Research on distribution path optimization of multi-center open-close hybrid electric vehicle with time window［J］. Chinese Journal of Management Science， 2024，DOI： 10.16381/j.cnki.issn1003-207x.2023.2045 .
[17]	邱金红，孙靖，仲兆满. 基于配送收益均衡的多目标绿色车辆路径优化算法［J］. 控制与决策， 2023， 38（2）： 365-371.
	Qiu J H， Sun J， Zhong Z M. A multi-objective green vehicle routing optimization algorithm based on delivery benefit balance［J］. Control and Decision， 2023， 38（2）： 365-371.
[18]	杨洋，武志磊，王晓霞. 不确定需求下物流配送网点选址多目标优化及仿真［J］. 科学技术与工程， 2024， 24（14）： 5994-6002.
	Yang Y， Wu Z L， Wang X X. Multi-objective optimization and simulation of logistics distribution network location under uncertain demand［J］. Science Technology and Engineering， 2024， 24（14）： 5994-6002.
[19]	王勇，罗思妤，镇璐，等. 考虑违约追偿和损失补偿的多中心集配网络联盟优化问题［J］. 中国管理科学， 2023， 31（3）： 10-25.
	Wang Y， Luo S Y， Zhen L， et al. 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.
[20]	Zhen L， Wu J， Laporte G， et al. Heterogeneous instant delivery orders scheduling and routing problem［J］. Computers & Operations Research， 2023， 157： 106246.
[21]	周成昊，吕博轩，周翰宇，等. 以商圈为中心的O2O动态外卖配送路径优化模型与算法［J］. 运筹学学报（中英文）， 2022， 26（3）： 17-30.
	Zhou C H， Lv 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.
[22]	郭昊颖，熊浩，任汭杨，等. 允许取送交叉和中途接单的外卖配送路径优化［J］.系统工程，2022， 40（5）： 70-81.
	Guo H Y， Xiong H， Ren R Y， et al. The optimization of takeout delivery route that allows cross picking and delivery and order halfway［J］. Systems Engineering， 2022， 40（5）： 70-81.
[23]	熊浩，郭昊颖，鄢慧丽，等. 考虑取送交叉和多种扰动因素的外卖配送路径优化研究［J］. 湖南大学学报（自然科学版）， 2022， 49（10）： 92-102.
	Xiong H， Guo H Y， Yan H L， et al. Research on real-time route optimization of takeaway delivery considering pickup and delivery cross and multiple disturbance factors［J］. Journal of Hunan University （Natural Sciences）， 2022， 49（10）： 92-102.
[24]	范厚明，咸富山，王怀奇. 动态需求下考虑订单聚类的外卖配送路径优化［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.
[25]	卢福强，蒋润雪，毕华玲，等.动态订单下无人机辅助骑手外卖配送路径优化研究［J］.中国管理科学， 2026，34 （2）： 79-88.
	Lu F Q， Jiang R X， Bi H L， et al. Research on optimization of delivery path of UAV-assisted rider under dynamic order［J］. Chinese Journal of Management Science， 2026，34 （2）： 79-88.
[26]	Deb K， Pratap A， Agarwal S， et al. A fast and elitist multiobjective genetic algorithm： NSGA-II［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197.
[27]	赵向南，邢磊，靳志宏. 考虑不确定行驶时间的双目标外卖配送路径优化［J］. 大连海事大学学报， 2019， 45（4）： 65-72.
	Zhao X N， Xing L， Jin Z H. Bi-objective takeaway distribution route optimization considering uncertain driving time［J］. Journal of Dalian Maritime University， 2019， 45（4）： 65-72.
[28]	Liao W， Zhang L， Wei Z. Multi-objective green meal delivery routing problem based on a two-stage solution strategy［J］. Journal of Cleaner Production， 2020， 258： 120627.
[29]	任腾，陈玥，向迎春，等. 考虑客户满意度的低碳冷链车辆路径优化［J］. 计算机集成制造系统， 2020， 26（4）： 1108-1117.
	Ren T， Chen Y， Xiang Y C， et al. Optimization of low-carbon cold chain vehicle path considering customer satisfaction［J］. Computer Integrated Manufacturing Systems， 2020， 26（4）： 1108-1117.
[30]	梁萌. “数字泰勒主义” 影响下的外卖平台 “计件工资制” 研究［J］. 社会， 2024， 44（3）： 1-26.
	Liang M. A study of piecework wage system of food-delivery platforms under the influence of digital Taylorism［J］. Society， 2024， 44（3）： 1-26.
[31]	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.
[32]	吴擎，张春江，高亮. 一种基于混合交叉的差分进化算法［J］. 华中科技大学学报（自然科学版）， 2018， 46（5）： 78-83+105.
	Wu Q， Zhang C J， Gao L. Differential evolution algorithm based on hybrid crossover［J］. Journal of Huazhong University of Science and Technology （Nature Science Edition）， 2018， 46（5）： 78-83+105.

算例	测试次数	算法类型	顾客满意度(%)	骑手收益(元)	平台利润(元)	测试次数	算法类型	顾客满意度(%)	骑手收益(元)	平台利润(元)
算例1	1	KNN-NSGA-II	82.38	41.75	352.10	4	KNN-NSGA-II	81.28	37.01	350.27
		NSGA-II	69.35	28.50	338.14		NSGA-II	72.96	32.88	331.47
		MOPSO	72.30	27.5	327.50		MOPSO	68.51	20.87	337.01
	2	KNN-NSGA-II	83.33	39.28	354.05	5	KNN-NSGA-II	82.10	41.04	348.80
		NSGA-II	75.07	32.46	343.63		NSGA-II	75.32	32.81	332.61
		MOPSO	75.00	29.73	324.19		MOPSO	75.74	37.13	302.08
	3	KNN-NSGA-II	81.65	40.16	353.08	6	KNN-NSGA-II	83.25	40.89	356.90
		NSGA-II	73.67	34.63	344.15		NSGA-II	73.08	31.03	334.11
		MOPSO	69.89	21.72	334.60		MOPSO	65.18	21.34	333.68
算例2	1	KNN-NSGA-II	72.64	31.94	444.89	4	KNN-NSGA-II	72.10	31.95	439.45
		NSGA-II	64.23	20.42	422.13		NSGA-II	62.37	17.18	421.94
		MOPSO	65.00	22.56	423.25		MOPSO	65.48	19.84	428.84
	2	KNN-NSGA-II	72.63	31.97	458.64	5	KNN-NSGA-II	72.43	30.14	439.71
		NSGA-II	61.22	18.97	420.24		NSGA-II	62.37	17.82	409.61
		MOPSO	66.22	19.83	421.32		MOPSO	66.90	20.41	429.91
	3	KNN-NSGA-II	72.61	30.65	437.71	6	KNN-NSGA-II	71.53	31.03	436.70
		NSGA-II	62.85	19.51	403.11		NSGA-II	61.39	18.08	413.11
		MOPSO	62.87	19.10	419.12		MOPSO	67.55	22.32	429.61
算例3	1	KNN-NSGA-II	79.50	38.87	803.83	4	KNN-NSGA-II	78.37	37.95	802.00
		NSGA-II	61.25	30.97	786.90		NSGA-II	66.39	30.89	789.75
		MOPSO	64.67	34.93	787.34		MOPSO	66.53	30.92	790.35
	2	KNN-NSGA-II	81.15	40.81	806.75	5	KNN-NSGA-II	80.13	39.87	804.41
		NSGA-II	62.74	31.52	786.77		NSGA-II	63.14	28.83	784.19
		MOPSO	62.03	30.01	774.40		MOPSO	62.00	31.31	783.55
	3	KNN-NSGA-II	80.79	41.23	805.51	6	KNN-NSGA-II	82.28	42.74	809.71
		NSGA-II	64.34	28.48	785.22		NSGA-II	68.36	30.88	784.15
		MOPSO	63.28	28.43	783.75		MOPSO	69.55	33.79	780.25

算例	指标	测试1	测试2	测试3	测试4	测试5	测试6
算例1	MS	1.5781	1.3764	1.3377	1.5338	1.4379	1.3984
算例1	Spacing	0.5821	0.6022	0.5921	0.6234	0.6102	0.6491
算例2	MS	1.3518	1.3103	1.3061	1.3710	1.4881	1.4341
算例2	Spacing	0.6595	0.6009	0.6464	0.5868	0.5357	0.6250
算例3	MS	1.4344	1.4614	1.4194	1.4181	1.4118	1.3649
算例3	Spacing	0.6013	0.6146	0.5693	0.6115	0.6213	0.6129