考虑工作量平衡的多目标取送货路径规划

doi:10.12305/j.issn.1001-506X.2026.04.15

Abstract

Abstract:

Regarding the vehicle workload balance in the vehicle routing problem, a multi-objective order allocation and path planning joint optimization model is established, aiming to minimize the platform delivery cost, maximize customer satisfaction, and balance vehicle workload. Considering the characteristics of the problem, a heuristic algorithm based on the non-dominated sorting genetic algorithm II (NSGA-II) framework is designed. The intra-path node relocation operator, intra-path order relocation operator, inter-path order exchange operator, inter-path order relocation operator, and route balance operator are used to improve the algorithm’s search ability and find higher-quality solution. Finally, the effectiveness of the model and algorithm is demonstrated through case study. The experimental results show that the model and algorithm proposed in this paper can achieve a balance among multiple objectives, improve the vehicle workload balance without significantly increasing the platform delivery cost or reducing customer satisfaction. Compared with NSGA-II and multi-objective ant colony algorithm, the proposed variable neighborhood search-based NSGA-II algorithm has better search ability.

Key words: city logistics, pickup and delivery, vehicle routing problem, multi-objective optimization, variable neighborhood search, workload balance

CLC Number:

Yusi XIE, Qin LEI, Zhibin WU. Multi-objective pickup and delivery routing planning with consideration of workload balance[J]. Systems Engineering and Electronics, 2026, 48(4): 1254-1263.

Figures/Tables 22

Fig.1

Table 1

Table 2

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Table 3

Table 4

Table 5

Table 6

Table 7

Table 8

Table 9

Table 10

Fig.10

Table 11

Table 12

References 31

1	李翰, 张洪海, 张连东, 等. 城市区域多物流无人机协同任务分配[J]. 系统工程与电子技术, 2021, 43 (12): 3594- 3602.
	LI H, ZHANG H H, ZHANG L D, et al. Multiple logistics unmanned aerial vehicle collaborative task allocation in urban areas[J]. Systems Engineering and Electronics, 2021, 43 (12): 3594- 3602.
2	WANG Y, WEI Z K, LUO S Y, et al. Collaboration and resource sharing in the multidepot time-dependent vehicle routing problem with time windows[J]. Transportation Research Part E: Logistics and Transportation Review, 2024, 192, 103798. doi: 10.1016/j.tre.2024.103798
3	SCHILDE M, DOERNER K F, HARTL R F. Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem[J]. European Journal of Operational Research, 2014, 238 (1): 18- 30. doi: 10.1016/j.ejor.2014.03.005
4	LIU C J, QUILLIOT A, TOUSSAINT H, et al. A filtering system to solve the large-scale shared autonomous vehicles dial-a-ride problem[J]. Transportation Research Part C: Emerging Technologies, 2024, 161, 104551. doi: 10.1016/j.trc.2024.104551
5	JODEAU J, ABSI N, CHEVRIER R, et al. The rail-road dial-a-ride problem[J]. European Journal of Operational Research, 2024, 318 (2): 486- 499. doi: 10.1016/j.ejor.2024.05.036
6	CHENG X, LIAO S Y, HUA Z S. A policy of picking up parcels for express courier service in dynamic environments[J]. International Journal of Production Research, 2017, 55 (9): 2470- 2488. doi: 10.1080/00207543.2016.1231431
7	NERIA G, HILDEBRANDT F D, TZUR M, et al. The restaurant meal delivery problem with ghost kitchens[J]. Transportation Science, 2024, 59(2):433–450.
8	YE A, ZHANG K, CHEN X M, et al. Modeling and managing an on-demand meal delivery system with order bundling[J]. Transportation Research Part E: Logistics and Transportation Review, 2024, 187, 103597. doi: 10.1016/j.tre.2024.103597
9	REN T, LUO T Y, JIA B B, et al. Improved ant colony optimization for the vehicle routing problem with split pickup and split delivery[J] Swarm and Evolutionary Computation, 2023, 77: 101228.
10	ZHU Z Q, CHEN Y R, WAHAB M I M. An exact algorithm for simultaneous pickup and delivery problem with split demand and time windows[J]. Computers & Operations Research, 2024, 170, 106761. doi: 10.1016/j.cor.2024.106761
11	MENG S S, CHEN Y R, LI D. The multi-visit drone-assisted pickup and delivery problem with time windows[J]. European Journal of Operational Research, 2024, 314 (2): 685- 702. doi: 10.1016/j.ejor.2023.10.021
12	ZHAO J, DONG H X, WANG N. Green split multiple-commodity pickup and delivery vehicle routing problem[J]. Computers & Operations Research, 2023, 159, 106318. doi: 10.1016/j.cor.2023.106318
13	FERREIRA K M, DE QUEIROZ T A, MUNARI P, et al. A variable neighborhood search for the green vehicle routing problem with two-dimensional loading constraints and split delivery[J]. European Journal of Operational Research, 2024, 316 (2): 597- 616. doi: 10.1016/j.ejor.2024.01.049
14	吴廷映, 刘兵兵, 余玉刚. 带取货点选择的电动车取送货路径优化的自适应大邻域搜索算法[EB/OL]. [2024-10-15]. https://doi.org/10.16381/j.cnki.issn1003-207x.2024.0142.
	WU T Y, LIU B B, YU Y G. An adaptive large neighborhood search algorithm for electric vehicle pickup-and-delivery routing problem with pickup-points selection[EB/OL]. [2024-10-15]. https://doi.org/10.16381/j.cnki.issn1003-207x.2024.0142.
15	CORTES C E, MATAMALA M, CONTARDO C. The pickup and delivery problem with transfers: formulation and a branch-and-cut solution method[J]. European Journal of Operational Research, 2010, 200 (3): 711- 724. doi: 10.1016/j.ejor.2009.01.022
16	ZHOU S Q, ZHANG D Z, YUAN W, et al. Pickup and delivery problem with electric vehicles and time windows considering queues[J]. Transportation Research Part C: Emerging Technologies, 2024, 167, 104829. doi: 10.1016/j.trc.2024.104829
17	MO Y D, YANG K, HAN S H, et al. Multi-period heterogeneous fleet vehicle routing problem with self-pickup point selection: a last-mile delivery scenario in urban and rural areas[J]. Annals of Operations Research, 2024. DOI: https//doi.org/10.1007/s10479-024-06011-7.
18	KACHITVICHYANUKUL V, SOMBUNTHAM P, KUNNAPAPDEELERT S. Two solution representations for solving multi-depot vehicle routing problem with multiple pickup and delivery requests via PSO[J]. Computers & Industrial Engineering, 2015, 89, 125- 136. doi: 10.1016/j.cie.2015.04.011
19	HOU Y, GUO X Y, HAN H G, et al. Adaptive ant colony optimization algorithm based on real-time logistics features for instant delivery[J]. IEEE Trans. on Cybernetics, 2024, 54(11): 6358–6370.
20	JOZEFOWIEZ N, SEMET F, TALBI E G. Multi-objective vehicle routing problems[J]. European Journal of Operational Research, 2008, 189 (2): 293- 309. doi: 10.1016/j.ejor.2007.05.055
21	LIU C M, CHANG T C, HUANG L F. Multi-objective heuristics for the vehicle routing problem[J]. International Journal of Operations Research, 2006, 3 (3): 173- 181.
22	LI J J, FANG Y, TANG N. A cluster-based optimization framework for vehicle routing problem with workload balance[J]. Computers & Industrial Engineering, 2022, 169, 108221. doi: 10.1016/j.cie.2022.108221
23	MATL P, HARTL R F, VIDAL T. Workload equity in vehicle routing: the impact of alternative workload resources[J]. Computers & Operations Research, 2019, 110, 116- 129. doi: 10.1016/j.cor.2019.05.016
24	LEHUEDE F, PETON O, TRICOIRE F. A lexicographic minimax approach to the vehicle routing problem with route balancing[J]. European Journal of Operational Research, 2020, 282 (1): 129- 147. doi: 10.1016/j.ejor.2019.09.010
25	MANCINI S, GANSTERER M, HARTL R F. The collaborative consistent vehicle routing problem with workload balance[J]. European Journal of Operational Research, 2021, 293 (3): 955- 965.
26	徐倩, 熊俊, 杨珍花, 等. 基于自适应大邻域搜索算法的外卖配送车辆路径优化[J]. 工业工程与管理, 2021, 26 (3): 115- 122.
	XU Q, XIONG J, YANG Z H, et al. Route optimization of takeout delivery vehicles based on adaptive large neighborhood search algorithm[J]. Industrial Engineering and Management, 2021, 26 (3): 115- 122.
27	TENG R, HONG-BO X, KANG-NING J, et al. Optimisation of takeaway delivery routes considering the mutual satisfactions of merchants and customers[J]. Computers & Industrial Engineering, 2021, 162, 107728. doi: 10.1016/j.cie.2021.107728
28	邱金红, 孙靖, 仲兆满. 基于配送收益均衡的多目标绿色车辆路径优化算法[J]. 控制与决策, 2023, 38 (2): 365- 371. doi: 10.13195/j.kzyjc.2021.0669
	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. doi: 10.13195/j.kzyjc.2021.0669
29	陈希琼, 胡大伟, 杨倩倩, 等. 多目标同时取送货车辆路径问题的改进蚁群算法[J]. 控制理论与应用, 2018, 35 (9): 1347- 1356. doi: 10.7641/CTA.2018.80085
	CHEN X Q, HU D W, YANG Q Q, et al. An improved ant colony algorithm for multi-objective vehicle routing problem with simultaneous pickup and delivery[J]. Control Theory and Applications, 2018, 35 (9): 1347- 1356. doi: 10.7641/CTA.2018.80085
30	CAI Y Q, CHENG M Q, ZHOU Y, et al. A hybrid evolutionary multitask algorithm for the multiobjective vehicle routing problem with time windows[J]. Information Sciences, 2022, 612, 168- 187. doi: 10.1016/j.ins.2022.08.103
31	REYES D, ERERA A, SAVELSBERGH M, et al. The meal delivery routing problem[J]. Optimization Online, 2018, 6571, 2018.

模型参数	含义
$r\in R $	车辆为$ r $，$R $为所有车辆集合
$m $	可用车辆数量
$n $	等待被配送订单数量
$v $	车辆的骑行速率
$Q $	车辆的最大容量
${l}_{i,j} $	点$i $和点$ j $两点之间的行驶距离
$ {t}_{i,j} $	点$ i $和点$ j $两点之间的行驶时间
$ {p}_{i} $	送货点$ i\in D $，平台所需承担的惩罚成本
$ {y}_{i} $	送货点$ i\in D $，客户的满意度
$ {w}_{r} $	车辆$ r $的工作量
$ \overline{w} $	所有车辆的平均工作量
$ ST $	车辆在节点花费的服务时间
$ {c}_{1} $	车辆行驶单位距离所产生的成本
$ {f}_{1} $	所有车辆的总路径成本
$ {f}_{2} $	平台承担的总惩罚成本
$ {T}_{1} $	订单开始产生超时惩罚的初始送达时间
$ {T}_{2} $	订单进入第二级超时惩罚的送达时间
$ {T}_{3} $	订单进入第三级超时惩罚的送达时间
$ {e}_{1} $	一级超时惩罚成本
$ {e}_{2} $	二级超时惩罚成本
$ {e}_{3} $	三级超时惩罚成本
$ \mu $	客户满意度转折点

决策变量	含义
$ x_{i,j}^{r} $	车辆$ r $是否从点$ i $行驶到点$ j $，若行驶则值为1，否则为0
$ s_{i}^{r} $	车辆$ r $在点$ i $的开始服务时间
$ t_{i}^{r} $	车辆$ r $到达点$ i $的时间
$ q_{i}^{r} $	车辆$ r $在点$ i $装载的订单数量

符号	值
$ v $/(km/h)	24
$ Q $/个	8
ST/min	2
$ {c}_{1} $/(RMB/km)	0.05
$ {T}_{1} $/min	40
$ {T}_{2} $/min	50
$ {T}_{3} $/min	60
$ {e}_{1} $/RMB	3
$ {e}_{2} $/RMB	6
$ {e}_{3} $/RMB	9

参数	值
迭代次数	100
种群个数	100
邻域迭代次数	10
邻域操作次数	5

前沿点	优化目标
前沿点	P/元	S	B/min
1	77.70	0.175	8.21
2	77.71	0.176	8.12
3	77.72	0.184	7.32
4	77.79	0.178	5.92
5	77.82	0.178	5.83
6	77.84	0.179	5.70
7	80.98	0.186	4.52
8	81.02	0.196	3.84
9	83.81	0.177	6.70
10	84.15	0.202	3.67

Multi-objective pickup and delivery routing planning with consideration of workload balance

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 22

References 31

Related Articles 15

Recommended Articles

Metrics

Comments

车辆编号	派单结果	路径规划结果
1	27, 22, 19, 36	1, 27, 22, 67, 62, 19, 36, 76, 59
2	34, 18, 42, 41, 35, 30	2, 34, 18, 42, 41, 81, 74, 82, 35, 30, 70, 75, 58
3	40, 8, 44, 48, 46, 13	3, 40, 8, 80, 44, 48, 46, 84, 86, 13, 53
4	47, 16, 11, 26, 21	4, 47, 16, 87, 56, 11, 26, 51, 66, 21, 61
5	25, 15, 32, 39, 38	5, 25, 15, 55, 65, 32, 72, 39, 79, 38, 78
6	33, 28, 24, 9, 37, 29	6, 33, 28, 24, 9, 64, 49, 73, 68, 37, 77, 29, 69
7	31, 45, 17, 20, 23	7, 31, 45, 17, 71, 85, 57, 20, 60, 23, 63
8	14, 10, 43, 12,	8, 14, 10, 43, 83, 12, 52, 50, 54

单目标模型	VNS-GA				Gurobi
单目标模型	P/元	S	B/min	T/s	P/元	S	B/min	T/s
配送总成本最优	72.04	0.17	13.47	21.66	78.51	0.20	16.91	10800
客户满意度最优	73.99	0.16	11.07	36.40	78.34	0.18	16.72	10800
车辆工作量平衡最优	193.96	0.49	1.89	27.08	199.09	0.52	3.04	10800

节点服务时间/min	P/元	S	B/min
1	58.84	0.11	5.37
2	79.34	0.18	6.06
3	124.74	0.31	6.42

时间分级范围/min	P/元	S	B/min
[30,40,50]	151.91	0.37	7.32
[40,50,60]	79.34	0.18	6.06
[50,60,70]	60.44	0.11	5.84

超时惩罚成本/元	P/元	S	B/min
[1,4,7]	58.60	0.20	6.56
[3,6,9]	79.34	0.18	6.06
[5,8,11]	102.65	0.16	5.54

算例	NSGA-II					多目标蚁群算法					VNS-NSGA-II
算例	P/元	S	B/min	HV	T/s	P/元	S	B/min	HV	T/s	P/元	S	B/min	HV	T/s
A4r20o	50.12	0.26	6.73	262.86	43.74	48.79	0.22	6.44	283.26	32.15	45.33	0.19	5.27	330.12	54.57
B4r20o	42.76	0.19	4.85	429.85	48.60	44.32	0.22	4.68	316.42	35.64	41.77	0.19	4.13	434.38	62.11
A8r40o	91.96	0.22	8.67	554.78	77.38	87.79	0.21	6.06	668.70	121.33	79.34	0.18	6.16	696.81	89.69
B8r40o	94.64	0.21	10.99	573.73	75.12	90.90	0.21	7.58	639.96	119.70	83.41	0.19	6.26	782.53	91.15
A16r80o	246.20	0.29	8.38	432.94	96.50	235.19	0.28	7.62	529.13	453.52	219.77	0.25	6.76	561.52	117.62
B16r80o	247.80	0.28	8.06	235.63	91.34	229.09	0.28	8.97	289.34	470.17	227.43	0.26	6.56	433.68	114.81

算例	VNS-NSGA-II			NSGA-II-RAND			NSGA-II-RB
算例	P/元	S	B/min	P/元	S	B/min	P/元	S	B/min
A4r20o	45.33	0.19	5.27	44.48	0.20	7.88	48.32	0.21	5.02
B4r20o	41.77	0.19	4.13	41.90	0.18	4.45	45.18	0.19	3.43
A8r40o	79.34	0.18	6.06	78.13	0.18	7.13	80.22	0.19	5.12
B8r40o	83.41	0.19	6.26	80.07	0.19	7.84	90.04	0.22	6.88
A16r80o	219.77	0.25	6.76	218.10	0.25	7.23	226.68	0.25	6.54
B16r80o	227.43	0.26	6.56	224.87	0.25	7.80	233.07	0.26	6.12

[1]	Qi SONG, Zhenyu HUANG, Huanyu LI, Anxin GUO, Rennong YANG. Modeling and simulation study of “agile combat employment” base construction [J]. Systems Engineering and Electronics, 2026, 48(1): 218-234.
[2]	Kaiqiang TANG, Huiqiao FU, Jiasheng LIU, Guizhou DENG, Chunlin CHEN. Hierarchical optimization research of constrained vehicle routing based on deep reinforcement learning [J]. Systems Engineering and Electronics, 2025, 47(3): 827-841.
[3]	Dawang WANG, Zhifeng LU, Guohua WU. Research on resource scheduling of fire control radar networking based on adaptive variable neighborhood search [J]. Systems Engineering and Electronics, 2025, 47(2): 496-507.
[4]	Xiaolong DIAO, Houming FAN, Yang LI, Zimu BIAN, Shuo WEI, Binghao ZHANG. Two-echelon unmanned vehicles collaborative delivery routing optimization in closed and open scenes [J]. Systems Engineering and Electronics, 2025, 47(12): 3952-3965.
[5]	Qin LEI, Yanbing GAO, Yufeng ZHOU, Zhibin WU. Multi-delivery option path planning based on improved ALNS algorithm [J]. Systems Engineering and Electronics, 2025, 47(1): 173-181.
[6]	Tao HONG, Fan WANG, Zhi LI, Zhiwei ZHONG, Xiaojin DING, Ziwei LIU, Gengxin ZHANG. Business-driven terminal mode switching method for low Earth orbit satellite-based Internet of Things [J]. Systems Engineering and Electronics, 2024, 46(8): 2867-2876.
[7]	Qiangqiang XU, Hua CHAI. Optimization of task dispatch plan for vehicular optical observation equipment based on NSGA-Ⅱ [J]. Systems Engineering and Electronics, 2024, 46(7): 2393-2400.
[8]	Hao CHEN, Gang SUN, Shuang PENG, Jiangjiang WU. Dynamic rescheduling method for TT&C and data transmission resources based on multi-objective optimization [J]. Systems Engineering and Electronics, 2024, 46(11): 3744-3753.
[9]	Zelun GAO, Shaoqiu ZHENG, Rupeng LIANG, Yanyan HUANG. Model of strike target preference under super-network system operation [J]. Systems Engineering and Electronics, 2024, 46(1): 182-189.
[10]	Liyao WANG, Jin ZHANG, Hongxi ZHOU, Kemao WANG. Planning of multi-station accessing multi-satellite based on physical planning [J]. Systems Engineering and Electronics, 2023, 45(8): 2514-2520.
[11]	Hongzhou ZHAI, Hua ZHANG, Linna WU, Hequn BU, Kaixiang GONG. Optimization algorithm for reliability redundancy design based on collaborative balance [J]. Systems Engineering and Electronics, 2023, 45(12): 4084-4089.
[12]	Shiying YAN, Kefei YAN, Wei FANG, Hengyang LU. Large-scale multi-objective algorithm based on neighborhood adaptive of differential evolution [J]. Systems Engineering and Electronics, 2022, 44(7): 2112-2124.
[13]	Qian LIU, Yunjun LU, Kebin CHEN, Mengyao HAN, Liang GUO. Combat task decomposition EVA method based on binary constraints of task subject [J]. Systems Engineering and Electronics, 2022, 44(7): 2201-2210.
[14]	Rongwei CUI, Wei HAN, Xichao SU, Liguo WANG, Yujie LIU. Integrated optimization of carrier-based aircraft flight deck operations scheduling and resource configuration for pre-flight preparation stage [J]. Systems Engineering and Electronics, 2021, 43(7): 1884-1893.
[15]	Boyuan XIA, Kewei YANG, Zhiwei YANG, Xiaoke ZHANG, Danling ZHAO. Multi-objective optimization of equipment portfolio based on kill-web evaluation [J]. Systems Engineering and Electronics, 2021, 43(2): 399-409.