动态任务构建的多任务算法求解MOVRPTW问题

doi:10.19665/j.issn1001-2400.20250307

摘要/Abstract

摘要：

带时间窗的多目标车辆路径问题(MOVRPTW)是一个重要且具有挑战性的物流问题。进化多任务算法(EMT)是一种通过任务间知识迁移提升算法寻优能力的新颖方法。文中提出一种动态构造辅助任务的方法,旨在增强任务间的知识迁移效果,从而提高原始任务的寻优能力。文中采用动态更换辅助任务的思想改进多任务优化算法求解MOVRPTW问题,期望算法在任务间能持续提供有效的知识迁移。在算法的迭代过程中,当辅助任务不能提供有效迁移时,依据当前原始任务的非劣解的分布信息动态更换辅助任务以探索未搜索的方向,为提供更有效的知识迁移提供可能性。同时设计了从辅助任务到原始任务及原始任务到辅助任务的两种知识迁移方法来提高算法的的寻优能力。通过在大量标准测试算例上的仿真验证表明所提算法能够持续提供有效的知识迁移,显著提高EMT算法的寻优能力,为解决MOVRPTW问题提供了新的有效途径。

关键词: 动态辅助任务, 进化多任务算法, 知识迁移, MOVRPTW问题

Abstract:

The Multi-ObjectiveVehicle Routing Problem with Time Windows (MOVRPTW) is a significant and challenging issue in the field of logistics.The Evolutionary Multi-Task Algorithm (EMT) is a novel approach that enhances the optimization capability of algorithms through knowledge transfer between tasks.This paper proposes a method for dynamically constructing an auxiliary task,aiming to strengthen the effect of knowledge transfer between tasks and thereby improve the optimization capability of the original task.The paper employs the idea of dynamically switching the auxiliary task to enhance the multi-task optimization algorithm for solving the MOVRPTW problem,with the expectation that the algorithm can continuously provide an effective knowledge transfer between tasks.During the iteration process of the algorithm,when the auxiliary task cannot provide an effective transfer,the auxiliary task is dynamically replaced based on the distribution information of the current non-inferior solutions of the original task to explore unexplored directions,offering the possibility for a more effective knowledge transfer.Additionally,two knowledge transfer methods from the auxiliary task to the original task and from the original task to the auxiliary task are designed to enhance the algorithm's optimization capability.Simulation results on a large number of standard test cases demonstrate that the proposed algorithm can continuously provide an effective knowledge transfer,significantly improving the optimization capability of the EMT algorithm,and offering a new effective approach to solving the MOVRPTW problem.

Key words: dynamic auxiliary task, evolutionary multi-task algorithm, knowledge transfer, MOVRPTW problem

中图分类号:

U492.2+2

王宇东, 武燕. 动态任务构建的多任务算法求解MOVRPTW问题[J]. 西安电子科技大学学报, 2025, 52(3): 242-256.

WANG Yudong, WU Yan. Dynamic auxiliary task construction for multi-task algorithm to solve the MOVRPTW problem[J]. Journal of Xidian University, 2025, 52(3): 242-256.

图/表 7

图1

表1

表2

EMT-MODH和对比算法在Solomon测试实例上的比较"

Problems			M-MOEA/D				D-VND				Game-MOGLN				HRRGA				EMT-MODH
Problems			NV		TD		NV		TD		NV		TD		NV		TD		NV		TD
C1	C101		10		828.94		10		828.94		10		828.94		10		828.94		10		827.30
	C102		10		828.94		10		828.94		10		828.94		10		828.94		10		828.94
	C103		10		828.06		10		828.06		10		828.06		10		828.07		10		826.30
	C104		10		824.78		10		824.78		10		824.78		10		824.78		10		823.91
	C105		10		828.94		10		828.94		10		828.94		10		828.94		10		827.30
	C106		10		828.94		10		828.94		10		828.94		10		828.94		10		828.94
	C107		10		828.94		10		828.94		10		828.94		10		828.94		10		827.64
	C108		10		828.94		10		828.94		10		828.94		10		828.94		10		827.64
	C109		10		828.94		10		828.94		10		828.94		10		828.94		10		828.94
C2	C201		3		591.56		3		591.56		3		591.56		3		591.56		3		589.47
	C202		3		591.56		3		591.56		3		591.56		3		591.56		3		589.47
	C203		3		591.17		3		591.17		3		591.17		3		591.17		3		589.70
	C204		3		590.60		3		590.60		3		590.60		3		590.60		3		588.10
	C205		3		588.88		3		588.88		3		588.88		3		588.88		3		586.40
	C206		3		588.49		3		588.49		3		588.49		3		588.49		3		587.56
	C207		3		588.29		3		588.29		3		588.29		3		588.29		3		585.80
	C208		3		588.32		3		588.32		3		588.32		3		588.32		3		585.80
R1	R101		19		1 644.70		19		1 650.80		20		1 654.5		19		1 642.88		18		1 639.8
	R102		17		1 473.73		17		1 486.86		18		1 492.1		17		1 472.82		17		1 459.37
	R103		13		1 213.62		13		1 241.30		14		1 244.3		13		1 213.62		13		1 219.37
	R104		10		991.91		10		1 007.31		11		995.53		10		976.61		9		974.24
	R105		14		1 366.58		14		1 377.11		15		1 382.5		14		1 360.78		14		1 356.42
	R106		12		1 249.22		12		1 252.03		13		1 254.2		12		1 239.37		12		1 241.65
	R107		10		1 086.22		10		1 104.65		11		1 087.2		10		1 072.12		10		1 069.30
	R108		10		965.52		10		960.88		10		963.82		9		938.20		9		949.26
	R109		12		1 155.38		12		1 211.63		13		1 179.3		12		1 151.84		12		1 046.90
	R110		11		1 106.03		11		1 190.84		12		1 108.8		11		1 076.23		10		1 074.82
	R111		11		1 073.82		11		1 102.73		12		1 082.1		10		1 053.5		10		1 050.53
	R112		10		981.43		10		982.14		11		990.8		10		960.03		9		959.17
R2	R201		4		1 185.79		4		1 182.23		4		1 173.10		4		1 147.80		4		1 146.90
	R202		4		1 049.72		4		1 191.70		4		1 078.30		4		1 034.97		3		1 033.70
	R203		3		889.36		3		939.50		3		906.90		3		874.87		3		870.87
	R204		3		743.29		3		825.52		3		785.05		3		735.89		2		731.30
	R205		3		954.48		3		994.43		3		989.49		3		954.16		3		951.16
	R206		3		887.90		3		906.72		3		911.07		3		884.85		3		869.74
	R207		3		809.51		3		890.61		3		818.05		3		797.99		2		797.10
	R208		2		711.59		2		726.82		2		729.21		2		705.33		2		702.50
	R209		3		867.47		3		909.16		3		883.67		3		860.11		3		858.34
	R210		3		920.06		3		939.37		3		944.71		3		905.21		3		909.60
	R211		3		767.10		3		885.71		3		798.92		3		753.15		2		750.90
RC1		RC101		14		1 646.65		15		1 668.95		15		1 653.5		14		1 623.59		14		1 622.65
		RC102		13		1 484.48		13		1 510.75		13		1 489.5		13		1 461.23		12		1 457.40
		RC103		11		1 274.85		11		1 261.67		11		1 291.0		11		1 261.67		11		1 204.12
		RC104		10		1 145.79		10		1 135.48		10		1 136.6		10		1 135.52		10		1 135.48
		RC105		14		1 528.61		13		1 594.15		13		1 581.9		14		1 518.58		13		1 513.70
		RC106		12		1 399.17		12		1 410.73		12		1 403.4		12		1 376.99		11		1 372.70
		RC107		11		1 235.54		11		1 230.48		11		1 256.2		11		1 212.83		11		1 209.30
		RC108		10		1 138.95		11		1 139.82		10		1 130.3		10		1 118.07		10		1 117.53
RC2	RC201		4		1 289.94		4		1 314.35		4		1 311.30		5		1 265.56		4		1 264.70
	RC202		4		1 118.66		4		1 203.62		4		1 162.40		4		1 095.8		3		1 095.40
	RC203		3		940.55		3		966.73		3		959.59		4		926.82		3		937.45
	RC204		3		792.98		3		798.46		3		803.81		3		788.66		3		786.38
	RC205		4		1 187.48		4		1 241.35		4		1 234.10		5		1 157.55		4		1 155.20
	RC206		3		1 089.14		3		1 142.46		3		1 107.80		4		1 054.61		3		1 056.70
	RC207		3		987.88		3		1 061.14		3		1 026.40		4		969.80		3		964.80
	RC208		3		807.83		3		828.14		3		816.59		3		778.93		3		776.10

表2

表3

图2

表4

用HV指标比较EMT-MODH和对比算法在非劣解的表现"

Problems			MOGP
C1	C101	0.250	0.250	0.250	0.250	0.250	0.251
	C102	0.250	0.250	0.250	0.250	0.250	0.250
	C103	0.251	0.251	0.251	0.251	0.251	0.251
	C104	0.253	0.253	0.253	0.253	0.252	0.253
	C105	0.250	0.250	0.250	0.250	0.250	0.251
	C106	0.250	0.250	0.250	0.250	0.250	0.250
	C107	0.250	0.250	0.250	0.250	0.250	0.251
	C108	0.250	0.250	0.250	0.250	0.250	0.251
	C109	0.250	0.250	0.250	0.250	0.250	0.250
C2	C201	0.250	0.250	0.250	0.250	0.250	0.250
	C202	0.250	0.250	0.250	0.250	0.250	0.250
	C203	0.250	0.250	0.250	0.250	0.250	0.250
	C204	0.251	0.251	0.251	0.250	0.253	0.253
	C205	0.252	0.252	0.252	0.252	0.252	0.252
	C206	0.253	0.253	0.253	0.253	0.253	0.253
	C207	0.253	0.253	0.253	0.253	0.254	0.254
	C208	0.253	0.253	0.253	0.253	0.254	0.254
R1	R101	0.541	0.283	0.286	0.277	0.541	0.843
	R102	0.770	0.365	0.403	0.394	0.770	0.775
	R103	1.207	0.596	0.654	0.646	1.241	1.272
	R104	1.765	0.919	0.913	0.908	1.776	2.655
	R105	1.038	0.505	0.549	0.540	1.046	1.057
	R106	1.310	0.631	0.683	0.673	1.314	1.319
	R107	1.628	0.797	0.852	0.848	1.632	1.652
	R108	0.923	0.920	0.973	0.977	1.884	1.905
	R109	1.416	0.702	0.730	0.722	0.744	0.785
	R110	1.550	0.729	0.808	0.807	1.589	2.399
	R111	0.815	0.795	0.824	0.860	1.582	1.597
	R112	0.914	0.852	0.915	0.919	1.874	1.882
R2	R201	1.524	0.458	0.543	0.614	1.932	2.614
	R202	1.310	0.611	0.630	0.718	2.963	3.435
	R203	2.445	0.795	0.857	0.936	3.096	3.130
	R204	2.874	0.871	0.971	1.064	3.951	3.969
	R205	2.292	0.696	0.811	0.867	2.291	2.311
	R206	1.745	0.839	0.864	0.934	2.505	2.537
	R207	1.905	0.864	0.924	1.012	2.910	2.933
	R208	2.272	0.956	1.162	1.198	2.276	3.270
	R209	1.759	0.659	0.878	0.947	2.543	2.566
	R210	2.405	0.840	0.839	0.908	2.401	2.414
	R211	1.976	0.701	0.947	1.049	3.048	3.086
RC1	RC101	0.911	0.306	0.324	0.343	0.645	0.947
	RC102	1.220	0.406	0.452	0.445	1.686	1.707
	RC103	0.630	0.557	0.628	0.620	0.632	1.247
	RC104	0.742	0.675	0.743	0.733	0.740	0.747
	RC105	0.742	0.334	0.397	0.383	1.139	1.468
	RC106	0.992	0.473	0.536	0.523	1.560	1.578
	RC107	1.237	0.654	0.657	0.643	1.251	1.258
	RC108	1.416	0.684	0.752	0.741	1.429	1.447
RC2	RC201	1.997	0.754	0.536	0.595	2.012	2.380
	RC202	1.399	0.474	0.665	0.782	2.489	2.997
	RC203	2.530	0.509	0.886	0.914	2.536	3.272
	RC204	2.090	0.726	1.016	1.123	2.071	2.096
	RC205	1.748	0.936	0.597	0.662	2.222	2.267
	RC206	2.237	0.482	0.792	0.820	2.248	2.816
	RC207	2.448	0.622	0.848	0.882	2.450	3.175
	RC208	2.047	0.721	1.020	0.598	2.951	2.963

表4

图3

参考文献 47

[1]	BELHAIZA S. A Game Theoretic Approach for the Real-Life Multiple-Criterion Vehicle Routing Problem with Multiple Time Windows[J]. IEEE Systems Journal, 2016, 12(2):1251-1262.
[2]	ZHANG K, HE F, ZHANG Z, et al. Multi-Vehicle Routing Problems with Soft Time Windows:A Multi-Agent Reinforcement Learning Approach[J]. Transportation Research Part C:Emerging Technologies, 2020,121:102861.
[3]	MANDZIUK J. New Shades of the Vehicle Routing Problem:Emerging Problem Formulations and Computational Intelligence Solution Methods[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2019, 3(3):230-244.
[4]	DUAN J, HE Z, YEN G. Robust Multi-Objective Optimization for Vehicle Routing Problem with Time Windows[J]. IEEE Transactions on Cybernetics, 2022, 52(8):8300-8314.
[5]	KONSTANTAKOPOUS G D, GAYIALIS S P, KECHAGIAS E P. Vehicle Routing Problem and Related Algorithms for Logistics Distribution:A Literature Review and Classification[J]. Operational Research, 2022, 22(3):2033-2062.
[6]	GAUVIN C, DESAULNIERS G, GENDREAU M. A Branch-Cut-and-Price Algorithm for the Vehicle Routing Problem with Stochastic Demands[J]. Computational Operations Research, 2014, 50(1):141-153.
[7]	KOK A.L, MEYER C M, KOPFER H, et al. A Dynamic Programming Heuristic for the Vehicle Routing Problem with Time Windows and European Community Social Legislation[J]. Transportation Science, 2010, 44(4):442-454.
[8]	宋俊福, 徐炳辉, 张岩, 等. 基于改进自适应遗传算法的机器人路径规划[J]. 信息技术, 2022, 46(11):49-53.
	SONG Junfu, XU Binghui, ZHANG Yan, et al. Robot Path Planning Based on Improved Adaptive Genetic Algorithm[J]. Information Technology, 2022, 46(11):49-53.
[9]	SHI K, WU Z, JIANG B, et al. Dynamic Path Planning of Mobile Robot Based on Improved Simulated Annealing Algorithm[J]. Journal of the Franklin Institute, 2023, 360(6):4378-4398.
[10]	白波, 陈继洋, 周宁. 改进PSO算法整定PID控制参数的路径优化控制[J]. 系统仿真技术, 2023, 19(3):253-258.
	BAI Bo, CHEN Jiyang, ZHOU Ning. Path Optimization Control Based on Improved PSO Algorithm for Tuning PID Control Parameters[J]. System Simulation Technology, 2023, 19(3):253-258.
[11]	EYDI A, GHASEMI N. A Bi-Objective Vehicle Routing Problem with Time Windows and Multiple Demands[J]. Ain Shams Engineering Journal, 2021, 12(3):2617-2630.
[12]	TANG K, LIU S, YANG P, et al. Few-Shots Parallel Algorithm Portfolio Construction via Co-Evolution[J]. IEEE Transactions on Evolutionary Computation, 2021, 25(3):595-607.
[13]	LIU S, TANG K, YAO X. Memetic Search for Vehicle Routing with Simultaneous Pickup-Delivery and Time Windows[J]. Swarm and Evolutionary Computation, 2021, 66(1):100927.
[14]	YASSEN E T, AYOB M, AHMAD NAZRI M Z, et al. An Adaptive Hybrid Algorithm for Vehicle Routing Problems with Time Windows[J]. Computers & Industrial Engineering, 2017, 113(1):382-391.
[15]	邬思威. 面向车辆路径问题的邻域搜索驱动的遗传算法研究[D]. 南昌: 南昌大学, 2024.
[16]	MORADI B. The New Optimization Algorithm for the Vehicle Routing Problem with Time Windows Using Multi-Objective Discrete Learnable Evolution Model[J]. Soft Computing, 2020, 24(9):6741-6769.
[17]	高卫峰, 王琼, 李宏, 等. 无人机集群任务分配的多目标算法研究[J]. 西安电子科技大学学报, 2024, 51 (2):1-12.
	GAO Weifeng, WANG Qiong, LI Hong, et al. Research on Multi-Objective Algorithm for Task Assignment of UAV Swarms[J]. Journal of Xidian University, 2024, 51 (2):1-12.
[18]	TAN F, CHAI Z Y, LI Y L. Multi-Objective Evolutionary Algorithm for Vehicle Routing Problem with Time Window under Uncertainty[J]. Evolutionary Intelligence, 2023, 16(2):493-508.
[19]	QI Y, HOU Z, LI H, et al. A Decomposition Based Memetic Algorithm for Multi-Objective Vehicle Routing Problem with Time Windows[J]. Computers & Operations Research, 2015, 62(1):61-77.
[20]	QI R, LI J Q, WANG J, et al. QMOEA:A Q-Learning-Based Multi-Objective Evolutionary Algorithm for Solving Time-Dependent Green Vehicle Routing Problems with Time Windows[J]. Information Sciences, 2022, 608(1):178-201.
[21]	LAN Y L, LIU F, NG W W, et al. Decomposition Based Multi-Objective Variable Neighborhood Descent Algorithm for Logistics Dispatching[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2020, 5(5):826-839.
[22]	GUPTA A, ONG Y S, FENG L. Multifactorial Evolution:Toward Evolutionary Multitasking[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(3):343-357.
[23]	BALI K K, ONG Y S, GUPTA A, et al. Multifactorial Evolutionary Algorithm with Online Transfer Parameter Estimation:Mfeaii[J]. IEEE Transactions on Evolutionary Computation, 2019, 24(1):69-83.
[24]	HAO X, QU R, LIU J, et al. A Unified Framework of Graph-Based Evolutionary Multitasking Hyper-Heuristic[J]. IEEE Transactions on Evolutionary Computation, 2020, 24(3):469-483.
[25]	ONG Y S, GUPTA A. Evolutionary Multitasking:A Computer Science View of Cognitive Multitasking[J]. Cognitive Computation, 2016, 8(2):125-142.
[26]	TANG J, CHEN Y, DENG Z, et al. A Group-Based Approach to Improve Multifactorial Evolutionary Algorithm[C]// Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence(IJCAI 2018). Sweden:IJCAI,2018:3870-3876.
[27]	GUPTA A, ONG Y S, FENG L, et al. Multi-Objective Multifactorial Optimization in Evolutionary Multitasking[J]. IEEE Transactions on Cybernetics, 2017, 47(7):1652-1665.
[28]	DING J, YANG C Y, JIN Y, et al. Generalized Multitasking for Evolutionary Optimization of Expensive Problems[J]. IEEE Transactions on Evolutionary Computation, 2019, 23(1):44-58.
[29]	BALI K K, GUPTA A, FENG L, et al. Linearized Domain Adaptation in Evolutionary Multitasking[C]// Proceedings of the IEEE Congress on Evolutionary Computation (CEC). Piscataway:IEEE,2017:1295-1302.
[30]	ZHONG J H, FENG L, CAI W T, et al. Multifactorial Genetic Programming for Symbolic Regression Problems[J]. IEEE Transactions on Systems,Man,and Cybernetics:Systems, 2019, 50(11):1-14.
[31]	FENG L, ZHOU L, ZHONG J, et al. Evolutionary Multitasking via Explicit Autoencoding[J]. IEEE Transactions on Cybernetics, 2019, 49(9):3457-3470. doi: 10.1109/TCYB.2018.2845361 pmid: 29994415
[32]	GUPTA A, ONG Y S, FENG L. Insights on Transfer Optimization:Because Experience Is the Best Teacher[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2017, 2(1):51-64.
[33]	BALI K K, GUPTA A, ONG Y S, et al. Cognizant Multitasking in Multiobjective Multifactorial Evolution:Mo-mfea-ii[J]. IEEE Transactions on Cybernetics, 2020, 51(4):1784-1796.
[34]	DA B, GUPTA A, ONG Y S, et al. Evolutionary Multitasking Across Single and Multi-Objective Formulations for Improved Problem Solving[C]// Proceedings of the IEEE Congress on Evolutionary Computation. Piscataway:IEEE,2016:1695-1701.
[35]	SHANG Q, HUANG Y, WANG Y, et al. Solving Vehicle Routing Problem by Memetic Search with Evolutionary Multitasking[J]. Memetic Computing, 2022, 14(1):31-44.
[36]	CAI Y, CHENG M, ZHOU Y, et al. A Hybrid Evolutionary Multitask Algorithm for the Multi-Objective Vehicle Routing Problem with Time Windows[J]. Information Sciences, 2022, 612(5):168-187.
[37]	CAI Y, LIN Z, CHENG M, et al. Solving Multi-Objective Vehicle Routing Problems with Time Windows:A Decomposition-Based Multiform Optimization Approach[J]. Tsinghua Science and Technology, 2024, 29(2):305-324.
[38]	QIAO K J, LIANG J, LIU Z Y, et al. Evolutionary Multitasking with Global and Local Auxiliary Tasks for Constrained Multi-Objective Optimization[J]. Acta Automatica Sinica (English Edition), 2023, 10(10):1951-1964.
[39]	YE Q, LIAN Q, et al. Dynamic-Multi-Task-Assisted Evolutionary Algorithm for Constrained Multi-Objective Optimization[J]. Swarm and Evolutionary Computation, 2024, 90(1):101683.
[40]	PRINS C. A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem[J]. Computers and Operations Research, 2004, 31(12):1985-2002.
[41]	ZHOU Y, WANG J. A Local Search-Based Multiobjective Optimization Algorithm for Multiobjective Vehicle Routing Problem with Time Windows[J]. IEEE Systems Journal, 2015, 9(3):1100-1113.
[42]	SOLOMON M M. Algorithmsfor Vehicle Routing and Scheduling Problem with Time Window Constraints[J]. Operations Research, 1987, 35(2):254-265.
[43]	GHANNADPOUR S F, ZANDIYEH F. A New Game-Theoretical Multi-Objective Evolutionary Approach for Cash-in-Transit Vehicle Routing Problem with Time Windows (A Real Life Case)[J]. Applied Soft Computing, 2020, 93(1):106378.
[44]	KHOO T S, BABRDEL BONAB M. The Parallelization of A Two-Phase Distributed Hybrid Ruin-and-Recreate Genetic Algorithm for Solving Multi-Objective Vehicle Routing Problem with Time Windows[J]. Expert Systems with Applications, 2021, 168(1):114408.
[45]	ZITZLER E, THIELE L. Multiobjective Optimization Using Evolutionary Algorithms—A Comparative Case Study[C]// Proceedings of the 5th International Conference on Evolutionary Multi-Criterion Optimization. Heidelberg:Springer,1998:292-302.
[46]	GHOSEIRI K, GHANNADPOUR S F. Multi-Objective Vehicle Routing Problem with Time Windows Using Goal Programming and Genetic Algorithm[J]. Applied Soft Computing, 2010, 10(3):1096-1107.
[47]	GARCÍA-NÁJERAA. Multi-Objective Evolutionary Algorithms for Vehicle Routing Problems[D]. UK: The University of Birmingham, 2010.

参数	说明	设置值
L	独立运行次数	30
N	种群大小	200
m	辅助任务数量	18
Max_evals	最大评估次数	50 000
T	每个个体的邻域	10
ρ_c	交叉概率	0.8
ρ_m	变异概率	0.2