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

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

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

3、 7. 货物需求量g1 0.89,g2 0.14,g3 0.28,g4 0.33,g5 0.21,g6 0.41,g7 0.57， 且m gi aqxk 。利用matlab 编程，求出需求点和中心仓库、需求点之间的各个 距 离 ， 用cij 表 示 。 求 满 足 需 求 的 最 小 的 车 辆 行 驶 路 径 ， 就 是 求m i nZci j xi j。经过初始化粒子群，将初始的适应值作为每个粒子的个 kijk体最优解，并寻找子群内的最优解以及全局的最优解。重复以上步骤，直到满足终止条件。本题的最短路径由计算可知为217.81关键字：粒子群算法、车辆路径、速度一、 问题的重述一个中心仓库序

4、号为0， 7 个需求点序号为17， 其位置坐标见表1， 中心有3 辆车，容量均为1，由这三辆车向7 个需求点配送货物，出发点和收车点都是中心仓库。求满足需求的距离最小的车辆行驶路径。表 1 仓库中心坐标和需求点坐标及需求量序号01234567坐标（ 18， 54）（ 22， 60）（ 58， 69）（ 71， 71）（ 83， 46）（ 91 ， 38）（ 24， 42）（ 18， 40）需求量00.890.140.280.330.210.410.571现实生活中中心仓库以及各个需求点之间军事直线连接，两点之间距离即为 坐标系中两点坐标间距离。2不因天气及失火等原因车辆停止运输。3每个需求点由

5、一辆车供应货物。三、 符号说明k配送货物车辆数l需求点个数gi货物需求量qk配送货物车辆的容量cij从点i 到 j 的距离yki需求点i 由 k 车配送xijk车 k 从 i 行驶到j问题分析4.1 算法分析车辆路径问题(VRP)可以描述为有一个中心仓库，拥有K 辆车，容量分 别 为qk(k 1,2, ,K) ， 负 责 向 L 个 需 求 点 配 送 货 物 ， 货 物 需 求 量 为gi(i 1,2, ,L)，且maxgi maxqk； cij 表示从点i 到 j 的距离。求满足需求的距离最小的车辆行驶路径。将中心仓库编号为0，需求点编号为1 ， 2，L。数学模型为:min Zcijxij

6、ki jks.t.gi yki qk, kyki1,i 1,2, ,Lkxijkykj, j 0,1,L; kxijkyki,i 0,1,L; kX(xijk)Sxijk0或 1,i, j 0,1,L; kyki0或1,i 0,1, , L; k其中，1 yki0需求点 i 由 k车配送 ，1 车k从i行 驶驶 j否则xijk0 否 则在 本 题 中 ， k 3,q1q2q3 1,l 7. 货 物 需 求 量g1 0.89,g2 0.14,g3 0.28,g4 0.33, g5 0.21,g6 0.41,g7 0.57，利用粒子群优化算法，经过初始化粒子群，将初始的适应值作为每个粒子的个体最优

7、解，并寻找子群内的最优解以及全局的最优解。重复以上步骤，直到满足终止条件。4.2 举例具体演算分析例如 , 设 VRP 问题中发货点任务数为7, 车辆数为 3, 若某粒子的位置向量X为:发货点任务号: 1 2 3 4 5 6 7X v: 1 2 2 2 2 3 3X r: 1 4 3 1 2 2 1则该粒子对应解路径为:车 1: 0 1 0车 2: 0 4 5 3 2 0车 3: 0 7 6 0粒子速度向量V 与之对应表示为V v 和 V r该表示方法的最大优点是使每个发货点都得到车辆的配送服务, 并限制每个发货点的需求仅能由某一车辆来完成, 使解的可行化过程计算大大减少Z虽然该表示方法的维数

8、较高, 但由于 PSO 算法在多维寻优问题有着非常好的特性, 维数的增加并未增加计算的复杂性, 这一点在实验结果中可以看到五、 模型的建立与求解在本题中，需要分别计算以下几个内容，计算需求点与中心仓库及各需求点间距离，利用粒子群优化算法，求出函数的全局最优位置和最后得到的优化极值。需求点与中心仓库及各需求点间距离利用直角三角形勾股定理，求斜边长度。A(x1,y1)， B(x2, y2)，直角坐标系中求 A,B 两点之间距离AB(y2 y1)2 (x2 x1)2距离01234567007.211142.7255.6665.4974.73313.4161417.2111037.10850.2262

9、.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.13567.11906.324671420.39649.40661.465.27673.0276.32460粒子群优化算法算法实现过程步骤 1 初始化粒子群 T

10、OC o 1-5 h z 粒子群划分成若干个两两相互重叠的相邻子群;每个粒子位置向量X v 的每一维随机取1 K ( 车辆数 ) 之间的整数, X r的每一维随机取1 L(发货点任务数) 之间的实数;每个速度向量V v 的每一维随机取- ( K - 1) ( K - 1) ( 车辆数 ) 之间的整数 , V r 的每一维随机取- ( L - 1) ( L - 1) 之间的实数;用评价函数Eval 评价所有粒子;将初始评价值作为个体历史最优解P i , 并寻找各子群内的最优解P l 和总群体内最优解P g步骤 2 重复执行以下步骤, 直到满足终止条件或达到最大迭代次数对每一个粒子, 计算 V v

11、、 V r ; 计算X v、 X r , 其中 X v 向上取整 ; 当 V 、X 超过其范围时按边界取值用评价函数E va l 评价所有粒子;若某个粒子的当前评价值优于其历史最优评价值, 则记当前评价值为该历史最优评价值, 同时将当前位置向量记为该粒子历史最优位置P i ;寻找当前各相邻子群内最优和总群体内最优解, 若优于历史最优解则更新P l、 P g针对本题0表示中心仓库, 设车辆容量皆为q= 1. 0, 由 3辆车完成所有任务，初始化群体个数n= 40; 惯性权重w = 0. 729; 学习因子c1= c2= 1. 49445; 最大代数 TOC o 1-5 h z MaxDT 50

12、；搜索空间维数（未知数个数）D 7;算法得到的最优值的代数及所得到的最优解，预计迭代次数50， 共进行 20次运算运算次数12345678910总距离217.81230.41217.81217.81 303.04217.81303.04217.81217.81230.41运算次数11121314151617181920总距离217.81217.81230.41217.81 217.81217.81217.81217.81217.81217.81 TOC o 1-5 h z 从实验结果分析，15次达到已知最优解，得到的最优总路径为：07601023450对应的行车路线为：车辆一：0760车辆二：

13、010车辆三 : 023450行车总距离217.81粒子群优化算法达到最优路径50次的代数7232177171374119 7.1 模型的改进 28113314212311718224135836201038565359215762567305592921638943148129379六、 模型的评价粒子群优化算法结果分析方法达到最优 路径次数未达最优 路径次数达到最优路 径平均代数达到最优路径平均时间(S)粒子群50028.363.04分析PSO 方法, 可以看出它与GA 等其他演化算法的最大不同在于 TOC o 1-5 h z 迭代运算中只涉及到初等运算, 且运算量非常少;每个粒子能直接获

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

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

16、寻优。本文的研究表明，改进局部办粒子群算法，能过有效地解决车辆路径问题。八、 参考文献李军 , 郭耀煌 . 物流配送车辆优化调度理论与方法M . 北京 : 中国物资出版社, 2001.马炫，彭芃，刘庆. 求解带时间窗车辆路径问题的改进粒子群算法. 计算机工程与应用，2009， 45（ 27） ： 200-202姜启源， 数学建模，高教出版社，2000 年附录需求点与中心仓库及各需求点间距离c=;zuobiao=18 5422 6058 6971 7183 4691 3824 4218 40;for i=1:8for j=1:8c(i,j)=sqrt(zuobiao(j,2)-zuobiao(i

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

18、1(i,j)=2*(2*rand()-1); %随机初始化速度%v2(i,j)=6*(2*rand()-1);endend% 先计算各个粒子的适应度，并初始化Pbest 和 gbestfor i=1:Ny1(i,:)=x1(i,:);y2(i,:)=x2(i,:);pbest(i)=fitness(y1(i,:),y2(i,:),D);endpg1=x1(1,:); %Pg为全局最优pg2=x2(1,:);for i=2:Nif fitness(x1(i,:),x2(i,:),D)fitness(pg1,pg2,D)pg1=x1(i,:);pg2=x2(i,:);gbest=fitness(p

19、g1,pg2,D);endend% 进入主要循环，按照公式依次迭代，直到满足精度要求for t=1:MaxDTfor i=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,:);for j=1:Dif x1(i,j)3 x1(i,j)=3;endendfor j=1:Dx2(i,j)=ceil(7*rand();endif fitness(x1(i,:),x2(i,:),D)pbest(i)y1(i,:)=x1(i,:);y2(i,:)=x2(i,:);pbest(i)=fitness(y1(i,:),y2(i,:),D);endif pbest(i)fitness(pg