面向车辆路径规划的自适应算子选择

车辆路径规划是一类常见的组合优化问题，通常指给定一些需要服务的任务和一个或多个发车点，寻找满足某些约束条件的成本最低的车辆行驶方案以完成这些任务。此类问题的输入信息通常可以用一个包含起始节点、需求节点和连接节点的边的图表示；它的解可表示为节点或边的序列，代表车辆的行驶顺序。车辆路径规划在物流运输、仓库调度等工业场景中广泛存在，其调度对象包含各种运载机器、物流从业者和抽象的工序流程。车辆路径规划中也存在一些普遍性挑战，如图结构数据的分析和约束的处理。因此，面向车辆路径规划的研究不仅对工业生产有重要的意义，也对其它相关的优化问题研究存在借鉴和启发作用。元启发式算法是优化求解车辆路径规划的主流算法之一。元启发式算法中通存在多样的优化算子，在求解过程中发挥重要作用。求解不同的问题时，最适合的算子可能不同。针对问题设计算子需要对问题有丰富专家知识，然而面对一个新的问题，研究者的专家知识是有限的。基于此情况，一些研究工作提出自适应算子选择策略，旨在基于不同算子的特性选择并组合这些算子以高效求解新的问题。自适应算子选择本质是个动态资源分配问题，在数值优化领域中已有了较为广泛的相关研究，但在组合优化领域中此类研究仍不充分。车辆路径规划问题的离散性、排列性和独特解空间结构导致难以直接应用数值优化领域已有的自适应算子选择策略，需要研究与设计特殊的自适应算子选择策略。

针对面向车辆路径规划的元启发式算法，(1) 本文首先提出了一种算子行为分析方法，以分析车辆路径规划问题上元启发式算法的行为特征，用于解释经典的自适应算子选择策略在此类问题上展现的性能和特性；(2) 基于分析结果，本文提出了一种算子对应邻域的相关性量化方法和一种基于邻域相关性的通用自适应算子选择框架，以提高基于该框架的元启发式算法的优化性能；(3) 本文探索了通过学习路径结构特征指导动态算子选择的方法，并讨论了基于机器学习的自适应算子选择在车辆路径规划上的优势与挑战，为未来的研究工作提供参考借鉴。虽然本文聚焦于面向车辆路径规划问题研究自适应算子选择，本文所提出的问题特性分析方法以及自适应算子选择方法可以被用于其它相似的优化问题和优化算法，也可以为其他动态资源分配问题的研究提供研究思路和方案。

[1] 中国物流学会. 何黎明：中国智慧物流新未来[EB/OL]. 2017. http://csl.chinawuliu.com.cn/ html/19888842.html Accessed 2021-10-11.
[2] 章合杰. 智慧物流的基本内涵和实施框架研究[J]. 商场现代化, 2011(23): 44-46.
[3] SÖRENSEN K, GLOVER F. Metaheuristics[J]. Encyclopedia of Operations Research and Management Science, 2013, 62: 960-970.
[4] MLADENOVIć N, HANSEN P. Variable neighborhood search[J/OL]. Computers & Operations Research, 1997, 24(11): 1097-1100. DOI: 10.1016/S0305-0548(97)00031-2.
[5] MOSCATO P, COTTA C. A gentle introduction to memetic algorithms[M/OL]. Boston, MA: Springer US, 2003: 105-144. DOI: 10.1007/0-306-48056-5_5.
[6] DAS S, SUGANTHAN P N. Differential evolution: a survey of the state-of-the-art[J/OL]. IEEE Transactions on Evolutionary Computation, 2011, 15(1): 4-31. DOI: 10.1109/TEVC.2010.20 59031.
[7] KENNEDY J, EBERHART R. Particle swarm optimization[C/OL]//Proceedings of ICNN’95 - International Conference on Neural Networks: volume 4. 1995: 1942-1948 vol.4. DOI: 10.1109/ICNN.1995.488968.
[8] MALLIPEDDI R, SUGANTHAN P, PAN Q, et al. Differential evolution algorithm with ensemble of parameters and mutation strategies[J/OL]. Applied Soft Computing, 2011, 11(2): 1679-1696. DOI: 10.1016/j.asoc.2010.04.024.
[9] LAN W X, YE Z Y, RUAN P, et al. Region-focused memetic algorithms with smart initialisation for real-world large-scale waste collection problems[J/OL]. IEEE Transactions on Evolutionary Computation, 2022, 26(4): 704-718. DOI: 10.1109/TEVC.2021.3123960.
[10] TANG K, MEI Y, YAO X. Memetic algorithm with extended neighborhood search for capacitated arc routing problems[J/OL]. IEEE Transactions on Evolutionary Computation, 2009, 13 (5): 1151-1166. DOI: 10.1109/TEVC.2009.2023449.
[11] TIAN Y, LI X P, MA H P, et al. Deep reinforcement learning based adaptive operator selection for evolutionary multi-objective optimization[J/OL]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2022, Early Access: 1-14. DOI: 10.1109/TETCI.2022.3146882.
[12] DURGUT R, AYDIN M E, ATLI I. Adaptive operator selection with reinforcement learning [J/OL]. Information Sciences, 2021, 581: 773-790. DOI: 10.1016/j.ins.2021.10.025.
[13] DURGUT R, AYDIN M E, RAKIB A. Transfer learning for operator selection: a reinforcement learning approach[J/OL]. Algorithms, 2022, 15(1). DOI: 10.3390/a15010024.
[14] TENG T H, HANDOKO S D, LAU H C. Self-organizing neural wetwork for adaptive operator selection in evolutionary search[C/OL]//FESTA P, SELLMANN M, VANSCHOREN J. Learning and Intelligent Optimization. Cham: Springer International Publishing, 2016: 187-202. DOI: 10.1007/978-3-319-50349-3_13.
[15] HANDOKO S D, NGUYEN D T, YUAN Z, et al. Reinforcement learning for adaptive operator selection in memetic search applied to quadratic assignment problem[C/OL]//GECCO Comp ’14: Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation. New York, NY, USA: Association for Computing Machinery, 2014: 193–194. DOI: 10.1145/2598394.2598451.
[16] GONG W Y, FIALHO Á, CAI Z H, et al. Adaptive strategy selection in differential evolution for numerical optimization: an empirical study[J/OL]. Information Sciences, 2011, 181(24): 5364-5386. DOI: 10.1016/j.ins.2011.07.049.
[17] KREMPSER E, FIALHO Á, BARBOSA H J. Adaptive operator selection at the hyper-level [C/OL]//Parallel Problem Solving from Nature - PPSN XII. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012: 378-387. DOI: 10.1007/978-3-642-32964-7_38.
[18] EPITROPAKIS M G, CARAFFINI F, NERI F, et al. A separability prototype for automatic memes with adaptive operator selection[C/OL]//2014: 70-77. DOI: 10.1109/FOCI.2014.7007 809.
[19] SORIA ALCARAZ J A, OCHOA G, CARPIO M, et al. Evolvability metrics in adaptive operator selection[C/OL]//GECCO ’14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation. New York, NY, USA: Association for Computing Machinery, 2014: 1327–1334. DOI: 10.1145/2576768.2598220.
[20] FIALHO A, SCHOENAUER M, SEBAG M. Analysis of adaptive operator selection techniques on the royal road and long k-path problems[C/OL]//GECCO ’09: Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation. New York, NY, USA: Association for Computing Machinery, 2009: 779–786. DOI: 10.1145/1569901.1570009.
[21] FIALHO Á, DA COSTA L, SCHOENAUER M, et al. Dynamic multi-armed bandits and extreme value-based rewards for adaptive operator selection in evolutionary algorithms[C/OL]// Learning and Intelligent Optimization. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009: 176-190. DOI: 10.1007/978-3-642-11169-3_13.
[22] FIALHO A, SCHOENAUER M, SEBAG M. Toward comparison-based adaptive operator selection[ C/OL]//GECCO ’10: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation. New York, NY, USA: Association for Computing Machinery, 2010: 767–774. DOI: 10.1145/1830483.1830619.
[23] FIALHO Á, DA COSTA L, SCHOENAUER M, et al. Extreme value based adaptive operator selection[C/OL]//Parallel Problem Solving from Nature – PPSN X. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008: 175-184. DOI: 10.1007/978-3-540-87700-4_18.
[24] CANDAN C, GOEFFON A, LARDEUX F, et al. A dynamic island model for adaptive operator selection[C/OL]//GECCO ’12: Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation. New York, NY, USA: Association for Computing Machinery: 1253– 1260. DOI: 10.1145/2330163.2330337.
[25] CONSOLI P, YAO X. Diversity-driven selection of multiple crossover operators for the capacitated arc routing problem[C/OL]//BLUM C, OCHOA G. Evolutionary Computation in Combinatorial Optimisation. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014: 97-108. DOI: 10.1007/978-3-662-44320-0_9.
[26] CONSOLI P A, MEI Y, MINKU L L, et al. Dynamic selection of evolutionary operators based on online learning and fitness landscape analysis[J/OL]. Soft Computing, 2016, 20(10): 3889- 3914. DOI: 10.1007/s00500-016-2126-x.
[27] LU H, WEN ZHANG X, YANG S. A learning-based iterative method for solving vehicle routing problems[C/OL]//International Conference on Learning Representations. 2020. https://openre view.net/forum?id=BJe1334YDH.
[28] FLOOD M M. The traveling-salesman problem[J/OL]. Operations Research, 1956, 4(1): 61-75. DOI: 10.1287/opre.4.1.61.
[29] 管梅谷. 奇偶点图上作业法[J]. 数学学报, 1960, 10(3): 263-266.
[30] DANTZIG G B, RAMSER J H. The truck dispatching problem[J/OL]. Management Science, 1959, 6(1): 80-91. DOI: 10.1287/mnsc.6.1.80.
[31] GOLDEN B L, WONG R T. Capacitated arc routing problems[J/OL]. Networks, 1981, 11(3): 305-315. DOI: 10.1002/net.3230110308.
[32] LAPORTE G, NOBERT Y. A branch and bound algorithm for the capacitated vehicle routing problem[J/OL]. Operations-Research-Spektrum, 1983, 5(2): 77-85. DOI: 10.1007/BF017200 15.
[33] GOLDEN B, ASSAD A, LEVY L, et al. The fleet size and mix vehicle routing problem[J]. Computers & Operations Research, 1984, 11(1): 49-66.
[34] WILSON N H M, COLVIN N J. Computer control of the Rochester dial-a-ride system: number 77[M]. Massachusetts Institute of Technology, Center for Transportation Studies, 1977.
[35] BELTRAMI E J, BODIN L D. Networks and vehicle routing for municipal waste collection [J/OL]. Networks, 1974, 4(1): 65-94. DOI: 10.1002/net.3230040106.
[36] BENJAMIN A M, BEASLEY J E. Metaheuristics with disposal facility positioning for the waste collection VRP with time windows[J/OL]. Optimization Letters, 2013, 7(7): 1433-1449. DOI: 10.1007/s11590-012-0549-6.
[37] AKHTAR M, HANNAN M, BEGUM R, et al. Backtracking search algorithm in CVRP models for efficient solid waste collection and route optimization[J/OL]. Waste Management, 2017, 61: 117-128. DOI: 10.1016/j.wasman.2017.01.022.
[38] KIM B I, KIM S, SAHOO S. Waste collection vehicle routing problem with time windows [J/OL]. Computers & Operations Research, 2006, 33(12): 3624-3642. DOI: 10.1016/j.cor.20 05.02.045.
[39] GRULER A, FIKAR C, JUAN A A, et al. Supporting multi-depot and stochastic waste collection management in clustered urban areas via simulation–optimization[J/OL]. Journal of Simulation, 2017, 11(1): 11-19. DOI: 10.1057/s41273-016-0002-4.
[40] TAILLARD É D. A heuristic column generation method for the heterogeneous fleet VRP[J/OL]. RAIRO - Operations Research, 1999, 33(1): 1–14. DOI: 10.1051/ro:1999101.
[41] TAN K C, LEE L H, ZHU Q, et al. Heuristic methods for vehicle routing problem with time windows[J/OL]. Artificial Intelligence in Engineering, 2001, 15(3): 281-295. DOI: 10.1016/ S0954-1810(01)00005-X.
[42] LAPORTE G, SEMET F. Classical heuristics for the capacitated VRP[M/OL]//The Vehicle Routing Problem. 109-128. DOI: 10.1137/1.9780898718515.ch5.
[43] MEI Y, LI X D, YAO X. Decomposing large-scale capacitated arc routing problems using a random route grouping method[C/OL]//2013 IEEE Congress on Evolutionary Computation. 2013: 1013-1020. DOI: 10.1109/CEC.2013.6557678.
[44] MEI Y, LI X D, YAO X. Cooperative coevolution with route distance grouping for largescale capacitated arc routing problems[J/OL]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 435-449. DOI: 10.1109/TEVC.2013.2281503.
[45] TANG K, WANG J, LI X D, et al. A scalable approach to capacitated arc routing problems based on hierarchical decomposition[J/OL]. IEEE Transactions on Cybernetics, 2017, 47(11): 3928-3940. DOI: 10.1109/TCYB.2016.2590558.
[46] BAKER B M, AYECHEW M. A genetic algorithm for the vehicle routing problem[J/OL]. Computers & Operations Research, 2003, 30(5): 787-800. DOI: 10.1016/S0305-0548(02)000 51-5.
[47] BORTFELDT A, YI J. The split delivery vehicle routing problem with three-dimensional loading constraints[J/OL]. European Journal of Operational Research, 2020, 282(2): 545-558. DOI: 10.1016/j.ejor.2019.09.024.
[48] LI X J, YUAN M X, CHEN D, et al. A data-driven three-layer algorithm for split delivery vehicle routing problem with 3D container loading constraint[C/OL]//KDD ’18: Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. New York, NY, USA: Association for Computing Machinery, 2018: 528–536. DOI: 10.1145/ 3219819.3219872.
[49] FUELLERER G, DOERNER K F, HARTL R F, et al. Metaheuristics for vehicle routing problems with three-dimensional loading constraints[J/OL]. European Journal of Operational Research, 2010, 201(3): 751-759. DOI: 10.1016/j.ejor.2009.03.046.
[50] ESCOBAR-FALCÓN L M, ÁLVAREZ-MARTÍNEZ D, GRANADA-ECHEVERRI M, et al. A matheuristic algorithm for the three-dimensional loading capacitated vehicle routing problem (3L-CVRP)[J/OL]. Revista Facultad de Ingeniería Universidad de Antioquia, 2016(78): 09-20. DOI: 10.17533/udea.redin.n78a02.
[51] YI J, BORTFELDT A. The capacitated vehicle routing problem with three-dimensional loading constraints and split delivery-a case study[M/OL]//Operations Research Proceedings 2016. Cham: Springer International Publishing, 2018: 351-356. DOI: 10.1007/978-3-319-55702-1 _47.
[52] CESCHIA S, SCHAERF A, STÜTZLE T. Local search techniques for a routing-packing problem[ J]. Computers & industrial engineering, 2013, 66(4): 1138-1149.
[53] HELSGAUN K. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems[M]. Roskilde Universitet.
[54] HOOS H H. Automated algorithm configuration and parameter tuning[J/OL]. Autonomous Search, 2012: 37-71. DOI: 10.17533/udea.redin.n78a02.
[55] PAN Z J, KANG L S. An adaptive evolutionary algorithm for numerical optimization[C/OL]// Simulated Evolution and Learning: First Asia-Pacific Conference, SEAL’96 Taejon, Korea, November 9–12, 1996 Seclected Papers 1. Springer, 1997: 27-34. DOI: 10.1007/BFb0028518.
[56] ZHAN Z H, ZHANG J, LI Y, et al. Adaptive particle swarm optimization[J/OL]. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2009, 39(6): 1362-1381. DOI: 10.1109/TSMCB.2009.2015956.
[57] HUGHES E. Evolutionary algorithm with a novel insertion operator for optimising noisy functions[ C/OL]//Proceedings of the 2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512): volume 1. 2000: 790-797 vol.1. DOI: 10.1109/CEC.2000.870379.
[58] ZHANG H T, SUN J Y, XU Z B. Learning to mutate for differential evolution[C/OL]//2021 IEEE Congress on Evolutionary Computation (CEC). 2021: 1-8. DOI: 10.1109/CEC45853.2 021.9504990.
[59] TAN Z P, LI K S, WANG Y. Differential evolution with adaptive mutation strategy based on fitness landscape analysis[J/OL]. Information Sciences, 2021, 549: 142-163. DOI: 10.1016/j. ins.2020.11.023.
[60] SHARMA M, LÓPEZ-IBÁÑEZ M, KAZAKOV D. Performance assessment of recursive probability matching for adaptive operator selection in differential evolution[C/OL]//Parallel Problem Solving from Nature – PPSN XV. Cham: Springer International Publishing, 2018: 321-333. DOI: 10.1007/978-3-319-99259-4_26.
[61] THIERENS D. Adaptive strategies for operator allocation[J]. Parameter Setting in Evolutionary Algorithms, 2007: 77-90.
[62] THIERENS D. An adaptive pursuit strategy for allocating operator probabilities[C/OL]// GECCO ’05: Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation. New York, NY, USA: Association for Computing Machinery, 2005: 1539–1546. DOI: 10.1145/1068009.1068251.
[63] DACOSTA L, FIALHO A, SCHOENAUER M, et al. Adaptive operator selection with dynamic multi-armed bandits[C/OL]//GECCO ’08: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation. New York, NY, USA: Association for Computing Machinery, 2008: 913–920. DOI: 10.1145/1389095.1389272.
[64] KUK J, GONCALVES R, POZO A. Combining fitness landscape analysis and adaptive operator selection in multi and many-objective optimization[C/OL]//2019 8th Brazilian conference on intelligent systems (BRACIS). 2019: 503-508. DOI: 10.1109/BRACIS.2019.00094.
[65] SALLAM K M, ELSAYED S M, SARKER R A, et al. Landscape-based adaptive operator selection mechanism for differential evolution[J/OL]. Information Sciences, 2017, 418-419: 383-404. DOI: 10.1016/j.ins.2017.08.028.
[66] GOLDBERG D E. Probability matching, the magnitude of reinforcement, and classifier system bidding[J/OL]. Machine Learning, 1990, 5(4): 407-425. DOI: 10.1023/A:1022681708029.
[67] AUER P, CESA-BIANCHI N, FISCHER P. Finite-time analysis of the multiarmed bandit problem[ J/OL]. Machine Learning, 2002, 47(2): 235-256. DOI: 10.1023/A:1013689704352.
[68] LI W, LIANG P, SUN B, et al. Reinforcement learning-based particle swarm optimization with neighborhood differential mutation strategy[J/OL]. Swarm and Evolutionary Computation, 2023, 78: 101274. DOI: 10.1016/j.swevo.2023.101274.
[69] PITZER E, AFFENZELLER M. A comprehensive survey on fitness landscape analysis[M/OL]. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012: 161-191. DOI: 10.1007/978-3-642-232 29-9_8.
[70] MALAN K M, ENGELBRECHT A P. A survey of techniques for characterising fitness landscapes and some possible ways forward[J/OL]. Information Sciences, 2013, 241: 148-163. DOI: 10.1016/j.ins.2013.04.015.
[71] MALAN K M. A survey of advances in landscape analysis for optimisation[J/OL]. Algorithms, 2021, 14(2). DOI: 10.3390/a14020040.
[72] TAYARANI-N. M H, PRUGEL-BENNETT A. On the landscape of combinatorial optimization problems[J/OL]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 420-434. DOI: 10.1109/TEVC.2013.2281502.
[73] OCHOA G, VEREL S, DAOLIO F, et al. Local optima networks: a new model of combinatorial fitness landscapes[M]//Recent Advances in the Theory and Application of Fitness Landscapes. Springer Berlin Heidelberg, 2014: 233-262.
[74] LI F, GOLDEN B, WASIL E. Very large-scale vehicle routing: new test problems, algorithms, and results[J/OL]. Computers & Operations Research, 2005, 32(5): 1165-1179. DOI: 10.101 6/j.cor.2003.10.002.
[75] LIU S, ZHANG Y, TANG K, et al. How Good Is Neural Combinatorial Optimization?[A]. 2022. arXiv: 2209.10913.