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

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

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

3、小的车辆行驶路径，就是求。经过初始化粒子群，将初始的适应值作为每个粒子的个体最优解，并寻找子群内的最优解以及全局的最优解。重复以上步骤，直到满足终止条件。本题的最短路径由计算可知为。关键字：粒子群算法、车辆路径、速度一、 问题的重述一个中心仓库序号为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

4、.890.140.280.330.210.410.57二、 问题假设1现实生活中中心仓库以及各个需求点之间军事直线连接，两点之间距离即为坐标系中两点坐标间距离。2不因天气及失火等原因车辆停止运输。3每个需求点由一辆车供应货物。三、 符号说明配送货物车辆数需求点个数货物需求量配送货物车辆的容量从点i到j的距离需求点i由k车配送车k从i行驶到j四、 问题分析4.1算法分析车辆路径问题（VRP）可以描述为有一个中心仓库，拥有K辆车，容量分别为，负责向L个需求点配送货物，货物需求量为，且；表示从点i到j的距离。求满足需求的距离最小的车辆行驶路径。将中心仓库编号为0，需求点编号为1，2，L。数学模型为:

5、 s.t. 其中，在本题中，货物需求量，利用粒子群优化算法，经过初始化粒子群，将初始的适应值作为每个粒子的个体最优解，并寻找子群内的最优解以及全局的最优解。重复以上步骤，直到满足终止条件。 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该表示方法的最大优点是使每个发货点都得到车辆的配送服

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

7、37.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.2粒子群优化算法5.2

8、.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 和总群体内最优解P g步骤2重复执行以下步骤, 直到满足终止条件或达到最大迭代次数对每一个粒子, 计算V v、V r; 计算X

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

10、迭代次数50，共进行20次运算运算次数12345678910总距离217.81230.41217.81217.81303.04217.81303.04217.81217.81230.41运算次数11121314151617181920总距离217.81217.81230.41217.81217.81217.81217.81217.81217.81217.81从实验结果分析，15次达到已知最优解，得到的最优总路径为：对应的行车路线为：车辆一：车辆二：车辆三:行车总距离 粒子群优化算法达到最优路径50次的代数723217717137411928113314212311718224135836201

11、038565359215762567305592921638943148129379六、 模型的评价粒子群优化算法结果分析方法达到最优路径次数未达最优路径次数达到最优路径平均代数达到最优路径平均时间（S）粒子群50028.363.04分析PSO 方法, 可以看出它与GA 等其他演化算法的最大不同在于1) 迭代运算中只涉及到初等运算, 且运算量非常少;2) 每个粒子能直接获取群体历史经验和个体历史经验, 比在其他方法中使用精英集(elit ism ) 的方法更有效;3) 整个粒子群被划分为几个的子群, 且子群之间有一定重叠, 从而使收敛于局部最优解的几率大大减少L正因为如此, 本文将PSO 应用

12、于带时间窗车辆路径问题求解中, 取得了很好的效果, 有着运算速度快、解的质量与个体数目相关性小、所获得的解质量高等诸多优点七、 模型的改进和推广7.1模型的改进针对粒子群优化算法存在的问题，提出了一种新的改进算法基于粒子进化的多粒子群优化算法。该算法采用局部版的粒子群优化方法，从“粒子进化”和“多种群”两个方面对标准粒子群算法进行改进。多个粒子群彼此独立地搜索解空间，保持了粒子种群的多样性，从而增强了全局搜索能力而适当的“粒子进化”可以使陷入局部最优的粒子迅速跳出，有效的避免了算法“早熟”，提高了算法的稳定性。将基于粒子进化的多粒子群优化算法用于求解非线性方程组。该算法求解精度高、收敛速度快，

13、而且克服了一些算法对初值的敏感和需要函数可导的困难，能较快地求出复杂非线性方程组的最优解。数值仿真结果显示了该算法的有效性和可行性，为求解非线性方程组提供了一种实用的方法。7.2模型的推广作为物流系统优化中的重要一环，合理安排车辆路径、进行物流车辆优化调度可以提高物流经济效益、实现物流科学化。粒子群算法在多维寻优中有着非常好的特性，加入“邻居算子”的粒子群算法能使算法更好的全局寻优。本文的研究表明，改进局部办粒子群算法，能过有效地解决车辆路径问题。八、 参考文献1李军, 郭耀煌. 物流配送车辆优化调度理论与方法M . 北京: 中国物资出版社, 2001.2 马炫，彭芃，刘庆. 求解带时间窗车辆

14、路径问题的改进粒子群算法.计算机工程与应用，2009，45（27）：200-2023姜启源，数学建模，高教出版社，2000年附录需求点与中心仓库及各需求点间距离c=;zuobiao=18 5422 6058 6971 7183 4691 3824 4218 40;for i=1:8 for j=1:8 c(i,j)=sqrt(zuobiao(j,2)-zuobiao(i,2)2+(zuobiao(j,1)-zuobiao(i,1)2); endendc粒子群优化算法求解主算法clear all;clc;format long;%-给定初始化条件-c1=1.4962; %学习因子1c2=1.49

15、62; %学习因子2w=0.7298; %惯性权重MaxDT=50; %最大迭代次数D=7; %搜索空间维数（未知数个数）N=40; %初始化群体个体数目%-初始化种群的个体(可以在这里限定位置和速度的范围)-for i=1:N for j=1:D x1(i,j)=ceil(3*rand(); %随机初始化位置ceil 是向离它最近的大整数圆整 x2(i,j)=ceil(7*rand(); v1(i,j)=2*(2*rand()-1); %随机初始化速度 %v2(i,j)=6*(2*rand()-1); endend%-先计算各个粒子的适应度，并初始化Pbest和gbest- for i=1:

16、N y1(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:N if fitness(x1(i,:),x2(i,:),D)<fitness(pg1,pg2,D) pg1=x1(i,:); pg2=x2(i,:); gbest=fitness(pg1,pg2,D); end end%-进入主要循环，按照公式依次迭代，直到满足精度要求- for t=1:MaxDT for i=1:N v1(i,:)=w*v1(i,:)+

17、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:D if x1(i,j)<1 x1(i,j)=1; end if x1(i,j)>3 x1(i,j)=3; end end for j=1:D x2(i,j)=ceil(7*rand(); end if fitness(x1(i,:),x2(i,:),D)<pbest(i) y1(i,:)=x1(i,:); y2(i,:)=x2(i,:); pbest(i)=fitness(

18、y1(i,:),y2(i,:),D); end if pbest(i)<fitness(pg1,pg2,D) pg1=x1(i,:); pg2=x2(i,:); end end end%-最后给出计算结果 disp('*') disp('函数的全局最优位置为：') Solution1=pg1 Solution2=pg2disp('最后得到的优化极值为：')Result=fitness(pg1,pg2,D)disp('*')辅助算法一function result=fitness(x1,x2,D);aa=inf inf inf inf inf inf inf;bb=inf inf inf inf inf inf inf;cc=inf inf inf inf inf inf inf;for i=1:D if x1(i)=1 aa(i)=x2(i); else if x1(i)=2 bb(i)=x2(i); else cc(i)=x2(i); end end