求解带容量约束车辆路径问题的离散布谷鸟算法

向明尚， 张 强

( 东北石油大学 计算机与信息技术学院，黑龙江 大庆 163318 )

0 引言

带容量约束的车辆路径问题(Capacitated Vehicle Routing Problem,CVRP)[1]是物流研究领域中一个具有很高的实际应用和理论研究价值的问题。为求解有容量车辆路径问题,减少陷入局部最优的情况,张景玲等[2]提出一种基于强化学习的超启发算法；黄戈文等[3]提出一种采用灰狼空间整数编码和先路由后分组解决方案生成策略的自适应遗传灰狼优化算法，用于求解带容量约束的车辆路径问题；何国强等[4]采用传统遗传算法求解带容量约束的车辆路径问题,存在早熟收敛、易陷入局部最优等问题,设计双种群混合遗传算法进行求解；为解决带容量约束的车辆路径问题,李阳等[5]提出一种混合变邻域生物共栖搜索算法进行求解。

布谷鸟算法(Cuckoo Algorithm,CA)是一种模拟布谷鸟寄生育雏行为的仿生优化算法[6]。近年来，人们把布谷鸟搜索算法应用到实际工程优化问题中。对制造型企业生产项目调度优化,曹圣武等[7]提出一种基于自适应布谷鸟算法的调度策略；申志平等[8]设计一种基于Adam优化算法改进布谷鸟算法，解决传统无线传感器网络随机部署分布不均问题；对最小二乘法在求解未知节点位置过程中定位精度不足,李娜等[9]提出一种基于改进布谷鸟算法的WSN节点定位算法；为解决传统传感器网络随机部署分布不均问题,胡坚等[10]提出采用布谷鸟搜索算法进行节点部署优化。布谷鸟搜索算法主要用于解决连续性问题，并且在求解复杂工程问题时CA易陷入局部最优。为改善CA的优化性能，笔者提出一种离散布谷鸟算法 (Discrete Cuckoo Algorithm,DCA)，在DCA中利用轮盘赌机制，提高初始解的质量；重定义莱维飞行和寄生巢位置更新策略，利用新的位置更新策略对路径进行优化，引入shift法和2—opt法增强最优解的局部开发能力，进一步提高算法的优化性能；对改进效果进行仿真验证，并将DCA与BA、ACO、SA及PSO优化算法在求解文中建立的模型上进行对比。

1 数学模型

CVRP可描述为：一组车辆从配送中心出发对若干顾客进行服务，在配送货物时要满足车辆容量等约束条件，服务完一条路径上的全部客户后返回到配送中心，要求合理安排配送路径，使总目标函数最小。为便于分析和研究，假设：

(1)配送中心与每个客户节点之间是相互连通的道路，所有同种车型的配送车辆从配送中心出发，完成配送任务后返回配送中心；

(2)每辆车可以对多个客户点进行配送，但每个客户点有且仅有一辆配送车为其服务；

(3)每条配送路径的货物总需求量不超过配送车辆的最大装载限制；

(4)每个客户的需求量小于配送车辆的最大承载量。

(1)

其中

(2)

(3)

(4)

(5)

(6)

式中：minF为目标函数，F为配送车辆行驶总路径长度。约束条件式(2)表示每辆车不得超过其最大的承载量Q；约束条件式(3)表示车辆从配送中心出发，服务完一条配送路径后必须返回配送中心；约束条件式(4)、式(5)表示配送车辆服务完客户i后，一定从客户点i离开并前往客户点j;约束条件式(6)保证每个客户只能被一辆配送车辆服务一次。

2 算法设计

2.1 算法原理

在自然界中，布谷鸟通常采用巢寄生的方式繁育后代，通过对布谷鸟特殊的繁殖后代模拟，ARMACHESKA M等[11]提出一种新型元启发式算法，即CA。该算法模拟布谷鸟选巢产蛋的繁殖习性，利用莱维飞行进行路径搜索。在算法中需要设定3个理想状态[12]：

(1)布谷鸟一次只产一枚蛋，并随机选择寄生巢穴孵化，每个蛋等同于一个优化问题的解；

(2)在随机选择的一组寄生巢中，当前拥有最优蛋的寄生巢将被保留到下一代继续使用；

(3)可供选择的寄生巢数量n固定，宿主鸟发现外来鸟蛋的概率Pa∈[0,1]，此时宿主鸟将丢弃布谷鸟的蛋，或者放弃该鸟巢，从而导致孵化失败。标准的布谷鸟算法主要用于优化空间的连续变量，但CVRP问题中计算的变量是离散的。

2.2 个体编码

在CVRP问题中配送中心和顾客点为离散的点，因此采用非负整数编码。布谷鸟的一枚蛋等同于优化问题的一个解，即车辆的路径方案。配送中心用0表示，顾客点为1,2,…,n，每辆车由配送中心出发，服务完一条路径上的顾客后，再返回配送中心。对于解空间，根据配送车-辆的承载量约束可得如{0,2,1,5,0,7,3,9,8,0,4,6,10,0}的解，表示由3辆车进行配送，3辆车的配送路径分别为{0,2,1,5,0}，{0,7,3,9,8,0}，{0,4,6,10,0}，解的结构见图1。

图1 解的结构

2.3 初始解构造

对随机方法构造初始种群不均匀问题，使用轮盘赌机制增强初始解选择的随机性，提高初始种群的整体质量，使得各节点有概率被选中并被选择的可能性与其适应度大小成正比，并保持发现新路径的能力，避免算法陷入局部最优。设dij为i节点与j之间的距离，且dij=dji，操作步骤：

(1)所有车辆从配送中心出发，未加入路径的节点集合为C，已访问路径的节点集合为S；在集合C中随机选取一点作为第一个已访问路径的节点。

(3)随机生成一个实数n∈[0,1]，令n分别减去各待访问节点被选择的概率Pij。当n-Pij≤0时，判断是否满足车辆的容量约束，若是，则转步骤(4)；否则，转步骤(1)。

(4)将顾客节点加入已访问路径中，重复执行(2-3)，直至集合中待访问节点个数为0。

2.4 算法位置更新

标准布谷鸟优化算法用来求解具有连续性的问题，求解CVRP模型时，客户节点编码离散，需要重新定义布谷鸟优化算法的莱维飞行和巢寄生位置更新操作。为保持布谷鸟算法位置更新特点，在离散布谷鸟算法中，采用重新定义的莱维飞行和巢寄生交替搜索进行路径的更新操作。

2.4.1 莱维飞行重定义

DCA中用exchange法和2—opt法取代CA中的莱维飞行位置更新行为。其中，exchange法是通过随机选择三条路径中的三个节点(s、u、v)，将它们的位置相互交换后形成新的路径组合。exchange法路径结构见图2。由图2可见，交换s、u、v三个节点的位置后形成三条新路径。2—opt法主要通过局部搜索使DCA保持局部开发的能力，随机选择一条路径中的两个节点u、v，将u、v之间的节点相互交换位置，形成一条新的路径。2—opt法路径结构见图3。由图3可见，交换u、v两个节点之间的所有节点位置后形成一条新路径。

图2 exchange法路径结构

2.4.2 巢寄生重定义

DCA中用reverse法和shift法取代CA中的巢寄生行为。其中，shift法的操作为随机选择两条路径中的两个节点u、v，交换u、v两个节点的位置，形成两条新的路径。shift法路径结构(见图4)中，u、v两个节点互换位置后形成新的路径结构；reverse法主要通过局部搜索增加种群的多样性，随机选择一条路径中的两个节点u、v，将它们之间的节点序列根据原来的顺序逆序排列，形成新的路径结构(见图5)。由图5可见，将u、v两个节点之间序列逆序操作后形成一条新路径。

图3 2—opt法路径结构

图4 shift法路径结构

图5 reverse法路径结构

DCA主要分为三个阶段：

(1)初始化种群阶段。利用轮盘赌机制提高种群的初始质量，增强初始解选择的随机性。

(2)莱维飞行阶段。通过exchange法进行路径间搜索，增加种群的多样性；采用2—opt法在邻域范围内进行局部搜索，避免算法陷入局部最优。

(3)巢寄生阶段。通过shift法改进当前路径，使算法逐步接近最优解；通过reverse法对最优解局部搜索，提高算法的收敛速度和计算精度。

因此，DCA在理论上具有较好的全局和局部寻优能力。

2.5 算法步骤

(1)定义目标函数，初始化各参数，设置初始巢穴个数。

(2)使用轮盘赌机制进行种群的初始化，计算每条路径的适应度值，保留最优适应度值对应的路径M。

(3)采用离散化莱维飞行和离散化巢寄生操作得到新的路径W、X、Y、Z，分别计算它们适应度值。

(4)选择W、X、Y、Z中适应度值最小与路径M的适应度值进行比较。若结果优于M，则保留新路径为当前最优解。

(5)重复步骤(3-4)，直至算法满足终止条件(达到最大迭代次数或者其他终止准则等)。

3 实验与分析

采用AUGERAT标准测试集进行仿真实验，将DCA和粒子群算法[13](Particle Swarm Optimization,PSO)、模拟退火算法[14](Simulated Annealing, SA)、蝙蝠算法[15](Bat Algorithm,BA)，以及蚁群算法[16](Ant Colony Optimization,ACO)进行比较实验。部分算例实验结果见表1(NV为车辆数；TD为路径总长度)。DCA参数设置：最大迭代次数为1 000，种群数为100。对每个问题独立求解10次，取平均值，BA、PSO、ACO和SA的基本参数设置同DCA。

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

由表1可见，DCA在求解A-n32-k5、A-n33-k5、A-n36-k5、A-n37-k6、A-n39-k6、A-n54-k7、A-n62-k8问题时，结果优于其他4种对比算法；在求解A-n32-k5、A-n33-k5、A-n36-k5、A-n37-k6、A-n39-k6、A-n54-k7问题时，求得的最优总距离优于现在已知最优解；在求解A-n32-k5、A-n33-k6、A-n36-k5、A-n37-k5、A-n54-k7时，求得的最优车辆数优于其他4种对比算法。DCA在求解不同类型和规模的CVRP问题时有较好的性能。DCA求解部分算例的最优路径见图6，DCA求解部分算例的路径总长度迭代见图7。

由图7可见，在算法迭代初期，DCA引入轮盘赌机制对初始种群进行优化使得总路径长度大幅下降，在短时间内快速趋近最优解，从而体现DCA具有良好的全局搜索能力；随迭代次数的增加，DCA的局部搜索能力逐渐占主导地位，其中，DCA采用reverse法和2—opt进行邻域搜索，避免算法在迭代后期陷入局部最优，能充分挖掘搜索空间。因此，DCA有较好的求解能力。

图6 DCA求解部分算例的最优路径

图7 DCA求解部分算例的路径总长度迭代

4 结论

(1)提出一种离散布谷鸟算法(DCA)，引入轮盘赌机制优化初始种群，对布谷鸟算法的莱维飞行和巢寄生操作重定义，可以更加高效求解CVRP，寻优质量优于BA、ACO、SA、PSO算法。

(2)DCA在求解CVRP模型前期具备较强的全局搜索能力，后期有较强的局部寻优能力，并且在求解大规模数据量的问题时，具有较好的寻优能力。