A Multi-Task Evolutionary Algorithm for Multi-Objective Vehicle Routing Problems

LU Yuming; CAO Longhao; GUO Xin; AI Yihao; CHEN Hao; JIE Lilin

doi:10.12263/DZXB.20250777

您当前的位置：

首页 >

文章列表页 >

A Multi-Task Evolutionary Algorithm for Multi-Objective Vehicle Routing Problems

PAPERS | 更新时间：2026-06-04

- A Multi-Task Evolutionary Algorithm for Multi-Objective Vehicle Routing Problems
- ACTA ELECTRONICA SINICA Vol. 54, Issue 1, Pages: 352-367(2026)
- 作者机构：
  
  1.南昌航空大学航空制造与机械工程学院，江西南昌 330063
  2.北京安期生技术有限公司，北京 101399
  3.南昌航空大学信息工程学院，江西南昌 330063
  4.南昌航空大学仪器科学与光电工程学院，江西南昌 330063
  5.珠海京东方晶芯科技有限公司，广东珠海 519055
- 作者简介：
- 基金信息：
  
  National Natural Science Foundation of China(62473188);Natural Science Foundation of Jiangxi Province(20242BAB25094);Science and Technology Project of the Education Department of Jiangxi Province(GJJ2401009)
- DOI：10.12263/DZXB.20250777
  CLC： TP301;TP399
- Received：05 September 2025，
  
  Accepted：26 December 2025，
  
  Published：25 January 2026
- 稿件说明：
移动端阅览
鲁宇明, 曹龙昊, 郭鑫, 等. 面向多目标车辆路径规划问题的进化多任务算法[J]. 电子学报, 2026, 54(01): 352-367.

LU Yuming, CAO Longhao, GUO Xin, et al. A Multi-Task Evolutionary Algorithm for Multi-Objective Vehicle Routing Problems[J]. Acta Electronica Sinica, 2026, 54(01): 352-367.
鲁宇明, 曹龙昊, 郭鑫, 等. 面向多目标车辆路径规划问题的进化多任务算法[J]. 电子学报, 2026, 54(01): 352-367. DOI：10.12263/DZXB.20250777

LU Yuming, CAO Longhao, GUO Xin, et al. A Multi-Task Evolutionary Algorithm for Multi-Objective Vehicle Routing Problems[J]. Acta Electronica Sinica, 2026, 54(01): 352-367. DOI：10.12263/DZXB.20250777

摘要

多目标车辆路径规划问题（Multi-Objective Vehicle Routing Problem，MOVRP）是物流配送与运输领域的一个关键优化问题，直接关联物流运营效率、成本控制与客户服务质量，该问题广泛应用于城市配送、电商物流及应急物资运输等实际场景。随着物流系统规模的不断扩大及运行环境的动态化发展，MOVRP所涉及的约束条件和优化目标数量持续增加，问题结构日趋复杂，在求解效率、解集质量以及鲁棒性等方面对优化算法提出了更高要求。现有多目标优化算法在求解MOVRP时普遍采用单任务独立求解范式，即针对每个新的MOVRP问题均从零开始构建求解模型，这种求解方式忽略了不同问题实例或问题子结构之间潜在的相似性，未能有效利用历史搜索过程中积累的有用信息，从而造成重复搜索、收敛速度较慢，且在复杂场景下容易陷入局部最优，从而导致算法求解效果不佳。为应对这一挑战，本文提出一种多目标车辆路径进化多任务算法（Multi-Objective vehicle routing MultiTasking Evolutionary Algorithm，MO-MTEA）。首先，将原问题通过降维的方式拆分成若干个简单且相似的子任务，通过子任务的分层求解简化原问题的复杂度，该策略在保持原问题关键约束关系的前提下，有效降低了单个子任务的搜索空间规模，从而减轻算法的搜索负担，提高求解效率。其次，基于进化多任务（Evolutionary MultiTasking，EMT）技术，通过引入知识迁移机制，将各子任务在搜索过程中获得的有效信息在不同任务之间进行共享与传递，实现子任务之间的协同进化。该多任务协同机制能够充分挖掘不同子任务之间的潜在关联性，有效增强算法的全局搜索能力和收敛性能。最后，在主种群进化的同时，引入独立的存档种群，通过精英保留策略将主种群中的精英个体保存到存档种群中，在保证优秀解不丢失的同时，维持种群多样性和分布均匀性，防止主种群陷入局部最优。为验证该算法的性能，将所提出算法在经典Solomon测试数据集上进行测试，并与蚁群禁忌算法（Ant Colony Optimization-Tabu search，ACO-Tabu）、基于分解的多目标模因算法（Decomposition based Memetic Algorithm for Multi-Objective Evolutionary Algorithm，M-MOEA/D）、混合多目标模因算法（Hybrid MultiObjective Memetic Algorithm，HMOMA）和共同进化的约束优化（Coevolutionary framework for Constrained Multiobjective Optimization，CCMO）四种代表性的多目标进化算法进行比较。实验结果表明，MO-MTEA性能优于其他进化算法，能够更好地求解MOVRP。

Abstract

Multi-objective vehicle routing problem is a key optimization problem in the field of logistics distribution and transportation. It is directly impact to logistics operational efficiency

cost control and customer service quality. This problem has widely exist in practical scenarios such as e-commerce warehousing and distribution

urban cold chain transportation and emergency material scheduling

As logistics systems expand in scale and operating environments become increasingly dynamic

the number of constraints and optimisation objectives involved in MOVRP continues to grow

rendering the problem structure progressively more complex. This places heightened demands on optimisation algorithms regarding computational efficiency

solution quality

and robustness. Existing optimization algorithms employs a single-task independent solution approach

where each new problem is processed from scratch. where a solution model is built and the search process is initialized from scratch for each new MOVRP problem. This method fails to effectively utilise useful information accumulated during historical searches. Consequently

it leads to redundant searches

slower convergence speeds

and a tendency to become trapped in local optima in complex scenarios. This results in suboptimal algorithmic performance.To overcome the above-mentioned deficiencies

a multi-objective vehicle routing multi-task evolutionary algorithm is proposed in this paper. Firstly

the original problem is divided into several simple and similar sub-tasks by dimensional reduction

which is used to simplify the complexity of the original problem through hierarchical solution of sub-tasks. While preserving the key constraints of the original problem

this strategy effectively reduces the search space scale of individual sub-tasks

thereby alleviating the algorithm’s search burden and enhancing solution efficiency.Then

based on Evolutionary MultiTasking technology

the method of knowledge transfer is adopted to transfer the searched information between sub-tasks to achieve collaborative gain of sub-tasks and assist in the solution of the original task. This multi-task coordination mechanism fully exploits latent correlations between sub-tasks

significantly enhancing the algorithm’s global search capability and convergence performance. Finally

while the main population evolves

an independent archive population is introduced. The elite individuals in the main population are saved into the archive population.This ensures that high-quality solutions are not lost while maintaining population diversity and uniform distribution

effectively preventing the main population from becoming trapped in local optima.To evaluate the performance of the proposed algorithm

it is tested on the classic Solomon test dataset and compared with four mainstream evolutionary algorithms in the field

namely ACO-Tabu

M-MOEA/D

HMOMA and CCMO. Experimental results show that MO-MTEA outperforms other evolutionary algorithms and achieves superior solutions for MOVRP.

关键词

Keywords

references

Pan Lili , Hu Bing , Sun Zhe , et al . A review of the evolutionary algorithm based VRP problem [C ] // Proceedings of 2023 42nd Chinese Control Conference . Piscataway : IEEE , 2023 : 1939 - 1944 . DOI: 10.23919/ccc58697.2023.10241179 http://dx.doi.org/10.23919/ccc58697.2023.10241179

张歆悦 , 靳鹏 , 胡笑旋 , 等 . 时间依赖型多配送中心带时间窗的开放式车辆路径问题研究 [J ] . 中国管理科学 , 2024 , 32 ( 1 ): 146 - 157 .

Zhang Xinyue , Jin Peng , Hu Xiaoxuan , et al . Research on the time-dependent multi-depot open vehicle routing problem with time windows [J ] . Chinese Journal of Management Science , 2024 , 32 ( 1 ): 146 - 157 . (in Chinese)

蒋华伟 , 郭陶 , 杨震 . 车辆路径问题研究进展 [J ] . 电子学报 , 2022 , 50 ( 2 ): 480 - 492 .

Jiang Huawei , Guo Tao , Yang Zhen . Research progress of vehicle routing problem [J ] . Acta Electronica Sinica , 2022 , 50 ( 2 ): 480 - 492 . (in Chinese)

刘东升 , 王俊生 . 非结构化环境中基于拓扑约束的地面无人驾驶路径规划算法 [J ] . 控制与决策 , 2022 , 37 ( 12 ): 3103 - 3114 .

Liu Dongsheng , Wang Junsheng . Path planning algorithm for ground unmanned vehicles based on topological constraints in unstructured environments [J ] . Control and Decision , 2022 , 37 ( 12 ): 3103 - 3114 . (in Chinese)

Ren Teng , Xu Hongbo , Jin Kangning , 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 http://dx.doi.org/10.1016/j.cie.2021.107728

Dabia S , Ropke S , van Woensel T , et al . Branch and price for the time-dependent vehicle routing problem with time windows [J ] . Transportation Science , 2013 , 47 ( 3 ): 380 - 396 . DOI: 10.1287/trsc.1120.0445 http://dx.doi.org/10.1287/trsc.1120.0445

Azi N , Gendreau M , Potvin J Y . An exact algorithm for a single-vehicle routing problem with time windows and multiple routes [J ] . European Journal of Operational Research , 2007 , 178 ( 3 ): 755 - 766 . DOI: 10.1016/j.ejor.2006.02.019 http://dx.doi.org/10.1016/j.ejor.2006.02.019

沈俊杰 , 彭江 , 郭坤银 , 等 . 车联网中基于位置信息映射和相关性评估的进化多任务优化算法 [J ] . 电子学报 , 2025 , 53 ( 5 ): 1661 - 1676 .

Shen Junjie , Peng Jiang , Guo Kunyin , et al . Location mapping and correlation assessment based evolutionary multi-task optimization algorithm in the Internet of vehicles [J ] . Acta Electronica Sinica , 2025 , 53 ( 5 ): 1661 - 1676 . (in Chinese)

陈凯 , 龚毅光 . 混合多目标灰狼算法求解多目标VRPTW问题 [J ] . 计算机工程与应用 , 2024 , 60 ( 11 ): 309 - 318 .

Chen Kai , Gong Yiguang . Hybrid multiple-objective grey wolf algorithm solving multi-objective vehicle routing problem with time windows [J ] . Computer Engineering and Applications , 2024 , 60 ( 11 ): 309 - 318 . (in Chinese)

王旭健 , 张峰干 , 姚敏立 . 基于动态分解和角度惩罚距离的高维多目标进化算法 [J ] . 电子学报 , 2024 , 52 ( 8 ): 2773 - 2785 .

Wang Xujian , Zhang Fenggan , Yao Minli . Many-objective evolutionary algorithm based on dynamic decomposition and angle penalty distance [J ] . Acta Electronica Sinica , 2024 , 52 ( 8 ): 2773 - 2785 . (in Chinese)

Gupta A , Ong Y S , Feng Liang . Multifactorial evolution: Toward evolutionary multitasking [J ] . IEEE Transactions on Evolutionary Computation , 2016 , 20 ( 3 ): 343 - 357 . DOI: 10.1109/tevc.2015.2458037 http://dx.doi.org/10.1109/tevc.2015.2458037

Feng Liang , Zhou Lei , Gupta A , et al . Solving generalized vehicle routing problem with occasional drivers via evolutionary multitasking [J ] . IEEE Transactions on Cybernetics , 2021 , 51 ( 6 ): 3171 - 3184 . DOI: 10.1109/tcyb.2019.2955599 http://dx.doi.org/10.1109/tcyb.2019.2955599

Wang Jiahai , Ren Wenbin , Zhang Zizhen , et al . A hybrid multiobjective memetic algorithm for multiobjective periodic vehicle routing problem with time windows [J ] . IEEE Transactions on Systems, Man, and Cybernetics: Systems , 2020 , 50 ( 11 ): 4732 - 4745 . DOI: 10.1109/tsmc.2018.2861879 http://dx.doi.org/10.1109/tsmc.2018.2861879

Feng Liang , Huang Yuxiao , Zhou Lei , et al . Explicit evolutionary multitasking for combinatorial optimization: A case study on capacitated vehicle routing problem [J ] . IEEE Transactions on Cybernetics , 2021 , 51 ( 6 ): 3143 - 3156 . DOI: 10.1109/tcyb.2019.2962865 http://dx.doi.org/10.1109/tcyb.2019.2962865

Ding Xuefeng , Liu Tingting . A history information-guided evolutionary algorithm for the multiobjective vehicle routing problem with time windows [J ] . IEEE Sensors Journal , 2024 , 24 ( 21 ): 35787 - 35800 . DOI: 10.1109/jsen.2024.3458899 http://dx.doi.org/10.1109/jsen.2024.3458899

Qiao Kangjia , Liang Jing , Yu Kunjie , et al . A self-adaptive evolutionary multi-task based constrained multi-objective evolutionary algorithm [J ] . IEEE Transactions on Emerging Topics in Computational Intelligence , 2023 , 7 ( 4 ): 1098 - 1112 . DOI: 10.1109/tetci.2023.3236633 http://dx.doi.org/10.1109/tetci.2023.3236633

李坚强 , 蔡俊创 , 孙涛 , 等 . 面向复杂物流配送场景的车辆路径规划多任务辅助进化算法 [J ] . 自动化学报 , 2024 , 50 ( 3 ): 544 - 559 . DOI: 10.1109/tase.2023.3326315 http://dx.doi.org/10.1109/tase.2023.3326315

Li Jianqiang , Cai Junchuang , Sun Tao , et al . Multitask-based assisted evolutionary algorithm for vehicle routing problems in complex logistics distribution scenarios [J ] . Acta Automatica Sinica , 2024 , 50 ( 3 ): 544 - 559 . (in Chinese) . DOI: 10.1109/tase.2023.3326315 http://dx.doi.org/10.1109/tase.2023.3326315

郭庆辉 , 李媛 , 杨东升 . 一种改进麻雀搜索算法的收敛性分析及应用 [J ] . 控制与决策 , 2024 , 39 ( 8 ): 2502 - 2510 .

Guo Qinghui , Li Yuan , Yang Dongsheng . Convergence analysis and application of an improved sparrow search algorithm [J ] . Control and Decision , 2024 , 39 ( 8 ): 2502 - 2510 . (in Chinese)

Mirabi M . A novel hybrid genetic algorithm for the multidepot periodic vehicle routing problem [J ] . Artificial Intelligence for Engineering Design, Analysis and Manufacturing , 2015 , 29 ( 1 ): 45 - 54 . DOI: 10.1017/s0890060414000328 http://dx.doi.org/10.1017/s0890060414000328

Thang T B , Long N B , Hoang N V , et al . Adaptive knowledge transfer in multifactorial evolutionary algorithm for the clustered minimum routing cost problem [J ] . Applied Soft Computing , 2021 , 105 : 107253 . DOI: 10.1016/j.asoc.2021.107253 http://dx.doi.org/10.1016/j.asoc.2021.107253

Zhou Zifeng , Ma Xiaoliang , Liang Zhengping , et al . Multi-objective multi-factorial memetic algorithm based on bone route and large neighborhood local search for VRPTW [C ] // Proceedings of 2020 IEEE Congress on Evolutionary Computation . Piscataway : IEEE , 2020 : 9185528 . DOI: 10.1109/cec48606.2020.9185528 http://dx.doi.org/10.1109/cec48606.2020.9185528

Jiang Dengying , Jiang Wenxia , Huang Zhangcan . A hybrid algorithm for vehicle routing problem with time windows [C ] // Proceedings of the 3rd International Symposium on Advances in Computation and Intelligence . Heidelberg : Springer , 2008 : 198 - 205 . DOI: 10.1007/978-3-540-92137-0_22 http://dx.doi.org/10.1007/978-3-540-92137-0_22

Qi Yutao , Hou Zhanting , Li He , et al . A decomposition based memetic algorithm for multi-objective vehicle routing problem with time windows [J ] . Computers & Operations Research , 2015 , 62 : 61 - 77 . DOI: 10.1016/j.cor.2015.04.009 http://dx.doi.org/10.1016/j.cor.2015.04.009

Tian Ye , Zhang Tao , Xiao Jianhua , et al . A coevolutionary framework for constrained multiobjective optimization problems [J ] . IEEE Transactions on Evolutionary Computation , 2021 , 25 ( 1 ): 102 - 116 . DOI: 10.1109/tevc.2020.3004012 http://dx.doi.org/10.1109/tevc.2020.3004012

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Multi-Objective Path Planning Algorithm for WRSN with Time Window

Research on Recombination Operator and Multi-Objective Optimization Based on Fitness Guided Mating Restriction Strategy

Research on Reproduction Operator and Multi-objective Optimization Based on Multi-source Mating Selection Strategy

A Multi-Objective Memetic Optimization Algorithm Based on Ecological Population Preying-Competition Model

Attention Penalty and Adaptive Learning Scene Graph for Joint Multimodal Aspect-Based Sentiment Analysis

Related Author

CAO Longhao

WEI Zhen-chun

FU Yu

MA Zhong-jun

LYU Zeng-wei

SHI Lei

ZHANG Ben-hong

WANG Yu-hong

Related Institution

ZhuhaiBOE MLED Technology Co.,Ltd. Guangdong

Anhui Province Key Laboratory of Industry Safety and Emergency Technology

School of Computer and Information, Hefei University of Technology

Engineering Research Center of Safety Critical Industrial Measurement and Control Technology,Ministry of Education

School of Mechanical Engineering and Rail Transit , Changzhou University

⁰