基于混合自适应遗传算法的路径规划研究

程元栋，杨齐威

基于混合自适应遗传算法的路径规划研究

程元栋，杨齐威

（安徽理工大学 经济与管理学院，安徽 淮南 232000）

为解决供应商管理库存（VMI）模式下带时间窗的车辆路径规划（VRPTW）问题，综合考虑多种条件建立了具有多目标约束的数学模型，并创新性提出混合式自适应遗传算法，该算法在自适应遗传算法（AGA）的基础上加入了节约算法构造种群的初始解，引入了随机遍历抽样法进行选择操作，改进了算法的交叉方式，最后运用大规模邻域搜索法（LNS）对变异后的种群进行破坏和修复操作。通过MATLAB软件进行仿真实验，与传统自适应遗传算法进行对比，运输成本显著性降低了50%，据此得出该混合式自适应遗传算法在解决VRPTW问题时具有更强更科学的全局搜索和快速收敛的能力，以期更高效合理地优化供应商车辆配送路径规划。

供应商管理库存；节约算法；自适应遗传算法

VMI模式是供应链管理大环境下上下游企业紧密合作产生的一种运作方式，主要是供应商通过对下游企业销售资料的分析进行原材料配送，抑制“牛鞭效应”，达到“零库存”效果。而在供应链管理库存模式下带时间窗约束的路径规划一直是一个热门问题，因为高效合理的线路规划能提高配送效率及合作的紧密性，降低成本，对企业来说具有重大意义。

近年来对VMI模式和VRPTW问题有很多学者进行了大量的深入研究，在针对VMI模式的研究中，康凯等[1]通过建立Stackelberg博弈模型分析了库存补贴及零售商预付款策略的适用范围和对供应链绩效的影响，对提高资金受限的供应链整体绩效有很大的意义；刘云志等[2]利用不公平厌恶模型分析了模糊需求下考虑供应商存在偏好的二级VMI供应链协调问题；罗岭[3]通过建立带有库存成本变化的EOQ模型研究了受库存成本变化的VMI系统的最优协议问题等，解决了库存成本变化下如何实现VMI供应链协调的问题。而在解决VRPTW问题方面大多数学者采用了一些启发式算法从优化的角度进行研究，其中李珍萍等[4]利用Gurobi求解器对算例进行求解，表明了VMI模式下配送线路有效规划能够降低库存和配送成本，并利用贪婪算法与Gurobi求解器对比，证明了贪婪算法能够在最短的时间内得到较优的配送路线规划方案；LI等[5]提出了一种由贪婪算法改进的禁忌搜索算法（improved tabu search, I-TS）来解决具有软时间窗和随机出行服务时间的车辆路径问题，并用实例验证了其优越性；FAZI等[6]将贪婪算法与局部搜索法相结合构建了一种混合局部搜索元启发式算法用来解决海上集装箱驳船运输问题；刘辉[7]、朱永强[8]和SONG[9]等在蚁群算法的基础上进行了改进，使改进后的蚁群算法在路径规划寻优能力上有了较大的提升；胡卉等[10]提出了一种带有回火与缓冷操作的改进模拟退火算法对受推动式生产调度影响的物资配送规划模型进行求解，对比传统的模拟退火算法结果更稳定且更好；裴时域[11]、CRUZ-CHÁVEZ[12]等也将改进后的模拟退火算法分别运用到物流配送中心选址和调度问题中，提供了新的解决方案；综上所述，虽然针对VMI模式和VRPTW问题学者们已经进行了大量研究，但针对VMI模式下车辆配送路径规划方向的研究少之又少；为此本文预建立一种具有碳排放成本、时间窗和容量约束等多目标约束的线性规划模型，并提出了一种混合式自适应遗传算法，该算法相比传统启发式算法优化了初始解随机性大、算法全局搜索能力差、容易陷入局部最优解的困局等问题，经验证具有很好的使用效果。

1 模型建立

1.1 问题描述

基本假设：

VRPTW问题是一个NP-Hard问题，为简化问题，作出以下假设：

（1）车辆从供应商出发，完成任务后空载返回供应商；

（2）单个顾客的需求量由单车辆配送且一次性满足需求；

（3）车辆的运输成本与车辆行驶距离系线性相关；

（4）单条线路的最大需求量不大于单辆车的最大载重量；

（5）车辆在配送过程中匀速行驶，不受其他条件影响；

（6）车辆返回供应商的时间不能超过供应商要求完成服务的终点时刻。

1.2 参数定义

相关参数定义：

决策变量：

1.3 模型构建

2 算法设计

2.1 相关算法概述

2.1.1 自适应遗传算法

遗传算法（genetic algorithm, GA）是John Holland受物种进化原理启发产生的一种优化方法，原理是在种群进化中，只有适应能力强的个体才会遗传下去。AGA是基于传统遗传算法固定的遗传算子在种群进化期初能有效筛选较差个体，但随着种群进化，后期同样会对较好的解产生破坏，从而导致算法收敛速度慢，易“早熟”的现象提出的一种改进算法，AGA能够在种群迭代中自适应的调节交叉和变异概率，极大提高了算法收敛的速度。

2.1.2 节约算法

节约算法是Clarke和Wright提出的一种以最短运输里程为目标的路径规划方法，又称C-W算法，原理是在满足用户到货时间要求和车辆载重要求前提下，通过路径的合并使配送总路径距离减小的幅度最大，是一种解决车辆合理调配的启发式算法。

2.1.3 大规模邻域搜索法

LNS算法是局部搜索法的一种，主要是运用Destroy和Repair的思想，利用Removed和Re-inserting方式随机选择几个配送点对线路进行破坏，将选择的配送点从线路里面拿掉，剩下的配送点依次排序保存，然后再用修复的方法将选择出的配送点随机插入被破坏的线路中，从中选出最好的解。破坏方法通常包含随机性的元素，以便在每次调用破坏方法时破坏线路的不同部分。

2.2 混合自适应遗传算法

为解决VMI模式下VRPTW问题，本文创造性提出了一种混合自适应遗传算法（CW-AGA-LNS），具体流程如图1所示。该算法首先引入了节约算法来构造符合时间窗和载重容量约束的遗传算法初始解，降低了遗传算法随机生成初始解的随机性，使算法能够快速收敛；然后引入具有自适应的交叉变异概率的AGA，提高进化前期的搜索能力和后期的收敛速度；最后引入了LNS算法，对交叉变异后的结果进行破坏和修复操作后进行局部搜索，进一步提高算法的全局寻优能力。

图1 CW-AGA-LNS算法流程图

2.2.1 编码

2.2.2 构造种群初始解

采用C-W算法构造种群初始解：

步骤1 将所有顾客与供应商相连，只含有一个配送起点，计算总费用；

步骤2 将路径融合后的距离节约值降序排列，节约值越大，说明并线后路程节约越多；

步骤3 如果线路周围还有其他客户，在满足时间窗和载重约束下按照里程节约大小插入巡回路线，直到不能融合为止；

步骤4 以同样的方法融合第二条线路；

步骤5 判断是否还存在只有一个顾客的线路，如果有，重复上述步骤，否则输出每条线路的顾客序列号。

2.2.3 计算种群适应度

2.2.4 选择操作

图2 随机遍历抽样选择法示意图

2.2.5 自适应交叉和变异操作

在GA中交叉概率P和变异概率P是衡量算法性能的关键性指标，P值越大，新染色体产生速度就越快，但过大时会破坏整个遗传模式，P过小会使整个搜索过程进程缓慢；而P值越大，对优质解的破环概率越大，P过小时产生新的染色体结构概率较小。本文采用的是任子武等[13]改进后的自适应交叉变异概率，如式(16)和式(17)所示。

（1）交叉操作。采用改进的OX交叉方式，具体操作如图3所示。原理是在待交叉两条染色体上随机产生两个交叉位点，将交叉位点的个体提出来放在另一个染色体的前面和后面，然后删除交叉片段外的重复片段。改进后的交叉方式在面对两个同样的待交叉染色体也能产生新的子代个体，对保持种群的多样性有一定作用。

图3 改进OX交叉流程图

图4 变异操作流程图

2.2.6 局部搜索操作

（1）Removed操作。随机选取个顾客，将其从所有顾客中逐一摘选出来，具体过程为：

步骤1 随机选择一个顾客，将其从原顾客集中移除出来，保存到被移除顾客集合之中；

步骤2 计算该被移除顾客与剩余其他顾客的相关性值；

步骤3 将剩余顾客按照与被移除顾客的相关性值大小从高到低排列，再从中随机选取下一个顾客移除出来，重复上述操作，选出个顾客为止；

步骤4 保存被移除顾客合集和剩余顾客的排序。

（2）Re-inserting操作。将被移出的所有顾客重新插入到各个线路中去，采用最远插入启发式，即将最小插入距离增量最大的元素找出来；首先找出满足时间窗和载重约束的所有插入点，再计算所有插入点的距离增量；然后找出各顾客距离增量最小的最佳插入点，并记录距离增量；最后将对应距离增量最大的顾客插入到所在位置。该循环需要进行次，直到所有被移出的顾客全部插入各条线路中。

2.2.7 终止操作

当种群迭代次数达到最大值时，结束循环操作，输出最终解。

3 算法仿真

为有效验证CW-AGA-LNS算法在求解VRPTW问题的可行性和有效性，本文运用MATLAB R2018a软件并采用综合算例对比分析和具体算例对比分析的方式进行算例验证。

3.1 测试算例介绍

本文采用Solomon在研究VRPTW问题提出的Solomon案例集进行验证。该案例集每个案例包括客户的坐标集、接受服务的时间窗、客户点需求量、车辆最大载重和最大使用车辆数等，同时分为R、C、RC三种类型，每种类型又分为两种系列，具体特点为R型算例客户坐标点由均匀分布产生，C型算例客户坐标集由结构性分布产生，RC型算例是二者的混合分布形式。其中具体系列特征如表1所示。

表1 Solomon案例集典型算例特征

3.2 综合算例对比分析

根据多次验证结果，算法具体参数为种群规模为150，最大迭代次数为600代，自适应交叉和变异概率借鉴文献[13]多次试验结果设定为P10.9,P20.6, P10.1,P=0.01。

选取Solomon算例集中几个典型类型的数据分别用AGA和CW-AGA-LNS算法进行分别多次验证进行横向对比，具体结果如表2所示，可以看出无论面对何种类型的客户，CW-AGA-LNS所得出的结果都明显优于AGA，从各个算例达到迭代最优解的迭代代数可以看出后者收敛速度较慢，容易陷入“早熟”。

表2 算法横向对比结果

3.3 具体算例对比分析

为了具体体现CW-AGA-LNS算法的性能，减少误差，分别利用AGA和CW-AGA-LNS算法对C105案例进行多次求解求平均值，将两种算法进行纵向对比分析。根据C类型算例的多次验证结果，C类型算例无论是CW-AGA-LNS或AGA都能在迭代200代以内得到最优结果，所以此时算法的具体参数可以设置为种群规模为150，最大迭代次数为200代，P10.9,P20.6, P10.1,P=0.01。

将两种算法生成的种群初始解进行对比，如表3所示。结果表明，C-W算法产生的种群初始解与随机遍历生成的初始解相比总行驶里程和成本更低，且不存在违反约束的现象，降低了遗传算法随机生成初始解的随机性，使算法能够快速收敛。

表3 AGA和CW-AGA-LNS算法初始解对比

图5和图6是AGA和CW-AGA-LNS算法最终的里程迭代图，二者对比可以明显看出后者算法初始解适应度值较小，收敛速度明显更快，在进行第10次迭代时就达到了最优解，而前者的初始解适应度值比较高，在第47次迭代才达到最优解。而且从迭代图的曲线拐点多少也可以看出前者拐点更多，表明其寻优过程中陷入局部最优解的次数更多。

图5 AGA里程迭代图

图6 CW-AGA-LNS里程迭代图

两种算法最终结果对比如表4所示，可以看出CW-AGA-LNS比AGA最终结果所使用车辆的数目、行驶里程和总成本都要少且差别显著，前者效果更优。

表4 AGA和CW-AGA-LNS算法最终结果对比

3.4 结果对比

通过综合算例和具体算例的对比分析可以得出无论顾客分布属于何种类型，本文提出的CW-AGA-LNS都能很好地解决问题，并且相比传统的AGA结果更优秀，收敛速度快，陷入局部最优的次数更少；Solomon案例集几乎涵盖了所有的客户分布和需求类型，从各类型算例验证结果也可以表明CW-AGA-LNS比AGA收敛速度快，陷入局部最优的次数更少的结论并非偶然。这是因为CW-AGA-LNS在初始解生成时能够极大地降低初始解的随机性，并且经过改进交叉方式和局部搜索的操作能够加快算法收敛速度，增加算法的全局搜索能力。由此可见本文提出的CW-AGA-LNS在解决此类问题上更具实用性。

4 结论

本文主要是针对VMI模式下供应商配货路径规划所遇到的VRPTW问题进行研究，建立了满足多种约束条件的数学模型，并基于自适应遗传算法提出了一种混合式自适应遗传算法对模型进行求解，通过MATLAB软件将该算法与传统自适应遗传算法进行对比验证，得出该算法在解决此类VRPTW问题中效果更好，具有生成种群初始解的随机性低，算法跳出局部最优能力强，全局搜索能力强，收敛速度快等优点且结果相比AGA效果更优。但该研究也有一些不足之处，首先在实际情况中，供应商在配货路径规划上还会受到很多其他因素的影响，比如实时路况及车辆满载情况对车辆速度和燃油的影响、实际线路距离可能比欧氏距离要短等，本文所建立的数学模型有待改善；其次，从仿真过程中可以发现加入了局部搜索操作虽然会增加算法的搜索能力，但也会导致算法运行时间较长。这些都需要我们进一步的研究。

[1] 康凯，高思颖，穆秀清. 基于VMI供应商资金受限的供应链协调策略[J]. 计算机工程与应用，2020, 56(14): 264-271.

[2] 刘云志，樊治平. 模糊需求下考虑供应商公平偏好的VMI供应链协调[J]. 系统工程理论与实践，2016, 36(07): 1661-1675.

[3] 罗岭. 库存成本变化的VMI供应链协调[J]. 中国管理科学，2022, 30(10): 187-197.

[4] 李珍萍，焦鹏博. 基于供应商管理库存模式的配送路径优化问题[J]. 科学技术与工程，2021, 21(26): 11362-11367.

[5] LI G M, LI J H. An improved tabu search algorithm for the stochastic vehicle routing problem with soft time windows[J]. IEEE Access, 2020, (8): 158115-158124.

[6] FAZI S, FRANSOO J C, VAN WOENSEL T, et al. A variant of the split vehicle routing problem with simultaneous deliveries and pickups for inland container shipping in dry-port based systems[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 142: 102057.

[7] 刘辉，肖克，王京擘. 基于改进蚁群算法的无人矿车路径规划研究[J]. 制造业自动化，2021, 43(04): 108-112.

[8] 朱永强，孙宗涛. 改进蚁群算法在物流机器人路径规划中的应用[J]. 科学技术与工程，2020, 20(30): 12467-12471.

[9] SONG B Y, MIAO H M, XU L. Path planning for coal mine robot via improved ant colony optimization algorithm[J]. Systems Science & Control Engineering, 2021, 9(1): 283-289.

[10] 胡卉，刘富鑫，王愚勤，等. 基于改进模拟退火算法的推动式生产-配送协调优化[J]. 运筹与管理，2022, 31(02): 15-22.

[11] 裴时域，李元香. 改进的模拟退火算法在物流配送中心选址中的应用[J]. 统计与决策，2021, 37(09): 172-176.

[12] CRUZ-CHÁVEZ M A, PERALTA-ABARCA J C, CRUZ-ROSALES M H. Cooperative threads with effective-address in simulated annealing algorithm to job shop scheduling problems[J]. Applied Sciences, 2019, 9(16): 3360.

[13] 任子武，伞冶. 自适应遗传算法的改进及在系统辨识中应用研究[J]. 系统仿真学报，2006(01): 41-43, 66.

Research on path planning based on hybrid adaptive genetic algorithm

CHENG Yuan-dong，YANG Qi-wei

(School of Economics and Management, Anhui University of Science and Technology, Anhui Huainan 232000, China)

To solve the vehicle routing problem with time window in vendor managed inventory mode, a mathematical model with multi-objective constraints is established considering various conditions, and a hybrid adaptive genetic algorithm is innovatively proposed. The hybrid adaptive genetic algorithm is based on the adaptive genetic algorithm, which adds the saving algorithm to construct the initial solution of the population, introduces the random traversal sampling method for selection operation, improves the crossover method of the algorithm, and finally uses the large neighborhood search to search for the variance. Finally, the large-scale neighborhood search is applied to destroy and repair the mutated population. The simulation experiments were conducted by MATLAB software, and the transportation cost was significantly reduced by 50% when compared with the traditional adaptive genetic algorithm. Accordingly, it was concluded that the hybrid adaptive genetic algorithm has stronger and more scientific global search and fast convergence capability in solving the VRPTW problem, in order to optimize the supplier vehicle distribution path planning more efficiently and reasonably.

vendor managed inventory；saving algorithm；adaptive genetic algorithm

2022-08-16

国家自然科学基金项目（71473001）；研究生创新基金项目（2022CX2159）

程元栋（1979-），男，山东泰安人，副教授，博士，主要从事物流系统工程研究，Andoncheng@foxmail.com。

杨齐威（1996-），男，河南周口人，硕士，主要从事配送路径优化研究，23606116@qq.com。

TP301.6

A

1007-984X(2023)01-0087-08