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

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

摘要/Abstract

摘要：

针对取送货车辆路径规划中车辆工作量平衡问题，建立以物流平台配送成本最小、客户满意度最大以及车辆工作量平衡的多目标订单分配与路径规划联合优化模型。针对问题特点，设计了一个基于非支配排序遗传算法II(non-dominated sorting genetic algorithm II, NSGA-II)框架的启发式求解算法，并结合路径内节点重定位算子、订单重定位算子，路径间订单交换算子、订单重定位算子以及路径平衡算子增大搜索空间，提高算法搜索能力，寻找高质量解。最后，通过算例实验说明模型和算法有效性。实验结果表明，构建的模型和提出的算法能够在多个目标之间取得平衡，车辆工作量平衡程度的提高并不会明显增大平台配送成本或者是降低客户满意度。同时，和NSGA-II以及多目标蚁群算法相比，所提基于变邻域搜索的NSGA-II具有较好寻优能力。

关键词: 城市物流, 取送货, 车辆路径问题, 多目标优化, 变邻域搜索, 工作量平衡

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

中图分类号:

谢雨思, 雷勤, 吴志彬. 考虑工作量平衡的多目标取送货路径规划[J]. 系统工程与电子技术, 2026, 48(4): 1254-1263.

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.

图/表 22

图1

表1

表2

图2

图3

图4

图5

图6

图7

图8

图9

表3

表4

表5

表6

表7

表8

表9

表10

图10

表11

表12

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