聚类蚁群混合算法求解CVRP

Cluster ant colony hybrid algorithm for solving CVRP

摘要

针对带容量约束的车辆路径问题，提出了一种聚类蚁群混合算法，将车辆路径问题拆分成数个旅行商问题进行求解。首先，改进了蚁群算法中信息素和路径的生成方式，使其能够对车辆路径问题进行有效的拆分求解；然后通过对种群进行分级，加快了蚁群算法的收敛速度，并设置3种邻域搜索算子来避免蚁群算法陷入局部最优；最后，设计了仿真实验对算法的部分参数进行合理设计，选取50个Solomon基准算例对算法进行实验验证。实验结果表明，算法收敛速度快，稳定性较高，求解结果较好。

关键词

车辆路径问题 / 容量约束 / 聚类分析 / 改进蚁群算法 / 信息素 / 邻域搜索

Key words

vehicle routing problem / capacity constraints / cluster analysis / improved ant colony algorithm / pheromone / neighborhood search

随着电子商务的快速发展，物流行业也飞速发展，我国物流总费用占GDP的比重远高于发达国家，降低我国物流成本具有十分重要的意义。车辆路径问题（vehicle routing problem，VRP）的基本目标是在完成运输任务的情况下，尽可能降低物流运输成本。自1959 年车辆路径问题被提出后，学者根据现实情况发展了多个VRP分支。基础模型上的研究成果可以应用在大多分支问题上，因此，经典的CVRP仍是学者研究的重点^［1-2］。

随着数据规模与计算机计算能力的提升，学者们对VRP问题的研究更多采用启发式算法。经典的启发式算法有遗传算法^［3-4］、模拟退火^［5］、蚁群算法^［6-7］等。

蚁群算法在求解VRP上表现出很大的优势。陈迎欣^［8］通过引入搜索热区提高了蚁群的搜索效率，在一定程度上防止蚁群陷入局部最优。梁承姬等^［9］采用节约算法产生初始解，提高了蚁群算法的收敛速度，并使用最大最小蚂蚁系统在一定程度上弥补了蚁群算法容易陷入局部最优的缺陷。Thammano等^［10］使用扫描方法产生蚁群的初始解，并采用路径重链接的方式增加蚁群算法的搜索广度。

聚类分析 ^［11］是依据不同标准将总体中的个体进行分类，以便对问题进行更加深入的研究。VRP问题基于聚类的思维，将问题分解成若干个旅行商问题（traveling salesman problem，TSP）问题进行求解。但目前研究者在VRP问题上对聚类的应用较少，聚类与启发式算法结合较弱，基本只采用聚类分析来产生启发式算法的初始解。张潜等^［12］通过聚类进行初始分类，再使用遗传算法求解MVRP问题。李桃迎等^［13］通过k-means聚类进行初始分类，将商家-客户聚类后使用遗传算法对问题进行求解。赵雄等^［14］使用均值漂移聚类将客户进行分类后，使用贪婪算法对聚类后的分组进行求解得到初始解，而后在此初始解的基础上采用大邻域搜索算法求解异构VRP问题。

本文深度结合了聚类与蚁群算法，提出一种聚类蚁群混合算法。通过对CVRP中经典Solomon算例进行求解，验证了算法的有效性。

1 问题描述与数学模型

CVRP问题可以描述为：配送网络由一个配送中心及若干个客户点组成，已知各客户点的需求量以及配送网络各节点间的距离；安排若干辆同一型号的车辆从配送中心出发对客户进行服务，每个客户只能由一辆车服务且只能被服务一次，每辆车服务完成后需返回配送中心；求所有客户的需求都被满足而总行驶路程里程最短的配送方案。

记V=｛0，1，2，…，n｝为配送网络的节点集， 0代表配送中心，V_C =｛1，2，…，n｝表示客户集。配送网络中i点到j点的距离为d_ij。K为车辆集，Q为配送车辆的载重上限。q_i 为客户i的货物需求量且不超过Q。 X_{ij}^k为布尔变量，当车辆k由节点i行驶到j时， X_{ij}^k = \mathrm{1}；否则 X_{ij}^k = \mathrm{0}。CVRP数学模型如下。

\mathrm{m} \mathrm{i} \mathrm{n} F = {\displaystyle \sum _{i=\mathrm{0}}^n} {\displaystyle \sum _{j=\mathrm{0}}^n}{\displaystyle \sum _{k=\mathrm{1}}^m}{d}_{ij}{X}_{ij}^k （1）

s.t.

{\displaystyle \sum _{i=\mathrm{1}}^n} q_i{X}_i^k\le Q,\forall k\in K （2）

{\displaystyle \sum _{i=\mathrm{0}}^n} {\displaystyle \sum _{k=\mathrm{1}}^m}{X}_{ij}^k=\mathrm{1},\forall j\in V_c , k \in K （3）

{\displaystyle \sum _{j=\mathrm{0}}^n} {\displaystyle \sum _{k=\mathrm{1}}^m}{X}_{ij}^k=\mathrm{1},\forall i\in V_c , k \in K （4）

\begin{array}{ccc}{X}_{ij}^k\in \left\{\mathrm{0,1}\right\},\forall k\in K,\forall i,j\in V& & \end{array} （5）

式（1）为CVRP模型的目标函数，车辆总费用最少；式（2）为车辆容量约束，表示车辆不能超载；式（3）、（4）表示每个客户仅能被一辆车服务一次；式（5）表示决策变量取值约束。

2 聚类蚁群混合算法

蚁群算法中信息素矩阵由解的种群更新，而解的种群又根据信息素矩阵生成，相互影响迭代，形成正反馈循环，直至达到终止条件。因为这种正反馈关系，蚁群算法易陷入局部最优。聚类在VRP问题中的作用是对客户进行分组，再通过其他算法对聚类后的分组进行进一步求解，比如生成蚁群算法的初始种群。

本文算法将聚类思维贯穿始终，通过改进信息素与解的对应关系，深度融合聚类分析与蚁群算法，在每代种群生成时均进行聚类，信息素迭代是为了得到更好的聚类效果。

2.1 聚类蚁群混合算法

首先，生成一个大规模的初始种群来获取初始信息素矩阵，再以初始信息素矩阵为基础进行算法的迭代。每次迭代中，单个解的生成方式如下：先基于信息素矩阵进行聚类分组，再对每个分组进行TSP问题的求解，组合起来成为该CVRP的解，最后使用邻域搜索算子更新该解。当种群中解的数量达到种群规模，更新信息素矩阵及最优解情况。当达到终止条件时输出所得的最优解，聚类蚁群混合算法流程如图1所示。

2.2 初始种群的构造

设定初始车辆数等于总需求量除以车辆载货量，向上取整，而后随机为每辆车选择一个客户作为聚类中心，将剩余客户随机分配至可行车辆。若无可行车辆，则新增一个车辆，直至所有客户被分配完毕。客户分配完成后对每个分组，即每辆车进行TSP问题的求解，产生该次分组对应的CVRP问题的解。具体流程如下：

步骤1：设置初始车辆数为 c_{-} n = ⌈td/Q⌉，式中， t d = q_{\mathrm{1}} + q_{\mathrm{2}} + \cdots + q_n，为所有客户的总需求量；

步骤2：从客户集中随机抽取 c_{-} n个客户，分别将其分配至车辆 V_j , j = \mathrm{1,2} , \cdots , c_{-} n ,从客户集中删去这些客户；

步骤3：抽取客户集中的一个客户，将其随机分配至可行车辆，若无可行车辆则新增一车辆进行分配，分配完成后从客户集中删去该客户；

步骤4：重复步骤3直至所有客户均被分配；

步骤5：对每一个车辆进行TSP问题的求解，最终得出一个初始解；

步骤6：重复步骤1至步骤5，直至初始解数量达到初始解种群规模。

2.3 信息素矩阵的产生与更新

传统的蚁群算法求解CVRP时，信息素矩阵决定了车辆离开i点后去往的下一个节点j，相应的信息素矩阵的产生与迭代也只考虑路径中相连的两点i、j。在本文聚类蚁群混合算法中，信息素代表的是节点之间聚类联系程度。相应的，信息素矩阵的产生与迭代就要同时考虑到同一条路径内所有客户之间的关系。考虑到聚类需要一个聚类中心，因此对与车站相连的客户节点单独再计算一次其与车站的信息素。于是，每一个解对应的信息素矩阵产生方法如下所示：

步骤1：初始信息素矩阵为零矩阵，对解中的每个车辆进行步骤2与步骤3；

步骤2：信息素矩阵 P _0i 以及 P _i0 信息素增加量为tp/D_i，其中i为该车辆的路径中与车站相邻的两个客户；

步骤3：信息素矩阵 P _ij 以及 P _ji 信息素增加量为tp/D_i，其中i、j为该车辆的路径中去除车站后剩余的所有客户，i≠j。将种群中每一个解对应的信息素矩阵加起来就是种群对应的信息素矩阵。

在种群迭代过程中，蚁群算法通常采用式（6）进行信息素矩阵的迭代。

{\mathit{P}}^{\mathrm{n}\mathrm{e}\mathrm{w}} = ( \mathrm{1} - \rho ) {\mathit{P}}^{\mathrm{o}\mathrm{l}\mathrm{d}} + {\mathit{P}}^{\mathrm{t}\mathrm{h}\mathrm{i}\mathrm{s}} （6）

式中： {\mathit{P}}^{\mathrm{o}\mathrm{l}\mathrm{d}}是原有信息素矩阵；ρ为信息素衰退率； {\mathit{P}}^{\mathrm{t}\mathrm{h}\mathrm{i}\mathrm{s}}为本次种群的信息素矩阵。传统蚁群算法中蚁群中的蚂蚁携带的信息素完全相同，虽然这种方法在一定程度上增加了解的广度，但也降低了收敛速度。本文通过对解进行分级，对不同优劣程度的解分别设置信息素携带量，通过调整 {\mathit{P}}^{\mathrm{t}\mathrm{h}\mathrm{i}\mathrm{s}}使优解能更多地影响信息素浓度，从而使其更快收敛。

本文将解分为4个级别，分级判定条件及信息素携带量，如表1所示。

式中：D为当前最优解的总费用； D_i为该解的总费用；tp为蚁群算法中单只蚂蚁的信息素携带量的标准值。

2.4 新解生成方法

本文算法中依据信息素矩阵生成新解的具体方法如下：

步骤1：设置初始车辆数为 c_{-} n = ⌈td/Q⌉，其中 t d = q_{\mathrm{1}} + q_{\mathrm{2}} + \dots + q_n，为所有客户的总需求量；

步骤2： 通过式（7）的方法从客户集中依次选取 c_{-} n个客户作为聚类中心，分别将其分配至车辆 V_j , j = \mathrm{1,2} , \cdots , c_{-} n，从客户集中删去这些客户；

步骤3：抽取客户集中一个客户，利用式（8）为该客户选择聚类，即选择车辆。若无可行车辆则新增一车辆将其分配，该客户成为一个新的聚类中心。分配完成后从客户集中删去该客户。重复该步骤直至所有客户被抽取。

步骤4：对每一个聚类，即车辆进行TSP问题的求解，最终得出一个初始解

{\mathit{P}}_{ij} ( t ) = \frac{{\left[{\eta }_{ij}(t)\right]}^{\beta }{\left[{\tau }_{ij}(t)\right]}^{\alpha }}{\sum _{j\in A}{\left[{\eta }_{ij}(t)\right]}^{\beta }{\left[{\tau }_{ij}(t)\right]}^{\alpha }} （7）

（8）

式中： P _ij 和 \tau _ij 分别为i、j两点间的距离的倒数和信息素浓度；p为随机数；p ₁和p ₂为转移概率参数； \alpha为信息素浓度系数； \beta为距离浓度系数。

2.5 邻域算子设置

为克服蚁群算法容易陷入局部最优的问题，结合本文算法特色，设置如下3种邻域搜索算子。

算子1：基于本文算法产生解的原理，有些客户在分配时可选择的车辆内客户较少，导致在解生成完毕时，车辆内有部分客户与其他车辆的聚类相关性更高，因此设置算子1。通过对解中信息素情况进行判定，将一部分聚类分配较差的客户重新进行分配，得到更好的求解效果。

算子2：考虑到在某车辆容量较高时，算子1若只进行一次，则该车辆很难产生变化，解的搜索广度过低。因此一方面考虑增加算子1的重复次数，另一方面设置算子2，交换车辆V₁ 中的客户C_i 与车辆V₂ 中的客户C_j，增加邻域的广度。

算子3：考虑到本文算法初始解生成时采用随机选择每一车辆的初始客户，进而导致每辆车服务的客户数量比较平均，但最优解往往会有个别车辆服务的客户数量极少或极多，因此设置算子3。通过将某车辆V₁ 中的某个客户C_i 重新分配到其他车辆，获得一个更优解，从而避免本文算法的局限性。

3 仿真实验

仿真实验采用Solomon数据库中的算例，将本文算法的计算结果与库中已知最优解进行对比，达到验证本文算法有效性的目的。本文算法用Python实现，在Window11操作系统，处理器为Intel（R） Core（TM） i7-12700H 2.30GHz，16GB内存的电脑上运行。

3.1 参数设置

本文算法中主要的参数有以下6种：种群规模P、信息素衰退率ρ、转移概率P ₁、转移概率P ₂、转移函数信息素浓度系数α、转移函数距离浓度系数β。

取Solomon库中A、B组中具有代表性的6个案例，分别代表小规模、中等规模、较大规模情况下单车辆服务客户数较少和较多的情况，进行参数设置的实验，进而确定参数的选择。选取的算例及其相关数据如表2所示，CN代表案例客户数，CPC代表每辆车平均服务的客户数量。

共设置16组实验，参考此前的研究成果^{［9-10，15］}，结合实验效果调整各参数并运行程序求解表2中的6个案例，每个实验对每个案例求解15次，分析结果后确定参数。

最终选取蚁群算法参数情况如下：P=50、ρ=0.2、p ₁=0.2、p ₂=0.7、α=4、β=2。

本文算法终止条件设置为近似最优解R连续γ次不更新后终止。经过实验研究，最终设定γ=15。

3.2 实验设置

参数确定后，使用本文算法对Solomon库中A、B两组数据共50个案例进行求解，每个案例进行15次求解，得出最优解与平均解，并与数据库中已知最优解结果进行对比。所得结果如表3所示，其中BK为库中已知最优解，AVG为本文算法15次求解的结果平均值，BEST为本文算法求得的最优解。AVG与BK的相对误差计算公式为

Aer=（AVG-BK）/BK×100%（9）

BEST与BK的相对误差计算公式为

Ber=（BEST-BK）/BK×100%（10）

3.3 实验结果分析

实验结果如表3所示。由实验结果可得，本文算法在11个算例上得出了与当前已知最优解相同的结果，在两个算例上获得了距离上更优但车辆数增加的解。另外，在13个算例中得到了与已知最优解差距不超过1%的结果。在剩余算例中，除算例A-n69-k9外，本文算法在其他算例上所得结果与最优解的差距均不超过4%，证明了本文算法在求解CVRP问题时的有效性。

再分别选取3个小规模算例与3个大规模算例中典型的求解迭代过程，作出其迭代曲线，如图2所示。由图2a可以看出，本文算法在小规模算例上不到10次迭代就可以得到收敛结果。图2b说明本文算法在大规模算例上不超过30次迭代即可得到收敛结果。结合求解结果与收敛过程，本文算法在Solomon库中A、B两组共50个基准案例上的求解效果较好，收敛速度快，收敛性好。

4 结论

本文为求解CVRP问题提出了一种聚类蚁群混合算法。使用Solomon的VRP基准算例对算法的有效性进行了验证并分析。实验结果表明，在选取的50个Solomon标准算例中，本文提出的聚类蚁群混合算法能在22%的算例中获得当前已知最优解，在4%的算例中获得了更短总距离且车辆数增加的解。72%的算例与当前已知最优解的误差不超过2%，最大误差为4.4%。同时该算法具有良好的收敛性和较快的收敛速度。

在后续研究中，可考虑将本文算法在各种VRP问题上进行应用，并提升其求解效率。

参考文献

[1] Thibaut V.Hybrid genetic search for the CVRP： open-source implementation and SWAP* neighborhood［J］.Computers & Operations Research，2022 （140）：1-11.

[2] Machado A M， Mauri G R， Boeres M C S，et al. A new hybrid matheuristic of GRASP and VNS based on constructive heuristics， set-covering and set-partitioning formulations applied to the capacitated vehicle routing problem［J］.Expert Systems with Applications，2021，184（12）：1-13.

[3] Babak R， Frederico G G， Rasul E，et al.Combining genetic local search into a multi-population imperialist competitive algorithm for the capacitated vehicle routing problem［J］.Applied Soft Computing，2023， 142：1-16.

[4] 赵辰.基于遗传算法的车辆路径优化问题研究［D］.天津：天津大学，2012.

[5] 毕志升，蔡茗芊.基于多目标模拟退火的带容量限制车辆路径问题［J］.计算机与数字工程，2017，45（8）：1513-1518.

[6] 刘志硕，申金升，柴跃廷.基于自适应蚁群算法的车辆路径问题研究［J］.控制与决策，2005，20（5）：562-566.

[7] 陈高华，郗传松.求解多目标车辆路径优化的改进蚁群算法研究［J］.机械设计与制造，2023（9）：231-236.

[8] 陈迎欣.基于改进蚁群算法的车辆路径优化问题研究［J］.计算机应用研究，2012，29（6）：2031-2034.

[9] 梁承姬，崔佳诚，丁一.基于混合蚁群算法的车辆路径问题研究［J］.重庆交通大学学报（自然科学版），2016，35（3）：94-99.

[10] Thammano A， Rungwachira P.Hybrid modified ant system with sweep algorithm and path relin-king for the capacitated vehicle routing problem［J］.Heliyon，2021，7（9）：e08029.

[11] 唐东明.聚类分析及其应用研究［D］.成都：电子科技大学，2010.

[12] 张潜，高立群，胡祥培，物流配送路径多目标优化的聚类-改进遗传算法［J］.控制与决策，2003，18（4）：418-422.

[13] 李桃迎，吕晓宁，李峰，考虑动态需求的外卖配送路径优化模型及算法［J］.控制与决策，2019，34（2）：406-413.

[14] 赵雄，李琳.基于聚类的LNS算法求解异构VRP问题［J］.计算机技术与发展，2023，33（9）：98-104.

[15] 辛颖.基于蚁群算法的车辆路径规划问题求解研究［D］.长春：吉林大学，2015.

基金资助

国家自然科学基金(61972266)

辽宁省自然科学基金(2020-MS-233)

辽宁省兴辽英才计划项目(XLYC2002017)