求解车辆路径问题的改进布谷鸟算法

孟庆永+张启慧

摘 要：将一种新型的智能优化算法——布谷鸟算法（Cuckoo Search Algorithm，CS）用于车辆路径问题的求解。针对基本CS算法种群多样性差、寻优精度低等不足，提出一种动态交叉算子来丰富种群多样性，避免种群个体陷入局部最优，增强算法的全局寻优能力。通过对比试验验证了算法在求解VRP问题时具有寻优精度高、性能稳定等特点，是求解VRP问题的一种有效的算法。

关键词：车辆路径问题；布谷鸟算法；动态交叉

中图分类号：G4 文献标识码：A doi：10.19311/j.cnki.1672-3198.2016.33.171

0 引言

车辆路径问题（the vehicle routing problem，VRP）源于旅行商问题（TSP），最初由Dangzig等于1959年提出，用于解决运输车队在一个炼油厂和多个加油站之间最优路径问题，后来逐渐演化成经典的VRP问题，又叫基本VRP问题或有容量约束的VRP（CVRP）。VRP问题可以简单描述为一定数量的客户，各自有不同数量的货物需求，由若干隶属于同一中心仓库的车辆进行配送，在车辆容量有约束的前提下，寻找一组最优行车路线，目标是使客户需求得到满足的同时，资源（路程、成本、时间等）消耗最小。车辆路径问题是重要的组合优化问题，其成果可以直接应用于物流配送调度优化，也可为诸多实际问题如垃圾收集、街道清洁、公交路线等领域的优化提供了解决思路。所以车辆路径问题一直以来都是组合优化领域的研究热点。

文献详细调查了近年来VRP问题的算法研究，结果显示求解VRP的算法主要可以归纳为三类：精确算法、啟发式算方法和元启发式算法，其中元启发式算法占比达65%-80%。这与VRP问题性质有关，由于VRP问题是NP-hard问题，随着问题规模的增长，VRP问题的可行解会出现“组合爆炸”现象，精确算法和经典启发式算法在求解该类问题时，计算复杂度高，计算开销大，甚至无法获得可行解，而元启发式算法具有快速的寻优的性能，使其成为求解VRP问题的主要算法。目前，求解VRP问题的元启发式算法可以大致归纳如下：（1）遗传算法（GA）；（2）蚁群算法（ACO）；（3）模拟退火算法（SA）；（4）可变领域搜索（VNS）；（5）禁忌搜索算法（TS）；（6）局部搜索算法（LS）；（7）人工蜂群算法（ABC）；（8）粒子群算法（PSO）；（9）其他新兴元启发式算法，如蛙跳算法、蝙蝠算法、萤火虫算法等以及各种改进版本，更多关于VRP问题的元启发式算法参见文献。

虽然已有大量优秀的算法，但追求更高效的算法是VRP及其它组合优化问题一个重要的研究方向。本文将引入一种新兴元启发算法——布谷鸟算法（Cuckoo Search，CS），对其改进后用于VRP问题的求解。CS算法是由剑桥大学学者Yang和Deb于2009年提出的一种仿生智能算法。该算法的思想主要基于两个策略：一是布谷鸟通过lévy飞行机制寻找寄生巢，二是丢弃被发现的鸟巢并通过偏好随机游走的方式更新鸟巢位置。这种寻优方式结合了lévy飞行的全局搜索和随机游走的局部搜索，是一种简洁高效的寻优模式。根据文献，CS算法在连续型优化领域有着广泛的研究，涉及多目标优化、神经网络优化、工程设计、交通流量预测以及图像处理等，但在离散型组合优化领域的研究并不多见，主要集中于二进制CS算法求解经典NP难题（0/1背包问题、TSP问题）、生产调度优化以及无线网络优化，鲜见将CS算法应用于求解VRP问题的研究。考虑到CS算法求解优化问题的突出优势，本文将其应用于基本VRP问题的求解，针对VRP问题的特性，提出一种带有动态交叉策略的布谷鸟算法（CSDC），其核心思想是：引入遗传算法、微分算法等进化算法中的交叉变异思想，在种群经过lévy飞行和偏好随机游走两个环节后，对种群进行交叉选择操作，丰富种群的多样性，避免陷入局部最优，进一步提高CS算法的寻优性能。

1 VRP问题描述及数学模型

基本VRP问题可描述为：设点集V={0，1，2，…，k}表示k个客户和一个中心仓库，其中{0}表示仓库，设客户i的货物需求量为gi，i∈V-{0}，中心仓库有m辆载重量为q（q>gi）的车向k个客户配送货物，cij表示从客户i到客户j的成本（时间、路程、花费等），求一组可行的运输路线，使得所有客户需求得到满足的情况下，所用车辆数和总运输成本（路程）最小，其中每个客户只能由一辆车配送，且每辆车的运输量不得超过容量上限。首先定义变量：

其中，（2）为车辆容量约束；（3）表示每个需求点运输任务仅由一辆车完成；（4）和（5）保证了到达和离开某个需求点的车辆有且仅有1辆。

2 基本CS算法

CS算法通过模拟布谷鸟寻找寄生鸟巢的行为寻找最优解，其寻优过程如下：

步骤1：在目标函数的解空间内随机生成n个鸟巢N={X1，X2，…，XN}，Xi是第i个鸟巢的位置，对应于目标函数解空间的一个随机可行解，如果解的维数是k，则第i个鸟巢的位置Xi={xi1，xi2，…，xik}；计算每个鸟巢位置的适应值f（Xi），i∈{1，2，…，n}，找出适应值最好的鸟巢X，其中f（X）是目标函数，对于最小化问题，目标函数值越小适应值越好。

步骤4：评估所有鸟巢位置，找出最优鸟巢及其适应值，并将新的鸟巢位置放入步骤（2）中继续迭代，直到满足停止条件为止，然后输出最优鸟巢（最优解）及适应值。

3 车辆路径问题的改进CS算法

3.1 构造解向量

基本CS算法用来求解连续域函数优化问题的，对于离散组合优化如VRP问题，必须根据问题特点合理构造解向量的编码方式，使其适用于CS算法。本文借鉴文献的编码思想，采用实数编码方式，将离散域问题转换为连续域问题。

对于m辆车，k个客户的VRP问题，构造一个k+m-1维实数向量，该向量包含一个VRP问题解的完整信息：X=（x1，x2，…，xk+m-1），xi∈[1，k+m-1]，其解码过程如下：

假设有一6个客户，3辆车的VRP问题，对其客户进行编号：{1，2，3，4，5，6，0，0}，其中{0}代表中心仓库，其数量为车辆数减1。按上述编码规则产生一个解向量X={5.2，4.6，7.8，1.2，6.4，4.9，2.3，71}，对X进行整数排序，并与客户编号对应。

客户编号：{1，2，3，4，5，6，0，0}，X：{5，3，8，1，6，4，2，7}

将X视作客户编号的下标，按照下标大小顺序对客户编号进行排列，得到一组行车路径：4-0-2-6-1-5-0-3.每辆车的行车路径为：车1：0-4-0；车2：0-2-6-1-5-0；车3：0-3-0。上述解的构造方式可以确保每个客户有且仅有一辆车为其提供配送服务，且到达或离开某一客户的车辆有且仅有一辆。

3.2 构造适应值函数

适应值函数是评价一组解优劣的标准，对于无约束优化问题，目标函数即适应值函数，但基本VRP问题是带有车辆容量约束的优化问题，为编程方便，简化计算过程，可以通过罚函数将车辆约束整合到目标函数中，构建新的适应值函数：

其中：R是罚系数，可以设置为一个足够大的正数，将其与总过载量相乘。这样，超出车辆容量限制的不可行解会被赋予很大适应值，在迭代中会被淘汰掉。

3.3 带动态交叉操作的CS算法

本文在基本CS算法的基础上，引入遗传算法、微分算法等进化算法普遍使用的解的交叉思想，提出一种带动态交叉操作的CS算法（CSwith Dynamic Crossover Operation，CSDC）。通过交叉操作提高种群的多样性，避免种群陷入局部最优，提高算法的寻优性能。

CSDC算法的基本思想是：基本CS算法在经过lévy飞行后产生一个新位置Xt1i，丢弃部分被发现的鸟巢又产生一个新位置Xt2i，此时，Xt2i不是直接进入t+1次的迭代，而是将Xt1i、Xt2i各维分量进行随机重组生成新的交叉向量Xti，Xti作为鸟巢的最新位置进入t+1次迭代，其j维分量的值通过下面公式生成：

式中，rand是[0，1]间的随机数；CR是范围在[0，1]间的常数，称为交叉常量。CR取值越大，Xt2i中分量被选择的机会越大，Xti位置越接近Xt2i，反之则Xti越接近Xt1i。CR较好的取值范围是0.3到0.9之间，比较好的选取值是0.5。本文根据VRP问题的特点，动态选取0.7和0.35两个值作为交叉常量，如果位置Xt2i（解向量）违反了车辆容量约束，选取CR=0.35，即Xti更多地选取Xt1i中的分量构建新位置；反之，选取CR=0.7。通过适应值可以判断Xt2i是否违反容量约束。通过上述交叉操作，一是丰富了种群的多样性，避免陷入局部最优，提高算法的寻优性能；二是通过动态选取交叉常量，加速了算法的收敛速度。

CSDC算法的具体实施步骤如下：

步骤1：初始化种群。设置种群大小N，最大迭代次数MaxIter，发现概率pa，交叉常量CR。按照上述构造解向量的规则，随机产生N个鸟巢位置，超出边界值的分量取边界值，得N个初始鸟巢位置：X（0）={X01，X02，…，X0N}。

步骤2：根据式（11）计算每个鸟巢位置的适应值fitness，记录最优值及相应最优鸟巢的位置。

步骤3：保留上代最优鸟巢位置，按照式（8）、（9）通过lévy飞行机制更新鸟巢位置，并对更新后的鸟巢位置做越界处理。

步骤4：利用式（11）计算步骤3生成的新鸟巢位置适应值，找出最优值；对比上一代鸟巢位置的最优值，若优，则替换上一代最优值，并更新相应最优鸟巢位置，确定当前最优鸟巢位置及最优值。

步骤5：按照式（10）随机改变被发现的鸟巢位置，得到一组新鸟巢位置。

步骤6：将步骤4和步骤5获得的鸟巢位置按式（12）作交叉操作，得到一组新鸟巢位置。

步骤7：评价步骤6产生的鸟巢位置适应值，确定当前最优鸟巢位置及最优值。

步骤8：进入下一次迭代。判断是否满足结束条件，满足则退出迭代，输出最优值及最优鸟巢位置，否则转步骤3继续迭代。

4 实验结果与分析

4.1 实验1

为验证本文提出的算法在求解VRP问题时的性能，我们采用MATLAB（2014a）分别编写了求解VRP问题的局部粒子群算法（Particle Swarm Optimization，PSO）、基本布谷鸟算法（Cuckoo Search，CS）和带动态交叉操作的布谷鸟算法（Cuckoo Search with Dynamic Crossover Operation，CSDC）。采用文献提供的算例，将上述算法应用于8个客户，1个中心仓库，3辆车的基本VRP问题，已知问题的最优里程数为67.5，最优路径为0-4-7-6-0-1-3-5-8-2-0。实验环境为Windows7平台+Intel酷睿5i CUP+4G内存，算法相关参数设置如下：

PSO算法：惯性权重ω=0.729，学习因子C1=C2=1.49，领域结构采用环形结构，子群数是3；CS算法：发现概率pa=0.2，步长控制因子α=0.01×randn；CSDC算法：发现概率和步长控制因子同CS算法，动态交叉概率CR1=0.35，CR2=0.7，适应值fitness>105时，交叉概率取CR1，否则取CR2。上述三种算法的种群数N=25，罚系数R=108，最大迭代次数MaxIter=200，每种算法连续独立运行20次。测试结果如表1所示。

从测试结果可以看出，上述3种算法均能找到已知最优解，其中CSDC的寻优成功率远高于PSO和CS算法，反映出CSDC具有良好的全局收敛性。从平均值和标准差两个指标来看，CSDC所求最优里程的质量也远高于PSO和CS算法，且CSDC求得最優里程的标准差很小，表明CSDC对初始值具有较强的鲁棒性，显示出其在离散空间良好的寻优性能。由于增加了动态交叉操作，CSDC的平均运算时间略高于CS算法。从平均值的进化曲线（图1）和具有代表性的单次进化曲线（图2）可以直观看出，对于上述VRP问题，PSO和CS容易收敛于局部最优解，而CSDC的收敛速度与精度均高于其他两种算法，表明通过动态交叉操作丰富解的多样性，可以提高算法跳出局部最优的可能性同时提高了收敛速度。

为进一步验证CSDC算法求解小规模VRP的效率，选取文献中的算例作对比试验。文献采用蝙蝠算法（Bat Algorithm，BA）求解7个客户、3辆车的VRP问题，本文将CSDC算法用于同一问题的求解，迭代次数，种群数设置与文献相同，其它参数与上述设置相同，连续运行20次，结果如表2。

由表2可知，CSDC连续运行20次，达到最优路径20次，运行时间为35.59秒，运行时间及获得最优解的成功率均高于BA，表明CSDC在求解小规模VRP问题上有较高的效率。

4.2 实验2

实验2选用文献中的算例，進一步验证CSDC算法在解决较大规模VRP问题时的性能。该算例是20个客户、5辆车的VRP问题，每辆车载重8t，配送中心坐标是（14.5，13.0），各客户坐标及需求量见表3，求一组最小运输路径。

由于客户规模增大，解向量的维数也相应增多，为提高寻优的效率，将步长控制因子α设置为1.5×randn，发现概率设置为0.7，最大迭代次数为2000次（与文献设置相同）。将CSDC求解结果与文献提出的量子遗传算法（QGA）、混合量子遗传算法（HQGA）求解结果进行比较，如表4所示。

由表4可以看出，3种算法独立运行5次，CSDC所得结果优于QGA和HQGA，获得最优解里程为108.6，对应车辆路径为：车辆1：0-3-17-11-20-18-0；车辆2：0-4-0；车辆3：0-6-13-16-15-19-8-0；车辆4：0-1-7-10-9-12-2-14-5-0。上述实验结果表明，CSDC算法用于VRP问题的求解是行之有效的，对于规模较大的VRP问题，可以适当增大lévy飞行的步长控制因子及发现概率，以便算法能够在更大维度的解空间上寻优，降低陷入局部最优的概率，提高寻优质量。

5 结论

本文将CS算法应用于求解离散空间的VRP问题，针对基本CS算法局部搜索能力不强，收敛精度不高等特点，引入动态交叉算子，提出一种带动态交叉操作的CS算法。该算法在进化过程中，经过CS算法两个基本步骤后，不会直接进入下一次迭代，而是将两个步骤产生的位置向量根据适应值大小进行交叉操作，丰富解的多样性，避免陷入局部最优。实验结果表明，用该算法求解VRP问题可以取得不错的收敛精度，但动态交叉操作要计算新位置的适应值，一定程度上影响了运行速度，这是后续研究需要改进的地方。

参考文献

[1]Dan tzing G，RAMSER J.The truck dispatching problem[J].Management Science，1959，10（6）：80-911.

[2]Braekers K，Ramaekers K，Nieuwenhuyse I V.The vehicle routing problem：State of the art classification and review[J].Computers & Industrial Engineering，2016：1-49.

[3]Eksioglu B，Vural A V，Reisman A.The vehicle routing problem： A taxonomic review[J].Computers & Industrial Engineering，2009，57（4）：1472-1483.

[4]Montoya-Torres J R，Franco J L，Isaza S N，et al.A literature review on the vehicle routing problem with multiple depots[J].Computers & Industrial Engineering，2014，79：115-129.

[5]Yang X S，Deb S.Cuckoo Search via Lévy flights[C].Nature & Biologically Inspired Computing，2009. NaBIC 2009.World Congress on.IEEE，2009：210-214.

[6]Fister I，Yang X S，Fister D，et al.Firefly Algorithm：A Brief Review of the Expanding Literature[M].Cuckoo Search and Firefly Algorithm，2014：347-360.

[7]兰少峰，刘升.布谷鸟搜索算法研究综述[J].计算机工程与设计，2015，（04）：1063-1067.

[8]Ouaarab A，Ahiod B，Yang X S.Discrete cuckoo search algorithm for the travelling salesman problem[J].Neural Computing & Applications，2014，24（7-8）：1659-1669.

[9]张晶，吴虎胜.改进二进制布谷鸟搜索算法求解多维背包问题[J].计算机应用，2015，35（01）：183-188.

[10]Yao Y，Chunming Y E，Business S O.Solving job-shop scheduling problem by cuckoo search algorithm[J].Computer Engineering & Applications，2015.

[11]Wang H，Wang W，Sun H，et al.A new cuckoo search algorithm with hybrid strategies for flow shop scheduling problems[J].Soft Computing，2016：1-11.

[12]Alazzawi M K，Luo J，Li R，et al.Multiple Node Selection Aimed to Optimum Data Delivery Route Using Discrete Cuckoo Search Algorithm for Wireless Sensor Networks[J].Journal of Computational & Theoretical Nanoscience，2015，12（2）：316-325.

[13]Mantegna R N.Fast，accurate algorithm for numerical simulation of Lévy stable stochastic processes[J].Physical Review E Statistical Physics Plasmas Fluids & Related Interdisciplinary Topics，1994，49（5）：4677-4683.

[14]肖健梅，李军军，王锡淮.求解车辆路径问题的改进微粒群优化算法[J].计算机集成制造系统，2005，11（04）：577-581.

[15]段海滨.仿生智能计算[M].北京：科学出版社，2011：109-111.

[16]马祥丽，张惠珍，马良.蝙蝠算法在物流配送车辆路径优化问题中的应用[J].数学的实践与认识，2015，（24）：80-86.

[17]蔡蓓蓓，张兴华.混合量子遗传算法及其在VRP中的应用[J].计算机仿真，2010，27（07）：267-270.