李斌成 何国强

摘 要：针对遗传算法求解带容量约束的车辆路径问题时，存在早熟收敛和易陷入局部最优的问题，提出了改进的遗传算法。该算法结合扫描算法思想将种群初始化进行改进，使种群从迭代之初就处于一种最优的状态，并改进了选择策略和交叉策略。通过标准测试算例验证可知，该算法求解结果同测试算例给出的当前最优值之间的偏差在-0.24%以内，且求解结果和稳定性均由于对比算法，为求解此类问题给出了更加有效的解决方案。

关 键 词：容量约束车辆路径问题;遗传算法;扫描算法;相似度;移民策略

一、引言

1959年，Dantzig et al.[1]和Ralphs et al. [2]提出了带容量约束的车辆路径问题（capacitated vehicle routing problem，CVRP），在物流配送和车辆调度问题中得到了广泛应用。目前，关于容量约束车辆路径的计算方法主要分三类：精确算法、启发式算法及智能优化算法。精确算法与启发式算法对于较大规模容量约束车辆路径问题求解比较困难，因此对容量约束车辆路径问题求解方法的研究主要集中在智能优化算法上，如遗传算法（GA）[3]、模拟退火算法（SA）[4]、蚁群算法（ACO）[5]。石兆[6]通过对智能优化算法求解容量约束车辆路径问题研究发现，禁忌搜索算法求解时间较短，但求解效果不稳定，禁忌规则也不易确定;模拟退火算法在牺牲时间的前提下可以计算得到相对满意的结果，但存在易陷入局部最优的缺陷;蚁群算法存在求解效率低，容易产生早熟收敛现象的问题。考虑到以上智能优化算法的缺点和不足，近年来许多学者采用改进的智能优化算法求解容量约束车辆路径问题。刘万峰、李霞通过引入四种局部搜索算子对求解结果进行可行性评估，提出利用快速多邻域迭代局部搜索算法（fast multi-neighborhood ILS，FMNILS）求解车辆路径问题，取得了很好的效果[7]。王文蕊、吴耀华针对车辆路径问题实际应用进行建模分析，按照地理区域的不同对客户进行划分，通过改进K均值聚类法对各区域配送线路进行聚类分析，从而将问题转化为小规模的旅行商问题，但该方法对于多阶段优化算法中的K均值聚类中心点的选择方法仍需改进[8]。姜婷提出了混合差分蜂群算法，通过采用全局最优解来指导邻域搜索策略来增强人工蜂群开发能力不足的缺点，并通过差分算法的交叉更新策略对所提出的算法进行了局部优化[9]，该算法缺点是求解稳定性较弱。

遗传算法是求解此类非确定性多项式（non-deterministic polynomial，NP）完全问题的一种有效的全局搜索算法。赵燕伟等考虑将两个采用不同遗传算子的种群进行协同优化来求解容量约束車辆路径问题，避免算法在迭代过程中发生早熟收敛现象，取得了很好的效果，双种群遗传算法具有并行特点，利用两个种群同时进行进化，采用交换种群间优秀个体的遗传信息来打破平衡状态，利于跳出局部最优[10]。Wang cand Lu通过对遗传算法进行优化操作，将扫描算法同遗传算法相结合提出了混合遗传算法，在增加种群多样性的同时提高了算法寻优能力[11]。Dorronsoro et al.将遗传算法的全局搜索能力同2-opt局部搜索能力相结合，提出了混合遗传算法来提高算法搜索性能[12]。本文在研究传统遗传算法求解车辆路径问题时，存在早熟收敛、易陷入局部最优及求解结果依赖初始种群等缺点，提出了改进遗传算法（improved genetic algorithm，I-GA）求解容量约束车辆路径问题。

二、建立模型

本文所研究的是容量约束车辆路径问题，这类问题是指存在一个配送中心且拥有多台配送车辆，为多个客户点进行货物的配送工作，在满足客户点需求的基础上对客户配送次序及线路进行合理安排，使得总的配送里程或者配送费用最小。

设有向图G=（V，E），V={0}∪V0表示所有节点的集合，0表示配送中心，V0={1，2，…，m}表示客户点集合;E={（i，j）|i，j∈V}表示边集合;cij表示客户节点i和j之间的配送成本，由两节点间的距离决定;k={1，2，…，K}表示配送中心可用车辆集合，为同类型车，最大载重为Q;di表示客户i的需求量;xijk为二元决策变量，取值为1表示车辆k从节点i到节点j，否则取值为0;yik为二元决策变量，取值为1表示客户点i由车辆k服务，否则取值为0。

式（1）表示总成本最小的目标函数;式（2）表示配送车辆载重约束，配送车辆所服务的客户需求不大于车辆载重约束;式（3）表示每个客户有且仅有被一辆配送车辆所服务;式（4）表示相同节点之间无连通路径;式（5）表示一辆配送车辆仅服务一条路径，从配送中心出发服务完客户后，最后又返回配送中心;式（6）表示保证每个客户都被服务;式（7）和式（8）表示保证客户被配送车辆服务时，一定存在与其相连的路径;式（9）表示消除子回路;式（10）表示决策变量取值[13]。

三、改进遗传算法

传统遗传算法在求解容量约束车辆路径问题时，随着迭代次数的递增，种群多样性急剧递减，因为传统遗传算法随机生成初始种群，这造成了算法在寻优过程中存在早熟、收敛、陷入局部最优等问题。因此，文章考虑设计改进遗传算法来提高算法的寻优性能，在研究车辆路径问题特征基础上，结合扫描算法思想，对种群初始化进行改进，使算法在迭代之初就处在一个较好的状态。

（一）编码

假设客户点数目为N，配送车辆数为K，则该问题的编码可以表示为1～（N+K-1）的一个自然数序列。1～N表示客户点数，N+1～（N+K-1）表示线路的分割点，利用分割点对线路进行分割，即可得到K辆车各自的配送路径。

（二）种群初始化

扫描法进行种群初始化的思想是利用配送中心和任意客户点之间的一条射线对所有客户点进行顺时针或者逆时针扫描，通过车辆容量约束判定是否形成一条配送子路径，并在该子路径后加入分割符号，以此类推，直到所有客户点都扫描结束，形成一套完整的配送方案，将其作为遗传算法的一条染色体，重复这个过程，直到产生种群数量NP的染色体为止。为了使得初始种群在最初就保持一种最优状态，采用最近邻插入法对每条染色体各子路径进行顺序调整，达到配送子路径内部有序的目的。

1.构建初始种群

种群初始化具体流程如下。

Step 1：计算所有客户点与配送中心之间的正切值，并按照升序进行排列;

Step 2：从中随机选择一个正切值作为初始扫描射线，进行顺时针扫描;

Step 3：累计扇形区域内所覆盖的客户点需求之和，直到满足配送车辆容量后停止扫描，形成一个配送的客户群;

Step 4：以原射线末位置为起始位置重复上述过程，直到扫描完所有客户点为止，将生成的各子路径进行连接，中间采用分隔符进行分割，即形成一条染色体;

Step 5：将射线偏移一个角度后，重复Step 2～Step 5步骤产生其他染色体，直到生成种群规模NP的染色体时结束，如图1所示。

2.最近邻插入法

采用最近邻插入法对每条染色体内部各子路径进行顺序调整，基本流程如下。

Step 1：取配送中心0点为线路的起始点;

Step 2：依次选择一条染色体中的子路径，子路径中寻找客户点l，使得c0l值最小，从而构成该子路径中的一条局部线路0-l-0;

Step 3：从该子路径客户点中，寻找不属于Step2中局部线路的客户点并离该局部线路最近的k点;

Step 4：在局部线路上寻找使得cik+ckj-cij最小的弧线（i，j），将点k插入（i，j）之间;

Step 5：重复Step 2～Step 4，直到该子路径上所有客户都被访问为止;

Step 6：进行该染色体下一子路径各客户点顺序调整，直到所有子路径均调整完成后，重复上述过程，选择另一条染色体进行其子路径顺序调整。

（三）适应度函数计算

在算法开始迭代前，对种群中每一条染色体Gej进行解码操作，对解码完成后的各子路径进行车辆容量约束的判断，若存在子路径超出车辆容量约束，则该染色体Gej对应的解为不可行解，对该染色体的目标函数赋值一个有限的整数M0作为惩罚值，降低该染色体遗传到下一代的概率。根据式（1）计算目标函数值F（Gej），最后根据式（11）计算适应度函数值。

（四）遗传算子

周明在过往研究中给出了模式的定义，即它描述了在某些位置上具有相似结构特征的个体编码串的一个子集[14]。因此，通过改进种群初始化得到的种群中，对偏移一个正切值的相邻染色体而言，两分隔符之间具有相似的配送客户群，亦即具有相似的模式。考虑到初始化种群得到的个体已经是满足车辆容量约束的较优状态，为尽可能不破坏个体間的模式，文章设计了新的选择和交叉策略进行局部搜索。

1.选择策略

首先，利用非线性轮盘赌策略任意选择一个个体abi;然后，通过个体相似度值来进行个体之间相似性的评价，选择与个体abi相似性最大的个体abj进行后续的交叉操作。

（1）轮盘赌选择

文中选择算子采用沈斌、周莹君、王家海过往研究中具有良好鲁棒性的非线性排序轮盘赌策略，可以克服算法过早收敛[15]。将种群的染色体适应度值从小到大进行排序，并按式（12）分配概率。为了加快收敛速度，采用精英保留策略，即种群中的最优个体以概率1被复制到下一代。将分配给个体的选择概率按从大到小排序，求出每个个体的累积概率即个体自身选择概率与排在它之前个体的概率的累积和，然后产生一个随机数，通过它落入那个累计选择概率的区域而选择相应的个体，式（13）为累计概率公式。

交叉运算是指通过选择策略选出的两个配对个体按照某种方式互相交换其部分基因，从而形成两个新个体的过程。考虑到改进种群初始化个体之间的相似性，设计了改进的均匀交叉算子。改进均匀交叉算子（improved uniform crossover）是指两个配对个体的每一个基因座上的基因都以相同的概率进行交叉，然后对个体中重复的基因进行冲突检测和替换，从而产生两个新的个体。具体操作过程如下。

Step 1：通过选择策略得到两个个体A和B作为父代个体，如图2所示。

Step 2：随机生成一个同个体编码同维的屏蔽字段W=w1，w2，w3，…，wi，…，wl，其中l表示个体的维数，如图3所示。

Step 3：若wi=0，则新个体A′的第i个基因座上的基因值继承A对应的基因值，新个体B′的第i个基因座上的基因值继承B对应的基因值;若wi=1，则新个体A′的第i个基因座上的基因值继承B对应的基因值，新个体B′的第i个基因座上的基因值继承A对应的基因值，交叉后个体如图4所示。

Step 4：检测冲突基因，根据交换的两组基因建立一个映射关系，如图4所示，以1-6-3这一映射关系为例，从Step 2中能够发现交换后的预子代1中存在两个基因1，这时将预子代1中被选中部分的基因1通过映射关系转换为基因3，依次类推，将预子代中的所有冲突基因进行转换。

最后形成一对新的无冲突子代染色体A″和B″，结果如图6所示。

3.变异策略

变异运算是产生新个体的辅助方法，这也是遗传算法运算过程中不可或缺的，可以改善遗传算法局部搜索能力及维持种群的多样性。文中采用两点交换变异策略，通过随机的方式，在染色体中选择两个不同位置的基因，将它们的基因进行交换。

（五）移民策略

遗传算法在进化过程中，种群中的个体会趋于相似，种群的多样性会急剧下降，产生了遗传算法早熟收敛现象，算法过早地收敛于局部最优解，此时，交叉和变异操作很难使得算法跳出局部最优解。为了改变算法的早熟收敛现象，通过设定阈值判定当算法达到早熟收敛状态时，采用“移民策略”引入外部个体，替换部分适应度值较大的个体，以此打乱群体结构来增加种群多样性，从而进一步增强种群搜索能力。由于种群多样性的减少主要体现在群体间个体适应度值的接近程度上，即种群适应度值方差的降低，为了简化计算，利用公式（15）计算适应度方差，当E小于某一阈值时，可认为算法存在早熟收敛现象，可对其进行“移民策略”操作，阈值的取值通过算例测算后获得。

四、算例驗证及结果分析

本文选取容量约束车辆路径问题算例集中的SetA、SetB、SetE、SetP部分算例对改进遗传算法（I-GA）进行测试。实验环境为CPU∶2.50GHz;开发环境：MATLAB R2015b;在Intel（R） Core（TM） i5-2450M CPU@2.5GHZ、4GB RAM计算机和Windows7平台上运行。算例参数设置为：种群规模NP等于所求算例的规模数;迭代次数为MaxGen=1000;种群交叉概率PcA=0.9;种群变异概率PmB=0.1;早熟收敛判断阈值经测算，取值为E=1.0e-14，不满足约束个体的适应度函数惩罚值M0=50。图7给出了改进遗传算法求解算例E-n22-k4和A-n32-k5的配送线路图以及进化迭代曲线。

实验1 分别选取容量约束车辆路径问题测试集SetA三个算例及SetP中的6个算例，表1给出了对比算法CRO [16]和本文的设计算法。每个算例重复计算20次，其中BKR表示标准测试算例给出的当前最优解，Best、Worst、Average分别表示对应算法计算得到的最好值、最差值和均值，Dev表示计算结果同最优值的偏差（Dev=（BKR-Best）/BKR×100%）。

由表1对比结果分析可知：CRO可以求出Set-A和Set-P中9个算例中的4个最优值，与最优值的平均偏差为-1.44%;本文设计的改进遗传算法能够求出9个算例中的7个最优解，与最优解平均偏差为-0.24%。在求解精度方面，本文改进遗传算法求解结果同最优值BKR的偏差明显小于对比算法CRO所计算结果，并且改进遗传算法能够求解到最优解的比例更高，求解稳定，优于所对比的算法。

实验2 选取容量约束车辆路径的Set-A算例集中的5个算例，表2给出了对比算法CO-HS [17]和本文设计算法I-GA的计算结果，每个算例重复计算20次，表2中符号含义同表1。

由表2对比结果可知：CO-HS没有求解出Set-A算例集中5个算例的最优值，与最优值的平均偏差为-2.57%;本文改进遗传算法能够求出5个算例中的5个最优解，与最优解平均偏差为0.00%。在求解精度方面，本文改进遗传算法求解结果与最优值的偏差明显小于对比CO-HS所计算结果，并且改进遗传算法能够求解到最优解的比例更高，求解稳定，优于所对比的算法。

实验3 选取容量约束车辆路径的Set算例集中的9个算例，表3给出了对比算法Flag-MCS-CWS [18]和本文设计改进遗传算法的计算结果，每个算例重复计算20次，表3中符号含义同表1。

由表3对比结果可知：Flag-MCS-CWS求解出Set算例集中9个算例中的2个最优值，与最优值的平均偏差为-0.27%;本文改进遗传算法能够求出9个算例中的8个最优解，与最优解平均偏差为-0.05%。在求解精度方面，本文改进遗传算法求解结果与最优值的偏差明显小于对比Flag-MCS-CWS所计算结果，并且改进遗传算法能够求解到最优解的比例更高，求解稳定，优于所对比的算法。

以上计算结果表明，改进遗传算法不仅可以有效求解容量约束车辆路径问题，相比于对比算法而言，具有良好的鲁棒性。由此可见，本文提出的改进遗传算法为求解容量约束车辆路径问题提供了一个很好的思路。

五、结论

本文提出改进遗传算法求解容量约束车辆路径问题。针对容量约束车辆路径问题的相关特性，改进遗传算法采用扫描法思想改进初始化种群，并结合种群初始化改进了遗传算法的选择策略和交叉策略，在算法迭代后期判断其早熟收敛现象，据此引入外部种群来增强种群的多样性。实验结果表明，改进遗传算法求解容量约束车辆路径问题时具有良好的求解精度和收敛速度，为遗传算法求解此类问题提供了一定的参考。同传统遗传算法相比，由于对初始种群进行设定缘故，改进遗传算法在算例求解过程中结果更加稳定，后续研究还需在求解精度及时间复杂度方面做进一步改进。

参考文献：

[1]DANTZIG G B，RAMSER J H.The truck dispatching problem[J].Management science，1959，6（1）：80-91.

[2]RALPHS T K，KOPMAN L，PULLEYBLANK W R，et al.On the capacitated vehicle routing problem[J].Mathematical programming，2003，94（2-3）：343-359.

[3]VIDAL T，CRAINIC T G，GENDREAU M，et al.Implicit depot assignments and rotations in vehicle routing heuristics[J].European journal of operational research，2014，237（1）：15-28.

[4]PRADHANANGA R，TANIGUCHI E，YAMADA T，et al.Environmental analysis of pareto optimal routes in hazardous material transportation[J].Procedia-social and behavioral sciences，2014，125（1）：506-517.

[5]NARASIMHA K V，KIVELEVITCH E，SHARMA B，et al.An ant colony optimization technique for solving min–max multi-depot vehicle routing problem[J].Swarm & evolutionary computation，2013，13（complete）：63-73.

[6]石兆.物流配送选址——运输路径优化问题研究[D].长沙：中南大学，2014.

[7]刘万峰，李霞.车辆路径问题的快速多邻域迭代局部搜索算法[J].深圳大学学报（理工版），2015，32（2）：196-204.

[8]王文蕊，吴耀华.带实际约束的大规模车辆路径问题建模及求解[J].控制与决策，2013，28（12）：1799-1804.

[9]姜婷.混合差分蜂群算法求解带容量约束车辆路径问题[J].宜宾学院学报，2017，17（12）：52-56.

[10]赵燕伟，吴斌，蒋丽，等.车辆路径问题的双种群遗传算法求解方法[J].计算机集成制造，2004，10（3）：303-306.

[11]WANG C H，LU J Z.A hybrid genetic algorithm that optimizes capacitated vehicle routing problem[J].Expert systems with applications，2009，36（2）：2921-2936.

[12]DORRONSORO B，ARIAS D，LUAN F.A grid-based hybrid cellular genetic algorithm for large scale instances of the CVRP[C]// 2017 International Conference on High Performance Computing & Simulation.Genoa：Institute of Electronics Engineers，2007：759-765.

[13]李阳，范厚明.求解带容量约束车辆路径问题的混合变邻域生物共栖搜索算法[J].控制与决策，2018，33（7）：1190-1198.

[14]周明.遗传算法原理及应用[M].北京：国防工业出版社，1999.

[15]沈斌，周莹君，王家海.基于自适应遗传算法的Job-Shop调度问题研究[J].计算机应用，2009，29（S2）：161-164，188.

[16]蔣海青，赵燕伟，冷龙龙.基于化学反应优化算法的车辆路径问题[J].计算机集成制造系统，2018，24（8）：2012-2022.

[17]颜腾威，王丽侠，周杰，等.求解CVRP问题的改进和声算法[J].计算机技术与发展，2016，26（9）：187-191.

[18]夏茂庚，郑阳光，兰延涛，等.有容量约束车辆路径问题的蒙特卡洛模拟算法[J].科学技术与工程，2012，12（26）：6849-6852.