粒子群优化算法车辆路径问题

1、粒子群优化算法计算车辆路径问题摘要粒子群优化算法中，粒子群由多个粒子组成，每个粒子的位置代表优化问题在Dffi搜索空间中潜在的解。根据各自的位置，每个粒子用一个速度来决定其飞行的方向和距离,然后通过优化函数计算出一个适应度函数值(fitness)。粒子是根据如下三条原则来更新自身的状态：(1)在飞行过程中始终保持自身的惯性;(2)按自身的最优位置来改变状态;(3)按群体的最优位置来改变状态。本文主要运用运筹学中粒子群优化算法解决车辆路径问题。车辆路径问题由Dantzig和Ramser于1959年首次提出的，它是指对一系列发货点(或收货点)，组成适当的行车路径，使车辆有序地通过它们，在满足一定约

2、束条件的情况下，达到一定的目标(诸如路程最短、费用最小，耗费时间尽量少等)，属于完全NP问题，在运筹、计算机、物流、管理等学科均有重要意义。粒子群算法是最近出现的一种模拟鸟群飞行的仿生算法，有着个体数目少、计算简单、鲁棒性好等优点，在各类多维连续空间优化问题上均取得非常好的效果。本文将PSO应用于车辆路径问题求解中，取得了很好的效果。针对本题，一个中心仓库、7个需求点、中心有3辆车，容量均为1,由这三辆车向7个需求点配送货物，出发点和收车点都是中心仓库。k=3,q=q?=q3=1,l=7.货物需求重g1=0.89,g2=0.14g=0.28必=0.33。=0.21。=0.41,g7=0.57,

3、且mgia珠。利用matlab编程，求出需求点和中心仓库、需求点之间的各个距离，用Cj表小。求满足需求的最小的车辆行驶路径，就是求minZE二匚CjXij%经过初始化粒子群，将初始的适应值作为每个粒子的个ijk体最优解，并寻找子群内的最优解以及全局的最优解重复以上步骤，直到满足终止条件。本题的最短路径由计算可知为217.81关键字：粒子群算法、车辆路径、速度一、问题的重述一个中心仓库序号为0,7个需求点序号为17,其位置坐标见表1,中心有3辆车，容量均为1,由这三辆车向7个需求点配送货物，出发点和收车点都是中心仓库。求满足需求的距离最小的车辆行驶路径。表1仓库中心坐标和需求点坐标及需求量序号0

4、1234567坐标(18,54)(22,60)(58,69)(71,71)(83,46)(91,38)(24,42)(18,40)需求量00.890.140.280.330.210.410.57问题假设1 .现实生活中中心仓库以及各个需求点之间军事直线连接，两点之间距离即为坐标系中两点坐标间距离。2 .不因天气及失火等原因车辆停止运输。3 .每个需求点由一辆车供应货物。三、符号说明k配送货物车辆数l需求点个数gi货物需求量qk配送货物车辆的容量Cj从点i到j的距离yki需求点i由k车配送xijk车k从i行驶到j四、问题分析4.1算法分析车辆路径问题(VRP可以描述为有一个中心仓库，拥有K辆车，

5、容量分别为qk(k=1,2,，K),负责向L个需求点配送货物，货物需求量为gi(i=1,2,，L),且maxgi<maxqk;cj表示从点i至ijj的距离。求满足需求的距离最小的车辆行驶路径。将中心仓库编号为0,需求点编号为1,2,L。数学模型为：minZ='"cijxijkijks.t."giyki也,-卜、yki=1,i=1,2,LkXijk=ykj,j=0,1,L;k'、,xjk=yki,i=0,1,L;kX=(Xijk)SXjk=0或1,i,j=0,1，L;Vkyki=0或1,i-0,1,L;-k其中,f-yki=0需求点i由k车配送否则,1车

6、k从i行驶驶j0否则k=3,q=q2=q3=1,l=7.货物需求量g1=0.89,g2=0.14,g3=0.28,g4=0.33,gs=0.210=0.41,g?=0.57,利用粒子群优化算法，经过初始化粒子群，将初始的适应值作为每个粒子的个体最优解，并寻找子群内的最优解以及全局的最优解。重复以上步骤，直到满足终止条件。4.2举例具体演算分析例如，设VRP问题中发货点任务数为7,车辆数为3,若某粒子的位置向量X为：发货点任务号：1234567Xv:1222233Xr:1431221则该粒子对应解路径为：车1:01一0车2:0一4一5一3一2一0车3:0一7一6一0粒子速度向量V与之对应表示为V

7、v和Vr该表示方法的最大优点是使每个发货点都得到车辆的配送服务，并限制每个发货点的需求仅能由某一车辆来完成，使解的可行化过程计算大大减少Z®然该表示方法的维数较高，但由于PSO算法在多维寻优问题有着非常好的特性，维数的增加并未增加计算的复杂性，这一点在实验结果中可以看到五、模型的建立与求解在本题中，需要分别计算以下几个内容，计算需求点与中心仓库及各需求点间距离，利用粒子群优化算法，求出函数的全局最优位置和最后得到的优化极值。5.1 需求点与中心仓库及各需求点间距离利用直角三角形勾股定理，求斜边长度。A(xi,y3B(x2,y2),直角坐标系中求A,B两点之间距离AB=,J(y2-y1

8、)2+(x2-x1)2距离01234567007.211142.7255.6665.4974.73313.4161417.2111037.10850.2262.58672.42218.11120.396242.7237.108013.15333.97145.27743.41749.406355.6650.2213.153027.73138.58855.22761.4465.4962.58633.97127.731011.31459.13565.276574.73372.42245.27738.58811.314067.11973.027613.41618.11143.41755.22759.1

9、3567.11906.324671420.39649.40661.465.27673.0276.324605.2粒子群优化算法5.2.1算法实现过程步骤1初始化粒子群粒子群划分成若干个两两相互重叠的相邻子群； 每个粒子位置向量Xv的每一维随机取1K(车辆数)之间的整数，Xr的每一维随机取1L(发货点任务数)之间的实数； 每个速度向量Vv的每一维随机取-(K-1)(K-1)(车辆数)之间的整数，Vr的每一维随机取-(L-1)(L-1)之间的实数； 用评价函数Eval评价所有粒子； 将初始评价值作为个体历史最优解Pi,并寻找各子群内的最优解Pl和总群体内最优解pg步骤2重复执行以下步骤，直到满足终

10、止条件或达到最大迭代次数对每一个粒子,计算Vv、Vr；计算Xv、Xr,其中Xv向上取整；当V、X超过其范围时按边界取值用评价函数Eval评价所有粒子；若某个粒子的当前评价值优于其历史最优评价值,则记当前评价值为该历史最优评价值,同时将当前位置向量记为该粒子历史最优位置Pi;寻找当前各相邻子群内最优和总群体内最优解，若优于历史最优解则更新Pl、Pg5.2.2针对本题0表示中心仓库，设车辆容量皆为q=1.0,由3辆车完成所有任务，初始化群体个数n=40;惯性权重w=0.729;学习因子c1=c2=1.49445;最大代数MaxDT=50;搜索空间维数（未知数个数）D=7;算法得到的最优值的代数及所

11、得到的最优解，预计迭代次数50,共进行20次运算运算次数12345678910总距离217.81230.41217.81217.813；03.04217.81303.04217.81217.81230.41运算次数11121314151617181920总距离217.81217.81230.41217.812>17.81217.81217.81217.81217.81217.81从实验结果分析，15次达到已知最优解，得到的最优总路径为:0>7>6>0>1>0>2>3>4>5>0对应的行车路线为：车辆一：0>7>6，0

12、车辆二：01>0车辆三:0>2>3>4>5>0行车总距离217.81粒子群优化算法达到最优路径50次的代数723217717137411928113314212311718224135836201038565359215762567305592921638943148129379六、模型的评价粒子群优化算法结果分析方法达到最优路径次数未达最优路径次数达到最优路径平均代数达到最优路径平均时间(S)粒子群50028.363.04分析PSO方法，可以看出它与GA等其他演化算法的最大不同在于1)迭代运算中只涉及到初等运算，且运算量非常少；2)每个粒子能直接获取群体历

13、史经验和个体历史经验，比在其他方法中使用精英集(elitism)的方法更有效；3)整个粒子群被划分为几个的子群，且子群之间有一定重叠，从而使收敛于局部最优解的几率大大减少L正因为如此，本文将PSO应用于带时间窗车辆路径问题求解中，取得了很好的效果，有着运算速度快、解的质量与个体数目相关性小、所获得的解质量高等诸多优点七、模型的改进和推广7.1模型的改进针对粒子群优化算法存在的问题，提出了一种新的改进算法一基于粒子进化的多粒子群优化算法。该算法采用局部版的粒子群优化方法，从“粒子进化”和“多种群”两个方面对标准粒子群算法进行改进。多个粒子群彼此独立地搜索解空间，保持了粒子种群的多样性，从而增强了

14、全局搜索能力而适当的“粒子进化”可以使陷入局部最优的粒子迅速跳出，有效的避免了算法“早熟”，提高了算法的稳定性。将基于粒子进化的多粒子群优化算法用于求解非线性方程组。该算法求解精度高、收敛速度快，而且克服了一些算法对初值的敏感和需要函数可导的困难，能较快地求出复杂非线性方程组的最优解。数值仿真结果显示了该算法的有效性和可行性，为求解非线性方程组提供了一种实用的方法。7.2模型的推广作为物流系统优化中的重要一环，合理安排车辆路径、进行物流车辆优化调度可以提高物流经济效益、实现物流科学化。粒子群算法在多维寻优中有着非常好的特性，加入“邻居算子”的粒子群算法能使算法更好的全局寻优。本文的研究表明，改

15、进局部办粒子群算法，能过有效地解决车辆路径问题。八、参考文献1李军，郭耀煌.物流配送车辆优化调度理论与方法M.北京：中国物资出版社,2001.2马炫，彭莅，刘庆.求解带时间窗车辆路径问题的改进粒子群算法.计算机工程与应用，2009,45(27):200-2023姜启源，数学建模，高教出版社，2000年附录需求点与中心仓库及各需求点间距离c=；zuobiao=18542260586971718346913824421840;fori=1:8forj=1:8c(i,j)=sqrt(zuobiao(j,2)-zuobiao(i,2)A2+(zuobiao(j,1)-zuobiao(i,1)A2);e

16、ndendc粒子群优化算法求解主算法clearall;cic;formatlong;%-给定初始化条件c1=1.4962;%学习因子1c2=1.4962;%学习因子2w=0.7298;%惯性权重MaxDT=50;%最大迭代次数D=7;%搜索空间维数(未知数个数)N=40;%初始化群体个体数目%-初始化种群的个体(可以在这里限定位置和速度的范围)fori=1:Nforj=1:D是向离它最近的大整数圆整x1(i,j)=ceil(3*rand();%随机初始化位置ceilx2(i,j)=ceil(7*rand();v1(i,j)=2*(2*rand()-1);%随机初始化速度%v2(i,j)=6*(

17、2*rand()-1);endend%-先计算各个粒子的适应度，并初始化Pbest和gbestfori=1:Ny1(i,:)=x1(i,:);y2(i,:)=x2(i,:);pbest(i)=fitness(y1(i,:),y2(i,:),D);endpg1=x1(1,:);%Pg为全局最优pg2=x2(1,:);fori=2:Niffitness(x1(i,:),x2(i,:),D)<fitness(pg1,pg2,D)pg1=x1(i,:);pg2=x2(i,:);gbest=fitness(pg1,pg2,D);endend%-进入主要循环，按照公式依次迭代，直到满足精度要求for

18、t=1:MaxDTfori=1:Nv1(i,:)=w*v1(i,:)+c1*rand*(y1(i,:)-x1(i,:)+c2*rand*(pg1-x1(i,:);x1(i,:)=x1(i,:)+v1(i,:);x1(i,:)=ceil(x1(i,:);forj=1:Difx1(i,j)<1x1(i,j)=1;endifx1(i,j)>3x1(i,j)=3;endendforj=1:Dx2(i,j)=ceil(7*rand();endiffitness(x1(i,:),x2(i,:),D)<pbest(i)y1(i,:)=x1(i,:);y2(i,:)=x2(i,:);pbest(i)=fitness(y1(i,:),y2(i,:),D);endifpbest(i)<fitness(pg1,pg2,D)pg1=x1(i,:);pg2=