2.765

2022影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

面向复杂物流配送场景的车辆路径规划多任务辅助进化算法

李坚强 蔡俊创 孙涛 朱庆灵 林秋镇

李坚强, 蔡俊创, 孙涛, 朱庆灵, 林秋镇. 面向复杂物流配送场景的车辆路径规划多任务辅助进化算法. 自动化学报, 2024, 50(3): 544−559 doi: 10.16383/j.aas.c230043
引用本文: 李坚强, 蔡俊创, 孙涛, 朱庆灵, 林秋镇. 面向复杂物流配送场景的车辆路径规划多任务辅助进化算法. 自动化学报, 2024, 50(3): 544−559 doi: 10.16383/j.aas.c230043
Li Jian-Qiang, Cai Jun-Chuang, Sun Tao, Zhu Qing-Ling, Lin Qiu-Zhen. Multitask-based assisted evolutionary algorithm for vehicle routing problems incomplex logistics distribution scenarios. Acta Automatica Sinica, 2024, 50(3): 544−559 doi: 10.16383/j.aas.c230043
Citation: Li Jian-Qiang, Cai Jun-Chuang, Sun Tao, Zhu Qing-Ling, Lin Qiu-Zhen. Multitask-based assisted evolutionary algorithm for vehicle routing problems incomplex logistics distribution scenarios. Acta Automatica Sinica, 2024, 50(3): 544−559 doi: 10.16383/j.aas.c230043

面向复杂物流配送场景的车辆路径规划多任务辅助进化算法

doi: 10.16383/j.aas.c230043
基金项目: 国家自然科学基金 (62325307, 62073225, 62203134, 62376163, 62203308),广东省自然科学基金 (2023B1515120038, 2019B151502018), 深圳市科技计划项目(20220809141216003), 深圳大学科学仪器开发项目 (2023YQ019) 资助
详细信息
    作者简介:

    李坚强:深圳大学计算机与软件学院教授. 2008年获华南理工大学博士学位. 主要研究方向为嵌入式系统和物联网. E-mail: lijq@szu.edu.cn

    蔡俊创:深圳大学计算机与软件学院博士研究生. 主要研究方向为进化计算及其在物流领域中的应用. E-mail: caijunchuang2020@email.szu.edu.cn

    孙涛:中兴通讯股份有限公司工程师. 2022年获深圳大学硕士学位. 主要研究方向为进化计算和路径规划. E-mail: 1910272020@email.szu.edu.cn

    朱庆灵:深圳大学计算机与软件学院博士后. 2021年获香港城市大学博士学位. 主要研究方向为进化多目标优化和机器学习. E-mail: zhuqingling@szu.edu.cn

    林秋镇:深圳大学计算机与软件学院副教授. 2014年获香港城市大学博士学位. 主要研究方向为人工免疫系统,多目标优化和动态系统. 本文通信作者. E-mail: qiuzhlin@szu.edu.cn

Multitask-based Assisted Evolutionary Algorithm for Vehicle Routing Problems inComplex Logistics Distribution Scenarios

Funds: Supported by National Natural Science Foundation of China(62325307, 62073225, 62203134, 62376163, 62203308), Natural ScienceFoundation of Guangdong Province (2023B1515120038, 2019B151502018), Shenzhen Science and Technology Program (20220809141216003), and the Scientific Instrument Developing Project of Shenzhen University (2023YQ019)
More Information
    Author Bio:

    LI Jian-Qiang Professor at the College of Computer Science and Software Engineering, Shenzhen University. He received his Ph.D. degree from South China University of Technology in 2008. His research interest covers embedded systems and internet of things

    CAI Jun-Chuang Ph.D. candidate at the College of Computer Science and Software Engineering, Shenzhen University. His research interest covers evolutionary computation and its applications in the field of logistics

    SUN Tao Engineer at ZTE Corporation. He received his master degree from Shenzhen University in 2022. His research interest covers evolutionary computation and path planning

    ZHU Qing-Ling Postdoctor at the College of Computer Science and Software Engineering, Shenzhen University. He received his Ph.D. degree from the City University of Hong Kong in 2021. His research interest covers evolutionary multiobjective optimization and machine learning

    LIN Qiu-Zhen Associate professor at the College of Computer Science and Software Engineering, Shenzhen University. He received his Ph.D. degree from the City University of Hong Kong in 2014. His research interest covers artificial immune system, multiobjective optimization, and dynamic system. Corresponding author of this paper

  • 摘要: 在现代社会中, 复杂物流配送场景的车辆路径规划问题(Vehicle routing problem, VRP)一般带有时间窗约束且需要提供同时取送货的服务. 这种复杂物流配送场景的车辆路径规划问题是NP-难问题. 当其规模逐渐增大时, 一般的数学规划方法难以求解, 通常使用启发式方法在限定时间内求得较优解. 然而, 传统的启发式方法从原大规模问题直接开始搜索, 无法利用先前相关的优化知识, 导致收敛速度较慢. 因此, 提出面向复杂物流配送场景的车辆路径规划多任务辅助进化算法(Multitask-based assisted evolutionary algorithm, MBEA), 通过使用迁移优化方法加快算法收敛速度, 其主要思想是通过构造多个简单且相似的子任务用于辅助优化原大规模问题. 首先从原大规模问题中随机选择一部分客户订单用于构建多个不同的相似优化子任务, 然后使用进化多任务(Evolutional multitasking, EMT)方法用于生成原大规模问题和优化子任务的候选解. 由于优化子任务相对简单且与原大规模问题相似, 其搜索得到的路径特征可以通过任务之间的知识迁移辅助优化原大规模问题, 从而加快其求解速度. 最后, 提出的算法在京东物流公司快递取送货数据集上进行验证, 其路径规划效果优于当前最新提出的路径规划算法.
  • 图  1  VRPPDT模型

    Fig.  1  The model of the VRPPDT

    图  2  MBEA总体框架图

    Fig.  2  The overall framework diagram of MBEA

    图  3  一个个体的编码方法

    Fig.  3  The coding method of an individual

    图  4  子任务生成及解码过程

    Fig.  4  The generation and decoding process of the subtask

    图  5  一个解的切分过程

    Fig.  5  The splitting process of a solution

    图  6  基于路径的交叉过程

    Fig.  6  The operation process of the route-based crossover

    图  7  顺序交叉操作过程

    Fig.  7  The operation process of the order crossover

    图  8  本文提出的方法和对比算法的平均搜索收敛轨迹

    Fig.  8  Averaged search convergence traces of the proposed method and the compared algorithms

    表  1  京东数据集的特性

    Table  1  Properties of Jingdong dataset

    问题|V|CJ$ {u_1} $$ {u _2} $
    F201 ~ F2042002.55003000.014
    F401 ~ F4044002.55003000.014
    F601 ~ F6046002.55003000.014
    F801 ~ F8048002.55003000.014
    F1001 ~ F10041 0002.55003000.014
    下载: 导出CSV

    表  2  MBEA算法参数设置

    Table  2  Parameter settings in MBEA

    参数含义
    Evaluation算法总评价次数18 000
    TE每阶段的评价次数3 600
    N种群大小36
    Nre阶段数5
    Nbe保留个体的数量18
    k子任务个数1
    lower子任务维度最低占比0.7
    下载: 导出CSV

    表  3  MBEA和5种对比算法在京东数据集对比实验结果

    Table  3  Comparative experimental results of MBEA and five compared algorithms on Jingdong dataset

    问题MBEAEMAMATECCMOGVNSVNSME
    NVTDTC运行
    时间 (s)
    NVTDTC运行
    时间 (s)
    NVTDTC运行
    时间 (s)
    NVTDTC运行
    时间 (s)
    NVTDTC运行
    时间 (s)
    NVTDTC运行
    时间 (s)
    F2014353 85166 7513 2914554 91868 4184 2524253 99766 5978 7125166 09981 3992 9765284 808100 408815060 49475 4943
    F2024453 15566 3553 2704756 28870 3884 3404353 64966 60914 1945263 78279 3822 8395367 75683 6562524959 72874 4282
    F2034354 89967 6793 3564659 00972 8095 4164254 54467 02413 6354967 60882 3082 8815183 07998 3791035165 95181 2512
    F2044353 31166 2112 9834656 45670 2563 9864354 39867 2389 9294862 32976 7292 9705274 57190 1713005160 41575 7152
    F4018199 380123 62011 53893120 041147 9412 56784109 863135 12316 85294124 412152 6128 58098144 757174 1571 22996112 942141 74215
    F40284103 091128 35113 338101122 636152 9362 53587113 871139 97110 742100130 655160 6557 923101160 822191 12226898117 970147 37012
    F4038098 175122 05512 11995122 289150 7892 73184109 212134 41210 15497123 599152 6998 36498160 018189 41842093111 171139 07115
    F4048399 809124 64912 65695116 269144 7692 69486110 555136 29513 709100127 209157 2098 154101136 483166 78365194110 775138 97517
    F601118149 868185 14815 779153202 915248 8162 663126174 424212 34417 795148192 176236 57615 623144240 941284 141702138171 997213 39741
    F602121153 129189 42919 571164204 772253 9722 656129177 851216 55118 839146199 278243 07815 505141227 723270 0231 624143175 068217 96849
    F603120153 681189 74116 090151202 985248 2852 922128176 806215 14617 636151198 996244 29615 032143219 879262 779395142171 057213 65737
    F604122153 477190 13718 569157204 541251 6412 886128176 943215 40318 789154196 028242 22815 201145204 293247 793757141172 956215 25633
    F801159175 009222 70911 565200244 506304 5063 679164196 076245 15620 421200234 549294 54925 467189278 179334 8791 654178189 502242 90282
    F802157173 598220 57713 077210226 736289 7363 657164194 325243 46520 835199236 794296 49425 879184271 798326 9981 153179192 243245 943107
    F803159173 474221 17314 682206240 358302 1583 355165195 539244 91924 212201236 025296 32525 387186231 297287 0971 130180188 245242 24571
    F804156171 956218 75612 743213227 247291 1473 324161191 853240 03321 884198226 353285 75325 707181231 743286 0431 490174186 214238 41481
    F1001212265 385329 0449 698275363 035445 5353 874222293 298359 83825 957279364 136447 83634 957239391 293462 9931 236232278 192347 792154
    F1002211264 034327 2138 655279356 200439 9003 858225291 180358 74027 482284354 899440 09934 582240352 092424 0922 847234278 465348 665126
    F1003212265 409329 0088 910275358 768441 2683 917227295 806363 78626 217283359 276444 17633 748243408 770481 670554231274 553343 853126
    F1004212262 117325 65610 331285362 496447 9963 914223289 035355 81526 180289360 481447 18133 515234348 460418 660890233276 896346 796123
    最佳/
    全部
    18/200/202/200/200/200/20
    下载: 导出CSV

    表  4  RBX和OX的消融实验结果

    Table  4  Ablation experiment results of RBX and OX

    问题RBXOX RBX + OX
    F20166 51767 96666 751
    F20266 36567 74466 355
    F20368 94871 71867 679
    F20466 97069 37266 211
    F401124 851148 685123 620
    F402128 798146 954128 351
    F403123 550149 781122 055
    F404125 247155 403124 649
    F601187 048246 299185 148
    F602192 623253 252189 429
    F603193 915247 466189 741
    F604193 410245 400190 137
    F801224 758298 889222 709
    F802228 345296 430220 577
    F803226 138302 783221 173
    F804220 988294 788218 756
    F1001342 544442 939329 044
    F1002339 143440 007327 213
    F1003341 946446 173329 008
    F1004336 077445 518325 656
    最佳/全部1/200/2019/20
    下载: 导出CSV

    表  5  MBEA中参数lower的敏感性分析

    Table  5  Sensitivity analysis of lower in MBEA

    问题TC (0.7)TC (0.5)TC (0.6)TC (0.8)TC (0.9)
    F20166 75166 66466 92666 89566 971
    F20266 35566 58766 59766 67766 751
    F20367 67968 20667 91968 02767 783
    F20466 21166 21565 92066 20966 150
    F401123 620123 826123 103122 861122 672
    F402128 351127 154127 696127 771127 986
    F403122 055122 428122 703122 343122 270
    F404124 649124 771125 365125 138124 936
    F601185 148185 831186 163185 579186 371
    F602189 429190 317190 661190 363190 731
    F603189 741189 160189 740189 986189 683
    F604190 137189 300189 128189 743188 712
    F801222 709221 057221 905221 221220 910
    F802220 577221 957220 655219 998220 951
    F803221 173222 172222 227221 495221 377
    F804218 756218 002216 628217 680218 297
    F1001329 044330 379330 059330 929329 632
    F1002327 213327 346327 565326 923327 199
    F1003329 008329 596326 035328 369327 482
    F1004325 656325 790325 812326 352327 106
    最佳/全部9/203/203/202/203/20
    下载: 导出CSV

    表  6  MBEA中参数k的敏感性分析

    Table  6  Sensitivity analysis of parameter k in MBEA

    问题TC (1)TC (0)TC (2)TC (3)
    F20166 75167 98566 29866 731
    F20266 35567 92067 00267 111
    F20367 67968 18067 91767 680
    F20466 21166 62166 52465 730
    F401123 620124 871124 825123 839
    F402128 351127 377128 292127 603
    F403122 055123 494122 305121 883
    F404124 649126 338124 959125 486
    F601185 148187 055185 004187 381
    F602189 429192 343192 178189 516
    F603189 741190 448190 047190 610
    F604190 137191 208189 940189 096
    F801222 709223 158223 670224 248
    F802220 577222 758223 576225 523
    F803221 173222 456223 684223 939
    F804218 756218 393217 485220 373
    F1001329 044330 374331 387332 643
    F1002327 213329 829329 525326 603
    F1003329 008331 877330 099329 200
    F1004325 656330 725326 082331 858
    最佳/全部12/201/203/204/20
    下载: 导出CSV
  • [1] Hu M, Liu W D, Peng K, Ma X Q, Cheng W Q, Liu J C, et al. Joint routing and scheduling for vehicle-assisted multidrone surveillance. IEEE Internet of Things Journal, 2019, 6(2): 1781-1790 doi: 10.1109/JIOT.2018.2878602
    [2] 杨培颖, 唐加福, 于洋, 裴金翔. 面向最小碳排放量的接送机场服务的车辆路径与调度. 自动化学报, 2013, 39(4): 424-432 doi: 10.1016/S1874-1029(13)60042-7

    Yang Pei-Ying, Tang Jia-Fu, Yu Yang, Pei Jin-Xiang. Minimizing carbon emissions for vehicle routing and scheduling in picking up and delivering customers to airport service. Acta Automatica Sinica, 2013, 39(4): 424-432 doi: 10.1016/S1874-1029(13)60042-7
    [3] 韩月起, 张凯, 宾洋, 秦闯, 徐云霄, 李小川, 等. 基于凸近似的避障原理及无人驾驶车辆路径规划模型预测算法. 自动化学报, 2020, 46(1): 153-167

    Han Yue-Qi, Zhang Kai, Bin Yang, Qin Chuang, Xu Yun-Xiao, Li Xiao-Chuan, et al. Convex approximation based avoidance theory and path planning MPC for driver-less vehicles. Acta Automatica Sinica, 2020, 46(1): 153-167
    [4] 徐杨, 陆丽萍, 褚端峰, 黄子超. 无人车辆轨迹规划与跟踪控制的统一建模方法. 自动化学报, 2019, 45(4): 799-807

    Xu Yang, Lu Li-Ping, Chu Duan-Feng, Huang Zi-Chao. Unified modeling of trajectory planning and tracking for unmanned vehicle. Acta Automatica Sinica, 2019, 45(4): 799-807
    [5] 吴伟, 刘洋, 刘威, 吴国弘, 马万经. 自动驾驶环境下交叉口车辆路径规划与最优控制模型. 自动化学报, 2020, 46(9): 1971-1985

    Wu Wei, Liu Yang, Liu Wei, Wu Guo-Hong, Ma Wan-Jing. A novel autonomous vehicle trajectory planning and control model for connected-and-autonomous intersections. Acta Automatica Sinica, 2020, 46(9): 1971-1985
    [6] Abbatecola L, Fanti M P, Pedroncelli G, Ukovich W. A distributed cluster-based approach for pick-up services. IEEE Transactions on Automation Science and Engineering, 2019, 16(2): 960-971 doi: 10.1109/TASE.2018.2879875
    [7] 王素欣, 高利, 崔小光, 曹宏美. 多需求点车辆调度模型及其群体智能混合求解. 自动化学报, 2008, 34(1): 102-104

    Wang Su-Xin, Gao Li, Cui Xiao-Guang, Cao Hong-Mei. Study on multi-requirement points vehicle scheduling model and its swarm mix algorithm. Acta Automatica Sinica, 2008, 34(1): 102-104
    [8] 曾正洋, 许维胜, 徐志宇. 开放式两级车辆路径问题建模与多起始点变邻域下降法求解. 计算机科学, 2014, 41(10): 232-237

    Zeng Zheng-Yang, Xu Wei-Sheng, Xu Zhi-Yu. Modeling and multi-start variable neighborhood descent solution of two-echelon open vehicle routing problem. Computer Science, 2014, 41(10): 232-237
    [9] Kheirkhah A, Navidi H, Bidgoli M M. An improved benders decomposition algorithm for an arc interdiction vehicle routing problem. IEEE Transactions on Engineering Management, 2016, 63(2): 259-273 doi: 10.1109/TEM.2016.2542849
    [10] 胡蓉, 李洋, 钱斌, 金怀平, 向凤红. 结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题. 自动化学报, 2022, 48(12): 3006-3023

    Hu Rong, Li Yang, Qian Bin, Jin Huai-Ping, Xiang Feng-Hong. An enhanced ant colony optimization combined with clustering decomposition for solving complex green vehicle routing problem. Acta Automatica Sinica, 2022, 48(12): 3006-3023
    [11] Xiao J H, Zhang T, Du J G, Zhang X Y. An evolutionary multiobjective route grouping-based heuristic algorithm for large-scale capacitated vehicle routing problems. IEEE Transactions on Cybernetics, 2021, 51(8): 4173-4186 doi: 10.1109/TCYB.2019.2950626
    [12] Lin C H, Choy K L, Ho G T S, Chung S H, Lam H Y. Survey of green vehicle routing problem: Past and future trends. Expert Systems With Applications, 2014, 41(4): 1118-1138 doi: 10.1016/j.eswa.2013.07.107
    [13] Kassem S, Chen M Y. Solving reverse logistics vehicle routing problems with time windows. The International Journal of Advanced Manufacturing Technology, 2013, 68(1-4): 57-68 doi: 10.1007/s00170-012-4708-9
    [14] Min H. The multiple vehicle routing problem with simultaneous delivery and pick-up points. Transportation Research Part A: General, 1989, 23(5): 377-386 doi: 10.1016/0191-2607(89)90085-X
    [15] Dethloff J. Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up. OR-Spektrum, 2001, 23(1): 79-96 doi: 10.1007/PL00013346
    [16] Berbeglia G, Cordeau J F, Laporte G. Dynamic pickup and delivery problems. European Journal of Operational Research, 2010, 202(1): 8-15 doi: 10.1016/j.ejor.2009.04.024
    [17] Wang H F, Chen Y Y. A genetic algorithm for the simultaneous delivery and pickup problems with time window. Computers and Industrial Engineering, 2012, 62(1): 84-95 doi: 10.1016/j.cie.2011.08.018
    [18] Eksioglu B, Vural A V, Reisman A. The vehicle routing problem: A taxonomic review. Computers and Industrial Engineering, 2009, 57(4): 1472-1483 doi: 10.1016/j.cie.2009.05.009
    [19] 范厚明, 刘鹏程, 刘浩, 侯登凯. 多中心联合配送模式下集货需求随机的VRPSDP问题. 自动化学报, 2021, 47(7): 1646-1660

    Fan Hou-Ming, Liu Peng-Cheng, Liu Hao, Hou Deng-Kai. The multi-depot vehicle routing problem with simultaneous deterministic delivery and stochastic pickup based on joint distribution. Acta Automatica Sinica, 2021, 47(7): 1646-1660
    [20] 陈萍, 黄厚宽, 董兴业. 求解卸装一体化的车辆路径问题的混合启发式算法. 计算机学报, 2008, 31(4): 565-73

    Chen Ping, Huang Hou-Kuan, Dong Xing-Ye. A hybrid heuristic algorithm for the vehicle routing problem with simultaneous delivery and pickup. Chinese Journal of Computers, 2008, 31(4): 565-573
    [21] Gupta A, Heng C K, Ong Y S, Tan P S, Zhang A N. A generic framework for multi-criteria decision support in eco-friendly urban logistics systems. Expert Systems with Applications, 2017, 71: 288-300 doi: 10.1016/j.eswa.2016.09.033
    [22] Wang J H, Weng T Y, Zhang Q F. A two-stage multiobjective evolutionary algorithm for multiobjective multidepot vehicle routing problem with time windows. IEEE Transactions on Cybernetics, 2019, 49(7): 2467-2478 doi: 10.1109/TCYB.2018.2821180
    [23] Wang C, Mu D, Zhao F, Sutherland J W. A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup-delivery and time windows. Computers & Industrial Engineering, 2015, 83: 111-122
    [24] Mingyong L, Erbao C. An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows. Engineering Applications of Artificial Intelligence, 2010, 23(2): 188-195 doi: 10.1016/j.engappai.2009.09.001
    [25] 黄务兰, 张涛. 基于改进全局人工鱼群算法的VRPSPDTW研究. 计算机工程与应用, 2016, 52(21): 21-29

    Huang Wu-Lan, Zhang Tao. Vehicle routing problem with simultaneous pick-up and delivery and time-windows based on improved global artificial fish swarm algorithm. Computer Engineering and Applications, 2016, 52(21): 21-29
    [26] Shi Y, Zhou Y J, Boudouh T, Grunder O. A lexicographic-based two-stage algorithm for vehicle routing problem with simultaneous pickup-delivery and time window. Engineering Applications of Artificial Intelligence, 2020, 95: Article No. 103901
    [27] Hof J, Schneider M. An adaptive large neighborhood search with path relinking for a class of vehicle-routing problems with simultaneous pickup and delivery. Networks, 2019, 74(3): 207-250 doi: 10.1002/net.21879
    [28] Iqbal M, Xue B, Al-Sahaf H, Zhang M J. Cross-domain reuse of extracted knowledge in genetic programming for image classification. IEEE Transactions on Evolutionary Computation, 2017, 21(4): 569-587 doi: 10.1109/TEVC.2017.2657556
    [29] Di S, Zhang H G, Li C G, Mei X, Prokhorov D, Ling H B. Cross-domain traffic scene understanding: A dense correspondence-based transfer learning approach. IEEE Transactions on Intelligent Transportation Systems, 2018, 19(3): 745-757 doi: 10.1109/TITS.2017.2702012
    [30] Chalmers E, Contreras E B, Robertson B, Luczak A, Gruber A. Learning to predict consequences as a method of knowledge transfer in reinforcement learning. IEEE Transactions on Neural Networks and Learning Systems, 2018, 29(6): 2259-2270 doi: 10.1109/TNNLS.2017.2690910
    [31] Gupta A, Ong Y S, Feng L. Multifactorial evolution: Toward evolutionary multitasking. IEEE Transactions on Evolutionary Computation, 2016, 20(3): 343-357 doi: 10.1109/TEVC.2015.2458037
    [32] Gupta A, Ong Y S, Feng L, Tan K C. Multiobjective multifactorial optimization in evolutionary multitasking. IEEE Transactions on Cybernetics, 2017, 47(7): 1652-1665 doi: 10.1109/TCYB.2016.2554622
    [33] Bali K K, Ong Y S, Gupta A, Tan P S. Multifactorial evolutionary algorithm with online transfer parameter estimation: MFEA-Ⅱ. IEEE Transactions on Evolutionary Computation, 2020, 24(1): 69-83 doi: 10.1109/TEVC.2019.2906927
    [34] Hao X X, Qu R, Liu J. A unified framework of graph-based evolutionary multitasking hyper-heuristic. IEEE Transactions on Evolutionary Computation, 2021, 25(1): 35-47 doi: 10.1109/TEVC.2020.2991717
    [35] Feng L, Zhou L, Gupta A, Zhong J H, Zhu Z X, Tan K C, et al. Solving generalized vehicle routing problem with occasional drivers via evolutionary multitasking. IEEE Transactions on Cybernetics, 2021, 51(6): 3171-3184 doi: 10.1109/TCYB.2019.2955599
    [36] Feng L, Huang Y X, Zhou L, Zhong J H, Gupta A, Tang K, et al. Explicit evolutionary multitasking for combinatorial optimization: A case study on capacitated vehicle routing problem. IEEE Transactions on Cybernetics, 2021, 51(6): 3143-3156 doi: 10.1109/TCYB.2019.2962865
    [37] Feng L, Zhou L, Zhong J H, Gupta A, Ong Y S, Tan K C, et al. Evolutionary multitasking via explicit autoencoding. IEEE Transactions on Cybernetics, 2019, 49(9): 3457-3470 doi: 10.1109/TCYB.2018.2845361
    [38] Feng L, Huang Y X, Tsang I W, Gupta A, Tang K, Tan K C, et al. Towards faster vehicle routing by transferring knowledge from customer representation. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(2): 952-965 doi: 10.1109/TITS.2020.3018903
    [39] Shang Q X, Huang Y X, Wang Y, Li M, Feng L. Solving vehicle routing problem by memetic search with evolutionary multitasking. Memetic Computing, 2022, 14(1): 31-44. doi: 10.1007/s12293-021-00352-7
    [40] Braekers K, Ramaekers K, Van Nieuwenhuyse I. The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering, 2016, 99: 300-313
    [41] Huang M F, Hu X P. Large scale vehicle routing problem: An overview of algorithms and an intelligent procedure. International Journal of Innovative Computing, Information and Control, 2012, 8(8): 5809-5819
    [42] Shin K, Han S Y. A centroid-based heuristic algorithm for the capacitated vehicle routing problem. Computing and Informatics, 2011, 30(4): 721-732
    [43] Angelelli E, Mansini R. The vehicle routing problem with time windows and simultaneous pick-up and delivery. Quantitative Approaches to Distribution Logistics and Supply Chain Management. Berlin: Springer, 2002. 249−267
    [44] Dell'Amico M, Righini G, Salani M. A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection. Transportation Science, 2006, 40(2): 235-247 doi: 10.1287/trsc.1050.0118
    [45] Rieck J, Zimmermann J. Exact solutions to the symmetric and asymmetric vehicle routing problem with simultaneous delivery and pick-up. Business Research, 2013, 6(1): 77-92 doi: 10.1007/BF03342743
    [46] Subramanian A, Uchoa E, Pessoa A A, Ochi L S. Branch-cut-and-price for the vehicle routing problem with simul-taneous pickup and delivery. Optimization Letters, 2013, 7(7): 1569-1581 doi: 10.1007/s11590-012-0570-9
    [47] Cao W J, Yang W S. A survey of vehicle routing problem. MATEC Web of Conferences, 2017, 100: Article No. 01006
    [48] Elshaer R, Awad H. A taxonomic review of metaheuristic algorithms for solving the vehicle routing problem and its variants. Computers and Industrial Engineering, 2020, 140: Article No. 106242
    [49] Yu V F, Redi A A N P, Hidayat Y A, Wibowo O J. A simulated annealing heuristic for the hybrid vehicle routing problem. Applied Soft Computing, 2017, 53: 119-132 doi: 10.1016/j.asoc.2016.12.027
    [50] Schermer D, Moeini M, Wendt O. A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations. Computers & Operations Research, 2019, 109: 134-158
    [51] Ribeiro G M, Laporte G. An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem. Computers & Operations Research, 2012, 39(3): 728-735
    [52] Avci M, Topaloglu S. A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with sim-ultaneous pickup and delivery. Expert Systems with Applications, 2016, 53: 160-171 doi: 10.1016/j.eswa.2016.01.038
    [53] Zhou Y, Kong L J, Cai Y Q, Wu Z Y, Liu S P, Hong J M, et al. A decomposition-based local search for large-scale many-objective vehicle routing problems with simultaneous delivery and pickup and time windows. IEEE Systems Journal, 2020, 14(4): 5253-5264 doi: 10.1109/JSYST.2019.2959664
    [54] Baker B M, Ayechew M A. A genetic algorithm for the vehicle routing problem. Computers & Operations Research, 2003, 30(5): 787-800
    [55] Mohammed M A, Abd Ghani M K, Hamed R I, Mostafa S A, Ahmad M S, Ibrahim D A. Solving vehicle routing problem by using improved genetic algorithm for optimal solution. Journal of Computational Science, 2017, 21: 255-262 doi: 10.1016/j.jocs.2017.04.003
    [56] Sabar N R, Bhaskar A, Chung E, Turky A, Song A. An adaptive memetic approach for heterogeneous vehicle routing problems with two-dimensional loading constraints. Swarm and Evolutionary Computation, 2020, 58: Article No. 100730
    [57] Ouaddi K, Mhada F, Benadada Y. Memetic algorithm for multi-tours dynamic vehicle routing problem with overtime (MDVRPOT). International Journal of Industrial Engineering Computations, 2020, 11(4): 643-662
    [58] Zhang X Y, Duan H B. An improved constrained differential evolution algorithm for unmanned aerial vehicle global route planning. Applied Soft Computing, 2015, 26: 270-284 doi: 10.1016/j.asoc.2014.09.046
    [59] Venkatesan S R, Logendran D, Chandramohan D. Optimization of capacitated vehicle routing problem using PSO. International Journal of Engineering Science and Technology, 2011, 3(10): 7469-7477
    [60] Yu B, Yang Z Z, Yao B Z. An improved ant colony optimization for vehicle routing problem. European Journal of Operational Research, 2009, 196(1): 171-176 doi: 10.1016/j.ejor.2008.02.028
    [61] Lee C Y, Lee Z J, Lin S W, Ying K C. An enhanced ant colony optimization (EACO) applied to capacitated vehicle routing problem. Applied Intelligence, 2010, 32(1): 88-95 doi: 10.1007/s10489-008-0136-9
    [62] Liu S C, Tang K, Yao X. Memetic search for vehicle routing with simultaneous pickup-delivery and time windows. Swarm and Evolutionary Computation, 2021, 66: Article No. 100927
    [63] Ma Y F, Li Z M, Yan F, Feng C Y. A hybrid priority-based genetic algorithm for simultaneous pickup and delivery problems in reverse logistics with time windows and multiple decision-makers. Soft Computing, 2019, 23(15): 6697-6714 doi: 10.1007/s00500-019-03754-5
    [64] Wang J H, Zhou Y, Wang Y, Zhang J, Chen C L P, Zheng Z B. Multiobjective vehicle routing problems with simultaneous delivery and pickup and time windows: Formulation, instances, and algorithms. IEEE Transactions on Cybernetics, 2016, 46(3): 582-594 doi: 10.1109/TCYB.2015.2409837
    [65] Lagos C, Guerrero G, Cabrera E, Moltedo A, Johnson F, Paredes F. An improved particle swarm optimization algorithm for the VRP with simultaneous pickup and delivery and time windows. IEEE Latin America Transactions, 2018, 16(6): 1732-1740 doi: 10.1109/TLA.2018.8444393
    [66] Potvin J Y, Bengio S. The vehicle routing problem with time windows Part Ⅱ: Genetic search. INFORMS Journal on Computing, 1996, 8(2): 165-172 doi: 10.1287/ijoc.8.2.165
    [67] Oliver I M, Smith D J, Holland J R C. A study of permutation crossover operators on the traveling salesman problem. In: Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and Their Application. Cambridge, USA: L. Erlbaum Associates Inc., 1987.
    [68] Tian Y, Zhang T, Xiao J H, Zhang X Y, Jin Y C. A coevolutionary framework for constrained multiobjective opti-mization problems. IEEE Transactions on Evolutionary Computation, 2021, 25(1): 102-116 doi: 10.1109/TEVC.2020.3004012
    [69] Fleszar K, Osman I H, Hindi K S. A variable neighbourhood search algorithm for the open vehicle routing problem. European Journal of Operational Research, 2009, 195(3): 803-809 doi: 10.1016/j.ejor.2007.06.064
    [70] Cai J C, Zhu Q L, Lin Q Z. Variable neighborhood search for a new practical dynamic pickup and delivery problem. Swarm and Evolutionary Computation, 2022, 75: Article No. 101182
  • 加载中
图(8) / 表(6)
计量
  • 文章访问数:  183
  • HTML全文浏览量:  90
  • PDF下载量:  81
  • 被引次数: 0
出版历程
  • 收稿日期:  2023-02-10
  • 录用日期:  2023-08-07
  • 网络出版日期:  2024-02-19
  • 刊出日期:  2024-03-29

目录

    /

    返回文章
    返回