基于自适应大邻域搜索的遗传算法求解VRPTW研究

郭庆腾 董学士 李清顺

摘要：针对传统遗传算法在求解带时间窗的车辆路径问题（vehicle routing problems with time window， VRPTW）上存在的易陷入局部最优及求解质量不高等问题，本文主要对基于自适应大邻域搜索的遗传算法求解带时间窗车辆路径问题进行研究。通过将自适应大邻域搜索算法与遗传算法相结合，称为ALNS-GA设计了3个移除算子和2个重插算子，以提高遗传算法的局部搜索能力，并优化了初始种群生成策略。同时，为了验证算法的有效性，分别对比了传统遗传算法和基于大规模邻域搜索的遗传算法（LNS-GA、LNS*-GA），并选取Solomon数据库上VRPTW测试算例，在Matlab R2016b上进行实验验证。实验结果表明，当终止条件为迭代100次时，ALNS-GA的求解质量高于传统遗传算法，大部分案例中，ALNS-GA所求的最好值优于LNS-GA和LNS*-GA，且ALNS-GA平均用时均小于LNS-GA和LNS*-GA，特别是当顾客规模为100时，ALNS-GA的平均用时更少，虽然小部分案例的平均值略高于LNS-GA和LNS*-GA，但从整体上看，ALNS-GA的寻优速度和质量均优于LNS-GA和LNS*-GA，说明经过改进后，遗传算法的局部搜索能力明显提高，可以有效改善遗传算法在带时间窗车辆路径问题上的应用。该研究具有一定的创新。

关键词：遗传算法； 自适应大邻域搜索算法； 局部搜索； 带时间窗车辆路径问题

中图分类号：TP18 文献标识码：A

文章编号：1006-9798（2023）02-0001-09； DOI：10.13306/j.1006-9798.2023.02.001

基金项目：国家自然科学基金资助项目（61902189）； 山东省软件工程重点实验室（山东大学）开放基金（2020SPKLSE0612）

作者简介：郭庆腾（1998-），男，硕士研究生，主要研究方向为智能计算。

通信作者：董学士（1985-），男，博士，助理教授，CCF会员，主要研究方向为智能计算和智能交通。Email：dxs_cs@163.com

车辆路径问题（vehicle routing problems，VRP）［1］一直是国内外学者研究的热点，它指在一定约束和客户需求下，多个车辆从配送中心出发为多个客户送货，目的是寻找最短路径。经过数十年的研究与发展，VRP 问题已拓展出众多具有现实意义的问题［2］，带时间窗的车辆路径问题［3］便是其中之一。VRPTW是在VRP问题的基础上，加入时间窗约束，车辆在客户指定的时间窗内送货，因此计算难度和复杂度也随之增加。目前，该类问题的解决算法分为精确算法和启发式算法［4］。精确式算法是一类可求出最优解的算法，例如分支定界法［5］和动态规划［6］等，但随着问题规模的不断扩大，精确算法很难在可接受时间内求得最优解［7］，因此一般采用启发式算法求解。常见的启发式算法有遗传算法（genetic algorithm，GA）［8］、蚁群算法［9］、人工蜂群算法［10］和粒子群算法［11］等。虽然这些算法有一定的优势，但在求解时存在搜索能力不足，易陷入局部最优和“早熟”等问题，导致求解质量不高。近年来，针对这些问题，众多学者对启发式算法进行了改进。何庆等人［12］提出改进遗传模拟退火算法，设计了一种自适应的Metropolis准则，用于求解旅行商问题；夏小云等人［13］提出基于大邻域搜索的人工蜂群优化算法，用于求解带容量约束的VRP，增加了算法的搜索能力，提升了算法的整体效率；胡蓉等人［14］在蚁群算法中引入动态信息素浓度挥发系数，并提出4种变邻域操作求解绿色车辆路径问题，有效平衡了算法的全局搜索和局部搜索能力，增强了算法的性能；I.SBAI等人［15］提出了一种遗传变邻域搜索算法，将遗传算法和变邻域搜索算法相结合，有效降低了收敛时间，提高了解的质量。此外，ZHANG D等人［16］提出Tabu-ABC混合算法，把蜂群算法和禁忌搜索算法相结合，应用于有现实约束的 VRP，并利用蜂群算法获得高质量的初始种群，提高了禁忌搜索算法的性能；M.ALINAGHIAN等人［17］提出了一种带随机拓扑的粒子群算法，应用于求解与时间相关的竞争 VRP，加快了算法的收敛速度；R.GOEL等人［18］提出萤火虫算法与蚁群算法的混合算法求解 VRP，用蚁群算法作为基本框架，萤火虫算法搜索解的空间，提高了解的质量。基于此，本文提出一种基于自适应大邻域搜索的混合遗传算法，将自适应大邻域搜索算法（adaptive large neighborhood search，ALNS）［19］与遗传算法相结合，即ALNS-GA算法，将其应用于VRPTW问题，同时在Matlab R2016b上进行多组实验验证。验证结果表明，改进后的算法加强了遗传算法的局部搜索能力，有效改善遗传算法在带时间窗车辆路径问题上的应用，该研究具有一定的實际应用价值。

自适应大邻域搜索算法操作流程如图2所示。

2.3 基于自适应大邻域搜索的遗传算法

由于VRPTW问题存在很多约束，复杂性高，而传统遗传算法求解会导致求解量不高，难以求出预期效果。因此，将ALNS与GA相结合，加强局部搜索，得到高质量解。其基本思想是在每次迭代中，将GA求得的种群采用ALNS进行局部搜索，以增强遗传算法的局部搜索能力，ALNS-GA流程图如图3所示。

3 实验结果与分析

3.1 参数设置

实验参数设置为违反容量约束惩罚系数α=10，违反时间窗约束惩罚系数β=100，交叉概率Pc=09，变异概率Pm=005，种群数目Nc=100，移除节点最小比例系数c1=01，移除节点最大比例系数c2=015，路径权重极小正数λ=0001，顾客需求权重极小正数φ=001，算子权重系数k=05，权重奖励ω1=10，权重惩罚ω2=1。

3.2 實验结果

为了验证算法的有效性，本文在Matlab R2016b上进行实验，实验案例选取Solomon数据库上VRPTW经典测试算例C型、R型和RC型。其中，每个案例运行20次，结果四舍五入，保留4位小数，C101-25，50和100表示该案例前25，50和100个顾客。将ALNS-GA与传统GA路径距离进行对比实验，ALNS-GA与GA路径距离对比结果如表1所示。

由表1可以看出，传统GA的求解质量较差，而由于ALNS-GA是在GA后增加了ALNS操作，能够更好的发挥局部搜索能力，提高了寻优能力，使每个案例中ALNS-GA所求得的最好值及平均值优于传统GA，达到了优化目的。

ALNS-GA求解C101-100最佳路线如图4所示，GA求解C101-100最佳路线如图5所示，ALNS-GA求解C101-100最佳迭代过程如图6所示，GA求解 C101-100最佳迭代过程如图7所示，ALNS-GA求得RC103-100最佳路线如图8所示，GA求得RC103-100最佳路线如图9所示，ALNS-GA求解RC103-100最佳迭代过程如图10所示，GA求解 RC103-100最佳迭代过程如图11所示。其中图4，图5，图8，图9为一个标准坐标系，采用欧式距离，单位为km。

由图4～图11可以看出，GA求得的最佳路线散乱无序，说明迭代100次后解的质量较差，而ALNS-GA求解的最佳路线则得到显著的优化，其中，C101-100的最佳路线与Solomon数据库中的最优路线一致，RC103-100的最佳路线接近于Solomon数据库中的最优路线。在迭代次数为100时，ALNS-GA的收敛速度快于传统GA，能够较早的收敛，与GA相比，ALNS-GA的搜索能力和效率均有明显的提升。

ALNS-GA运行结果如表2所示， LNS*-GA和LNS-GA运行结果如表3所示。其中，迭代次数均设置为100次，LNS-GA表示基于大规模邻域搜索算法的遗传算法，在局部搜索中只有1组移除和重插算子，每次移除顾客数固定值为15，LNS*-GA则按照式（14）进行移除顾客。

由表2和表3可以看出，在运行20次时，LNS-GA和LNS*-GA，ALNS-GA所求得的最优值均小于或等于LNS-GA和LNS*-GA，其中等于的情况是因为所得解已达到Solomon数据库中当前已知最优解。在求解所用时间上，终止条件为迭代100次时，ALNS-GA的求解平均用时均小于LNS-GA和LNS*-GA，当顾客规模为100时，ALNS-GA平均用时更少，说明改进的算法求解速度更快。尽管少部分案例的平均值略高于LNS-GA和LNS*-GA，但从整体上看，ALNS-GA的寻优速度和求解质量均有所提高，优于LNS-GA和LNS*-GA，能够有效应用于求解VRPTW。

4 结束语

本文主要对基于自适应大邻域搜索的遗传算法求解带时间窗车辆路径问题进行研究。首先建立数学模型，将ALNS和GA相结合求解VRPTW，充分发挥了ALNS的局部搜索能力和GA的全局搜索能力。在Solomon数据库的多组仿真实验对比表明，ALNS-GA求解质量和寻优速度均有所提高，改善了在车辆调度问题上的应用。在求解VRPTW中，虽然有优秀的算法求得的解和当前已知最优解质量相当，但目前并未有在每个案例中都能有良好表现的算法。ALNS扩展能力强，性能有待进一步开发，且ALNS含有众多参数，未来将进一步优化参数，以及研究有动态路况等因素和更大规模的VPRTW问题，并改进更加有效的求解算法。

参考文献：

［1］ 蒋华伟， 郭陶， 杨震. 车辆路径问题研究进展［J］. 电子学报， 2022， 50（2）：480-492.

［2］ ZHANG H， GE H， YANG J， et al. Review of vehicle routing problems：models， classification and solving algorithms［J］. Archives of Computational Methods in Engineering， 2022， 29（1）：195-221.

［3］ 张庆华， 吴光谱. 带时间窗的同时取送货车辆路径问题建模及模因求解算法［J］. 计算机应用， 2020， 40（4）：1097-1103.

［4］ POTVIN J Y. Evolutionary algorithms for vehicle routing［J］. Informs Journal on Computing， 2009， 21（4）：518-548.

［5］ BARD J F， KONTORAVDIS G， YU G. A branch-and-cut procedure for the vehicle routing problem with time windows［J］. Transportation Science， 2002， 36（2）：250-269.

［6］ 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.

［7］ 陈成. 基于改进遗传算法的带时间窗的多目标配送路径优化［J］. 信息技术与信息化， 2018（10）：48-51.

［8］ ZOU T， NING L I， SUN D B. Genetic algorithm for variable fleet vehicle routing problem with time window［J］. Systems Engineering-Theory & Practice， 2004， 4（6）：2846-2849.

［9］ MOORE J F. The death of competition：Leadership and strategy in the age of business ecosystem［M］. Boston：John Wiley & Sons Ltd， 1996.

［10］ HE Y， LIU J H， YANG R H. Survey on artificial bee colony algorithm［J］. Application Research of Computers， 2018， 35（5）：1281-1286.

［11］ 周蓉， 沈維蕾， 刘明周， 等. 带时间窗装卸一体化车辆路径问题的混合离散粒子群优化算法［J］. 中国机械工程2016， 27（4）：494-502.

［12］ 何庆， 吴意乐， 徐同伟. 改进遗传模拟退火算法在TSP优化中的应用［J］. 控制与决策， 2018， 33（2）：219-225.

［13］ 夏小云， 庄鹤林， 杨火根， 等. 自适应大邻域搜索的人工蜂群算法求解带容量约束车辆路径问题［J］. 计算机集成制造系统， 2022， 28（11）：3545-3557.

［14］ 胡蓉， 李洋， 钱斌， 等. 结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题［J］. 自动化学报， 2022， 48（11）：1-18.

［15］ SBAI I， KRICHEN S， LIMAM O. Two meta-heuristics for solving the capacitated vehicle routing problem：the case of the tunisian post office［J］. Operational Research， 2022， 22 （1）：507-549.

［16］ ZHANG D， CAI S， YE F， et al. A hybrid algorithm for a vehicle routing problem with realistic constraints［J］. Information Sciences， 2017， 394/395：167-182.

［17］ ALINAGHIAN M， GHAZANFARI M， NOROUZI N， et al. A novel model for the time dependent competitive vehicle routing problem：Modified random topology particle swarm optimization［J］. Networks and Spatial Economics， 2017， 17（4）：1-27.

［18］ GOEL R， MAINI R. A hybrid of ant colony and firefly algorithms （HAFA） for solving vehicle routing problems［J］. Journal of Computational Science， 2018， 25：28-37.

［19］ HE K， KEVIN T， NI F， et al. Adaptive large neighborhood search for solving the circle bin packing problem［J］. Computers & Operations Research， 2021， 127：105140.

［20］ 陈思远， 林丕源， 黄沛杰. 指针网络改进遗传算法求解旅行商问题［J］. 计算机工程与应用， 2020， 56（19）：231-236.

Abstract：To address the problems of traditional genetic algorithms in solving vehicle routing problems with time window （VRPTW）， which are easy to fall into local optimum and the solution quality is not high， this paper focuses on the genetic algorithm based on adaptive large neighborhood search to solve vehicle routing problems with time window. By combining the adaptive large neighborhood search algorithm with the genetic algorithm， three removal operators and two reinsertion operators are designed as ALNS-GA to improve the local search capability of the genetic algorithm， and the initial population generation strategy is optimized. Meanwhile， to verify the effectiveness of the algorithm， traditional genetic algorithms and genetic algorithms based on large-scale neighborhood search （LNS-GA， LNS*-GA） are compared respectively， and VRPTW test cases on Solomon database are selected for experimental verification on Matlab R2016b. The experimental results show that the solution quality of ALNS-GA is higher than that of traditional genetic algorithms when the termination conditions are both 100 iterations， and the best values found by ALNS-GA are better than those of LNS-GA and LNS*-GA in most cases， and the average time taken by ALNS-GA is smaller than that of LNS-GA and LNS*-GA in all cases. Especially when the customer size is 100， the average time taken by ALNS -GA takes less time on average， and although the average value of a small number of cases is slightly higher than that of LNS-GA and LNS*-GA， on the whole， the speed and quality of ALNS-GA is better than that of LNS-GA and LNS*-GA in the search for the best performance， which indicates that after improvement， the local search ability of genetic algorithm is significantly improved， and it can effectively improve the application of genetic algorithm on vehicle path problems with time windows. The study has some innovations.

Key words：genetic algorithm； adaptive large neighborhood search algorithm； local search； vehicle routing problems with time windows