求解带容量约束车辆路径问题的离散鲸鱼算法*

郭玉洁 张 强 魏永和

（1.东北石油大学计算机与信息技术学院 大庆 163318）

（2.国家电网冀北电力有限公司管理培训中心 北京 100000）

1 引言

带容量约束的车辆路径问题（Capacitated Vehicle Routing Problem，CVRP）是车辆路径问题（Vehicle Routing Problem，VRP）［1］的经典问题之一。CVRP一直是组合优化和运筹学领域的热点问题，其在物流配送和车辆路径规划等领域具有十分广泛的应用背景，因此如何有效地解决CVRP具有很高的实际应用和理论研究价值。

随着启发式算法的不断发展，运用群智能算法对CVRP问题进行求解是目前的重要研究方向，如何提高求解CVRP问题的效率仍是当前学者们的研究重点。文献［2］提出一种基于文化基因的狼群算法求解VRPTW。文献［3］提出一种离散蝙蝠算法求解VRP，该算法引入随机插入策略和交换搜索来提高算法的局部搜索能力。文献［4］提出一种基于NSGA-II的蚁群算法求解双目标VRPTW。文献［5］等设计一种改进蚁群算法求解VRP，在传统蚁群算法中引入交通拥堵因子，提高了计算效率。文献［6］提出一种改进的禁忌搜索算法求解面向仓库的车辆路径问题。文献［7］设计一种具有贪婪转移准则的多目标蚁群算法求解VRP。文献［8］将模拟退火算法与遗传算法结合，设计一个新型编码解码方式求解VRP。然而，以上启发式算法在不同类型的VRP算例中会出现求解能力不稳定、易陷入局部最优等问题。

鲸鱼优化算法［9］（Whale Optimization Algorithm，WOA）是由澳大利亚学者Mirjalili和Lewis于2016年提出的一种新元启发式优化算法。近年来，许多学者把鲸鱼算法应用到实际工程优化问题中，但是现有的鲸鱼算法不能直接应用到CVRP上。因此，本文提出了一种离散鲸鱼算法（Discrete Whale Optimization Algorithm，DWOA）求解CVRP，通过基于距离代价函数的K-means算法将不同位置的客户划分为不同的配送区域，提高初始解的质量；重定义鲸鱼算法中包围捕食、泡泡网捕食、随机捕食的更新策略，利用新的位置更新策略对区域组中的路径进行优化，同时引入随机交换搜索、2-opt、3-opt相结合的邻域搜索策略，寻找到更多潜在的优秀解。实验结果表明DWOA能够有效跳出局部最优、稳定性更高、时间耗费更少。

2 数学模型

带容量约束的车辆路径问题（CVRP）是指物流车辆在配送货物时要满足车身容量等约束条件，在CVRP问题中有一个配送中心，多个客户点和配送车辆，求解CVRP的目标是在满足约束条件的基础上合理安排车辆路线，使配送的总成本最低。

其中：

式（1）为目标函数，F1为配送车辆数，F2为车辆行驶总距离；式（2）表示每辆车不得超过其最大载重量；式（3）表示车辆从配送中心出发完成配送任务后必须返回配送中心；式（4）表示车辆服务完客户i后再去服务客户j；式（5）表示车辆服务客户j之前服务客户i；式（6）表示每个客户只能被一辆车服务；式（7）和式（8）表示决策变量约束条件。

3 离散鲸鱼算法

3.1 区域划分

k-means算法是一种典型的聚类方法，核心思想是通过反复迭代优化聚类结果，使所有样本点到各自所属类别的中心距离平方和达到最小，其公式如下所示：

其中，Jc是k-means聚类方法的误差平方和准则，Xi为第i聚类的样本子集，mi为第i聚类Xi中的样本均值，p为第i聚类中包含的数据。尽管k-means算法能够有效地解决聚类问题，但不正确的k会影响算法的实际效果。因此，在本文中采用距离成本函数F［10～11］来确定k值。其描述如下：

其中m是所有数据的平均值。当F最小时，聚类结果最好，并且k是根据最小F得到的；通过距离代价函数的k-means算法将大VRP问题转换成多个小VRP问题后；判断每个小区域内所要配送的客户需求量和车辆最大载重的大小关系，将客户划分到不同的区域。因此，距离代价函数的k-means算法具体实现步骤如下。

2）对于待聚类样本，计算其与k个聚类中心的距离，并将样本归类到最近的聚类群中。

3）当每个样本都被分到k个聚类群后，重新计算聚类中心m1，m2，…，mk。

4）重复步骤2）～3），直到k个聚类中心不变。

5）计算距离成本函数F并记录，直到k值全部计算结束。

6）根据最小F值找到最优k值。

7）将客户集合x=(1，2，3，4，…，d)划分为k个配送区域。

8）判断每个区域的客户总需求量是否超出车辆最大载重。

9）若每个区域的客户需求量都满足车辆最大载重，则分区结束。

10）若在k1区域（k1∈k），当客户x1加入后，超出车辆的最大载重量，将x1之前的客户划分到当前区域，余下的客户组成一个新的区域，继续步骤8），判断剩余的区域是否满足车辆最大载重。

3.2 编码与解码

设P∈N*为鲸鱼种群规模，客户数为n，车辆数为m，维数d=n。定义第i个鲸鱼的位置为xi=(xi1，xi22，xi3，…，xid)，i=1，2，…，P，其中xi是(1，2，…，d)的一个置换。

鲸鱼位置按照规则与CVRP路径形成一一对应关系：”0”认为是配送中心；鲸鱼位置前后分别加上“0”，构成一条完整的CVRP路径；客户点之间经过的顺序构成一台车辆的访问路径。例如：n=9，m=3，xi=(1，3，2，8，9，7，6，4，5)，首先对客户点进行聚类分组，假设k取值为3，则分为三个小区域：{1 ，6，4，5}，{9，7，3}，{2，8}，因此，三辆车的访问路径分别为{0 ，1，6，4，5，0}，{0，9，7，3，0}，{0，2，8，0}。

3.3 鲸鱼位置的更新操作

标准鲸鱼优化算法用来求解具有连续性的问题，但是在求解CVRP模型时，客户节点的编码是离散的，因此需要重定义鲸鱼优化算法的包围捕食、泡泡网捕食、随机捕食操作。

1）更新方式选择

在DWOA算法中，当||A≥1且rand()＜0.5时，鲸鱼通过包围捕食来搜索猎物；当||A＜1且rand()＜0.5时，鲸鱼通过泡泡网捕食来攻击猎物；当rand()≥0.5时，鲸鱼通过随机搜索来寻找猎物。

其中，α在迭代过程中从2到0线性递减；ϒ为［0，1］随机数组成的向量。为了保证更新操作后路径的可行性，对于区域组内的路径的更新方式采用基于最短距离的插入、反转、交换等操作。设x=(x1，x2，xi，xj，xk，…，xd)，i=rand(d)且i∈d，Dij表示客户i和客户j之间的距离。

2）包围捕食重定义

在一条路径中，随机选择一个客户xi，然后遍历剩余的客户点；若存在一个客户xd，到客户xi的距离小于原访问路径xi到下一个相邻客户点xj的距离，则将客户点xd插入到客户点xi之后，余下的客户点依次后移。

3）泡泡网捕食重定义

在一条路径中，随机选择一个客户xi，然后遍历剩余的客户点，计算将其插入xi之后所对应的距离增加量；若存在一个客户xd，到客户xi的距离小于原访问路径xi到下一个相邻客户点xj的距离增加量，将xi到xd之间的客户点反转。

4）随机捕食重定义

在一条路径中，随机选择一个客户xi，然后遍历剩余的客户点；若存在一个客户xd，到客户xi的距离小于原访问路径xi到下一个相邻客户点xj的距离，则将xd与原访问路径中xi的下一个客户点xj交换位置。

因此，鲸鱼位置的更新操作从连续域到离散域的转换过程：1）通过计算客户点之间的距离差值，以此对应连续域中的鲸鱼之间的位置差。2）通过判断插入位置、反转位置和交换位置时距离的增加量，选择合适的插入位置，使其不断向最优位置靠拢，符合本算法的新路径更新定义。

3.4 邻域搜索策略

根据CVRP的特点，借鉴文献［12］的邻域搜索策略，本文提出了随机交换，2-opt，3-opt相结合的局部搜索策略。

1）交换搜索：对配送路径进行交换搜索，随机选取两个不同位置的客户点，将两个客户点位置交换。

图1 交换搜索示例图

2）2-opt搜索：对配送路径进行2-opt搜索，随机选取两个不同位置的客户点，将两个客户点之间的位置全部反转。

图2 2-opt搜索示例图

3）3-opt搜索：对于配送路径进行3-opt搜索，随机选取3个位置的客户点依次交换。

图3 3-opt搜索示例图

选择上述的邻域搜索策略对每次迭代得到的最优解进行变换，产生更多的邻域解，选择适应度最小的值作为每代的最优解，本算法的局部搜索策略按照一定的规则来交换客户的访问次序，得到的路径仍然对应着一个完整的CVRP路径。

4 实验与分析

本文采用Solomon的六种类型CVRP算例［13］测试DWOA，然后将DWOA和标准鲸鱼算法（Whale Optimization Algorithm，WOA）、粒子群算法［14］（Particle Swarm Optimization，PSO）、模拟退火算法［15］（Simulated Annealing，SA）进行比较实验，表1给出部分算例实验结果。DWOA的参数设置如下：MaxIt=1000，po pnum=100，w=0.2，WOA、PSO和SA的基本参数设置同DWOA一致。在表1中，NV是车辆数，TD是总行驶距离。

表1 部分算例实验结果对比

通过表1分析可知，在求解C型问题时，DWOA的性能略优于其他三种算法，其求得配送车辆数和行驶总里程和已知最优解车辆数、最优里程数十分相近，但在求解C2问题中也存在个别案例未达到最优解；在求解R型问题时，DWOA的车辆数明显少于其它两种算法，所求的最优行驶距离整体上与目前最优解接近，其中，R1问题中有部分需求的配送车辆和配送总里程要优于当前已知最优解，R2问题中需求的配送车辆都获得了最优解，且配送总里程与已知最优里程十分接近；在求解RC型问题时，DWOA的最优解远远优于其他两种算法，甚至优于目前已知的最优解。

为了具体验证DWOA算法在求解带容量约束车辆路径问题的性能，本文分别用DWOA、WOA、PSO、SA算法对CVRP的数学模型进行求解。在Solomon数据集中以C101、C201、RC208三种算例做具体分析，其结果如下所示。

图4 C101最优路径图

图5 C201最优路径图

图6 C208最优路径图

其中，C101算例得到的最优解为832.1701，所需车辆为10，与目前最优解828.94接近，从而证明离散鲸鱼算法在求解C101上有较好的寻优能力；C201算例得到的最优解为589.76，所需车辆为3，与目前最优解591.56接近，因此，离散鲸鱼算法在求解C201上有良好的寻优效果；RC208得到的最优解为817.8789，所需车辆为3，优于目前最优解828.94，证明离散鲸鱼算法在求解RC208上有很好的寻优能力。

图7、8、9为 四 种 算 法 在 求 解C101、C201、RC208算例时的总成本迭代图，其中，横坐标表示算法的迭代次数，纵坐标表示总成本（包括配送车辆数和车辆行驶总距离），图中反映了DWOA算法有较好的求解能力。在算法迭代初期，总成本大幅下降，表明DWOA算法在前期对客户点进行聚类操作划分区域，可以使算法最短的时间内向最优解趋近，从而体现出DWOA算法具有良好的全局搜索能力；随着迭代次数的增加，总成本变化逐渐变小，DWOA的局部搜索能力逐渐占主导地位，其中，DWOA采用了交换搜索、2-opt搜索、3-opt搜索相结合的邻域搜索策略，可以使算法在迭代后期跳出局部最优。因此，验证了DWOA算法在在求解CVRP模型时前期存在较强的全局搜索能力，后期则有较强的局部寻优能力，所得到的结果要优于WOA、PSO和SA三种算法。

图7 C101算例总成本迭代图

图8 C201算例总成本迭代图

图9 RC208算例总成本迭代图

5 结语

针对CVRP的求解，本文提出了一种离散鲸鱼算法。算法采用距离代价函数的K-means算法划分不同的客户区域，重定义鲸鱼算法的位置更新策略对单个区域内的访问路径进行更新，并引入随机交换搜索、2-opt、3-opt策略对最优路径进行邻域变换，增强算法局部搜索能力。算例验证及分析表明，DWOA能够有效求解CVRP，寻优质量优于所对比算法，可跳出局部最优。未来将进一步改进DWOA，以加强其在车辆路径规划问题上的应用。