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

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

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

3、 。k 3, q1 q2q3 1, l 7.货物需求量g1 0.89, g20.14, g3 0.28,g40.33, g50.21, g60.41, g7 0.57，且m gi aqxk 。利用 matlab 编程，求出需求点和中心仓库、需求点之间的各个 距 离 ， 用 cij 表 示 。 求 满 足 需 求 的 最 小 的 车 辆 行 驶 路 径 ， 就 是 求m i nzci j xi j。经过初始化粒子群，将初始的适应值作为每个粒子的个kijk1体最优解，并寻找子群内的最优解以及全局的最优解。重复以上步骤， 直到满足终止条件。本题的最短路径由计算可知为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.57二、问题假设1现实生活中中心仓库以及各个需求点之间军事直线连接，两点之间距离即为坐标系中两点坐标间距离。2不因天气及失

5、火等原因车辆停止运输。3每个需求点由一辆车供应货物。三、符号说明2k配送 物 数l需求点个数gi 物需求量qk配送 物 的容量cij从点 i 到 j 的距离yki需求点 i 由 k 配送xijk车 k 从 i 行 到 j四、问题分析4.1 算法分析 路径 （）可以描述 有一个中心 ， 有k ，容量vrp分 别为 qk ( k 1,2, k ) ， 负 责 向 l 个 需求 点 配 送 货 物 ， 货 物 需求 量 为gi (i1,2, l ) ，且 max gimax qk ； cij 表示从点i 到 j 的距离。求 足需求的距离最小的 行 路径。将中心 号 0，需求点 号 1， 2， l。数

6、学模型 :min zcij xijkijks.t.gi ykiqk ,kiyki1, i1,2, lkxijkykj , j0,1, l;kixijkyki , i0,1, l;kj3x( xijk )sxijk0或1,i , j0,1, l;kyki0或1,i0,1, l; k其中，1需求点 i 由k车配送1车k从i行驶驶 jyki， x0否则ijk0否则在本题中，k3,q1 q2q3 1,l7. 货物需求量g10.89, g2 0.14, g3 0.28,g40.33, g50.21, g60.41, g70.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 45 3 2 0车 3: 0 7 6 0粒子速度向量 v 与之对应表示为 v v 和 v r该表示方法的最大优点是使每个发货点都得到车辆的配送服务 , 并限制每个发货点的需求仅能由某一车辆来完成 , 使解的可行化过程计算大大减少 z虽然该表

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

9、61417.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.13567.11906.324671420.39649.40661.465.27673.0276.324605.

10、2 粒子群优化算法5.2.1 算法实现过程步骤 1初始化粒子群粒子群划分成若干个两两相互重叠的相邻子群;每个粒子位置向量 x v 的每一维随机取 1 k ( 车辆数 ) 之间的整数 , x r的每一维随机取 1l( 发货点任务数 ) 之间的实数 ;每个速度向量 v v 的每一维随机取 - ( k - 1) ( k - 1) (车辆数 ) 之间的整数 , v r 的每一维随机取 - ( l - 1) ( l- 1)之间的实数 ;用评价函数 eval 评价所有粒子 ;将初始评价值作为个体历史最优解p i ,并寻找各子群内的最优解 p l和5总群体内最优解 p g步骤 2重复执行以下步骤 ,直到满足

11、终止条件或达到最大迭代次数对每一个粒子 ,计算 v v、v r ;计算 x v、x r ,其中 x v 向上取整 ;当 v 、x 超过其范围时按边界取值 用评价函数 e va l评价所有粒子 ; 若某个粒子的当前评价值优于其历史最优评价值,则记当前评价值为该历史最优评价值 ,同时将当前位置向量记为该粒子历史最优位置p i ; 寻找当前各相邻子群内最优和总群体内最优解,若优于历史最优解则更新p l 、 p g5.2.2针对本题表示中心仓库,设车辆容量皆为 q0,由 辆车完成所有任务，初始化0= 1.3群体个数n惯性权重 w= 0. 729;学习因子c1=c2= 1. 49445;最大代数= 40

12、;maxdt50；搜索空间维数（未知数个数）d7;算法得到的最优值的代数及所得到的最优解，预计迭代次数 50，共进行 20次运算运算次数 12345678910总距离217.81 230.41217.81217.81 303.04217.81 303.04217.81217.81230.41运算次数 11121314151617181920总距离217.81 217.81230.41217.81 217.81217.81 217.81217.81217.81217.81从实验结果分析， 15次达到已知最优解，得到的最优总路径为：07601023450对应的行车路线为：车辆一：0760车辆二：0

13、10车辆三 : 0 2 3 4 5 0行车总距离217.81粒子群优化算法达到最优路径50次的代数7232177171374119628113314212311718224135836201038565359215762567305592921638943148129379六、模型的评价粒子群优化算法结果分析达到最优未达最优达到最优路达到最优路径平方法路径次数路径次数径平均代数均时间（ s）粒子群50028.363.04分析 pso 方法 ,可以看出它与 ga 等其他演化算法的最大不同在于1) 迭代运算中只涉及到初等运算 , 且运算量非常少 ;2) 每个粒子能直接获取群体历史经验和个体历史经验

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

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

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

17、obiao(i,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:dx1(i,j)=ceil(3*rand(); %随机初始化位置ceil是向离它最近的大整数圆整x2(i,j)=ceil

18、(7*rand();9v1(i,j)=2*(2*rand()-1); %随机初始化速度%v2(i,j)=6*(2*rand()-1);endend%-先计算各个粒子的适应度，并初始化pbest和 gbest-for 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,:);gbes

19、t=fitness(pg1,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)3x1(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