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

求解车辆路径问题的改进布谷鸟算法0引言车辆路径问题（thevehicleroutingproblem,VRFp源于旅行商问题（TSB»,最初由Dangzig等于1959年提出，用于解决运输车队在一个炼油厂和多个加油站之间最优路径问题，后来逐渐演化成经典的VRP问题，又叫基本VRP问题或有容量约束的VRP（CVRPVRP问题可以简单描述为一定数量的客户，各自有不同数量的货物需求，由若干隶属于同一中心仓库的车辆进行配送，在车辆容量有约束的前提下，寻找一组最优行车路线，目标是使客户需求得到满足的同时，资源（路程、成本、时间等）消耗最小车辆路径问题是重要的组合优化问题，其成果可以直接应用于物流配送调度优化，也可为诸多实际问题如垃圾收集、街道清洁、公交路线等领域的优化提供了解决思路所以车辆路径问题一直以来都是组合优化领域的研究热点文献详细调查了近年来VRP问题的算法研究，结果显示求解VRP的算法主要可以归纳为三类：精确算法、？7.⑹巢惴椒e驮？启发式算法，其中元启发式算法占比达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及其它组合优化问题一个重要的研究方向本文将引入一种新兴元启发算法一一布谷鸟算法（CuckooSearch,C§,对其改进后用于VRP、可题的求解CSJT法是由剑桥大学学者Yang和Deb于2009年提出的一种仿生智能算法该算法的思想主要基于两个策略：一是布谷鸟通过l6vy飞行机制寻找寄生巢，二是丢弃被发现的鸟巢并通过偏好随机游走的方式更新鸟巢位置这种寻优方式结合了l6vy飞行的全局搜索和随机游走的局部搜索，是一种简洁高效的寻优模式根据文献，CS算法在连续型优化领域有着广泛的研究，涉及多目标优化、神经网络优化、工程设计、交通流量预测以及图像处理等，但在离散型组合优化领域的研究并不多见，主要集中于二进制CS算法求解经典NP难题（0/1背包问题、TSP问题）、生产调度优化以及无线网络优化，鲜见将CS算法应用于求解VRP问题的研究。

考虑到CS算法求解优化问题的突出优势，本文将其应用于基本VRP问题的求解，针对VRP问题的特性，提出一种带有动态交叉策略的布谷鸟算法（CSDC,其核心思想是：引入遗传算法、微分算法等进化算法中的交叉变异思想，在种群经过l6vy飞行和偏好随机游走两个环节后，对种群进行交叉选择操作，丰富种群的多样性，避免陷入局部最优，进一步提高CS算法的寻优性能1VRP问题描述及数学模型基本VRP问题可描述为：设点集V={0,1,2,…，k}表示k个客户和一个中心仓库，其中{0}表示仓库，设客户i的货物需求量为gi,iGV-{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),iG{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),xiG[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。

上述解的构造方式可以确保每个客户有且仅有一辆车为其提供配送服务，且到达或离开某一客户的车辆有且仅有一辆1.2 构造适应值函数适应值函数是评价一组解优劣的标准，对于无约束优化问题，目标函数即适应值函数，但基本VRP问题是带有车辆容量约束的优化问题，为编程方便，简化计算过程，可以通过罚函数将车辆约束整合到目标函数中，构建新的适应值函数：其中：R是罚系数，可以设置为一个足够大的正数，将其与总过载量相乘这样，超出车辆容量限制的不可行解会被赋予很大适应值，在迭代中会被淘汰掉1.3 带动态交叉操作的CS算法本文在基本CS算法的基础上，引入遗传算法、微分算法等进化算法普遍使用的解的交叉思想，提出一种带动态交叉操作的CS算法（CSwithDynamicCrossoverOperation,CSDC通过交叉操作提高种群的多样性，避免种群陷入局部最优，提高算法的寻优性能CSDCf法的基本思想是：基本CS算法在经过l6vy飞行后产生一个新位置Xt1i，丢弃部分被发现的鸟巢又产生一个新位置Xt2i，此时，Xt2i不是直接进入t+1次的迭代，而是将Xt1i、Xt2i各维分量进行随机重组生成新的交叉向量Xti，Xti作为鸟巢的最新位置进入t+1次迭代，其j维分量的值通过下面公式生成：式中，rand是［0,1］间的随机数；CR是范围在［0,1］间的常数，称为交叉常量。

CR取值越大，Xt2i中分量被选择的机会越大，Xti位置越接近Xt2i,反之则Xti越接近Xt1iCR较好的取值范围是0.3到0.9之间，比较好的选取值是0.5本文根据VRP问题的特点，动态选取0.7和0.35两个值作为交叉常量，如果位置Xt2i（解向量）违反了车辆容量约束，选取CR=0.35，即Xti更多地选取Xt1i中的分量构建新位置；反之，选取CR=0.7通过适应值可以判断Xt2i是否违反容量约束通过上述交叉操作，一是丰富了种群的多样性，避免陷入局部最优，提高算法的寻优性能；二是通过动态选取交叉常量，加速了算法的收敛速度CSDCT法的具体实施步骤如下：步骤1:初始化种群设置种群大小N,最大迭代次数MaxIter,发现概率pa,交叉常量CR按照上述构造解向量的规则，随机产生N个鸟巢位置，超出边界值的分量取边界值，得N个初始鸟巢位置：X（0）={X01,X02,…，X0N}步骤2：根据式（11）计算每个鸟巢位置的适应值fitness，记录最优值及相应最优鸟巢的位置步骤3：保留上代最优鸟巢位置，按照式（8）、（9）通过l6vy飞行机制更新鸟巢位置，并对更新后的鸟巢位置做越界处理步骤4：利用式（11）计算步骤3生成的新鸟巢位置适应值，找出最优值；对比上一代鸟巢位置的最优值，若优，则替换上一代最优值，并更新相应最优鸟巢位置，确定当前最优鸟巢位置及最优值。

步骤5：按照式（10）随机改变被发现的鸟巢位置，得到一组新鸟巢位置步骤6：将步骤4和步骤5获得的鸟巢位置按式（12）作交叉操作，得到一组新鸟巢位置步骤7：评价步骤6产生的鸟巢位置适应值，确定当前最优鸟巢位置及最优值步骤8：进入下一次迭代判断是否满足结束条件，满足则退出迭代，输出最优值及最优鸟巢位置，否则转步骤3继续迭代4 实验结果与分析4.1 实验1为验证本文提出的算法在求解VRP问题时的性能，我们采用MATLAB2014a）分别编写了求解VRP问题的局部粒子群算法（ParticleSwarmOptimization，PSO）、基本布谷鸟算法（CuckooSearch,CS和带动态交叉操作的布谷鸟算法（CuckooSearchwithDynamicCrossoverOperation,CSDC采用文献提供的算例，将上述算法应用于8个客户，1个中心仓库，3辆车的基本VRP问题，已知问题的最优里程数为67.5,最优路径为0-4-7-6-0-1-3-5-8-2-0实验环境为Windows7平台+Intel酷睿5iCUP+4G内存，算法相关参数设置如下：PSOB法：惯性权重3=0.729,学习因子C1=C2=1.49,领域结构采用环形结构，子群数是3;CS算法：发现概率pa=0.2,步长控制因子a=0.01xrandn;CSDCT法：发现概率和步长控制因子同CS算法，动态交叉概率CR1=0.35,CR2=0.7,适应值fitness>105时，交叉概率取CR1否则取CR2上述三种算法的种群数N=25,罚系数R=108,最大迭代次数MaxIter=200,每种算法连续独立运行20次。

测试结果如表1所示从测试结果可以看出，上述3种算法均能找到已知最优解，其中CSDC勺寻优成功率远高于PSOffiCS算法，反映出CSDCM有良好的全局收敛性从平均值和标准差两个指标来看，CSDC所求最优里程的质量也远高于PS5口CS算法，且CSD8：得最里程的标准差很小，表明CSDC寸初始值具有较强的鲁棒性，显示出其在离散空间良好的寻优性能由于增加了动态交叉操作，CSDC勺平均运算时间略高于CS算法从平均值的进化曲线（图1）和具有代表性的单次进化曲线（图2）可以直观看出，对于上述VRP问题，PSOF口CS容易收敛于局部最优解，而CSDC勺收敛速度与精度均高于其他两种算法，表明通过动态交叉操作丰富解的多样性，可以提高算法跳出局部最优的可能性同时提高了收敛速度为进一步验证CSD®法求解小规模VRP勺效率，选取文献中的算例作对比试验文献采用蝙蝠算法（BatAlgorithm,BA求解7个客。