《粒子群优化算法车辆路径问题》由会员分享，可在线阅读，更多相关《粒子群优化算法车辆路径问题（11页珍藏版）》请在金锄头文库上搜索。
1、粒子群优化算法计算车辆路径问题摘要粒子群优化算法中，粒子群由多个粒子组成，每个粒子的位置代表优化问题 在维搜索空间中潜在的解。根据各自的位置，每个粒子用一个速度来决定其飞行 的方向和距离,然后通过优化函数计算出一个适应度函数值 (fitness)。粒子是根 据如下三条原则来更新自身的状态：(1)在飞行过程中始终保持自身的惯性；(2) 按自身的最优位置来改变状态;(3)按群体的最优位置来改变状态。本文主要运用 运筹学中粒子群优化算法解决车辆路径问题。车辆路径问题由Dan tzig 和Ramser于1959年首次提出的,它是指对一系列发货点(或收货点),组成适当的行 车路径，使车辆有序地通过它们，
2、在满足一定约束条件的情况下，达到一定的 目标(诸如路程最短、费用最小，耗费时间尽量少等)，属于完全NP问题，在 运筹、计算机、物流、管理等学科均有重要意义。粒子群算法是最近出现的一种 模拟鸟群飞行的仿生算法，有着个体数目少、计算简单、鲁棒性好等优点，在各 类多维连续空间优化问题上均取得非常好的效果。本文将PSO应用于车辆路径问 题求解中，取得了很好的效果。针对本题，一个中心仓库、7个需求点、中心有3辆车，容量均为1,由这三辆车向7个需求点配送货物，出发点和收车点都是中心仓库。k = 3,q = q2 = q3 =,1 = 7.货= 0.89, g? = 0.14, g3 = 0.28,g4 =
3、 0.33,g5 = 0.21, g6 = O/lg? = 0.57， 且mgi aqk。利用matlab编程，求出需求点和中心仓库、需求点之间的各个距离，用q表示。求满足需求的最小的车辆行驶路径，就是求 m i nz八7 7 Cj Xi。经过初始化粒子群，将初始的适应值作为每个粒子的个i j k体最优解，并寻找子群内的最优解以及全局的最优解。重复以上步骤，直到满足终止条件。本题的最短路径由计算可知为 217.81。关键字：粒子群算法、车辆路径、速度问题的重述一个中心仓库序号为0，7个需求点序号为17,其位置坐标见表1,中心有3辆车，容量均为1,由这三辆车向7个需求点配送货物，出发点和收车点都
4、是 中心仓库。求满足需求的距离最小的车辆行驶路径。问题假设表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 每个需求点由一辆车供应货物。三、符号说明k配送货物车辆数l需求点个数g货物需求量qk配送货物车辆的容量q从点i到j的距离yki需求点i由k车配送Xijk车k
5、从i行驶到j四、问题分析4.1算法分析车辆路径问题(VRP可以描述为有一个中心仓库，拥有K辆车，容量分别为qk =1,2,，K)，负责向L个需求点配送货物，货物需求量为gi (i =1,2,，L)，且maxgi - maxqk ； cj表示从点i至U j的距离。求满足需求的 距离最小的车辆行驶路径。将中心仓库编号为0，需求点编号为1，2，L。数学模型为：min Z =、 CjXjki j ks.t.giYki Xk,ki- yki 1, i 1,2, Lk Xjk 二丫“ j =0,1,丄；“i Xjk =yki,i =0,1,丄；kX 二（Xjk） SXjk =0或 1,i, j =0,1,
6、丄;-k yki =0 或 1,i =0,1,丄;-k其中,需求点i由k车配送1 车k从i行驶驶j否则，Xijk 0 否则k = 3,qi = q2 = q3 = 1,1 = 7.货 物 需 求 量。朋禺“鸟=0.289 = 0.33,g 0.21,g 0.41,g 0.57，利用粒子群优化算法，经过初始化粒子群，将初始的适应值作为每个粒子的个体最优解，并寻找子群内的最优解以及全局的最优解。重复以上步骤，直到满足终止条件。4.2举例具体演算分析例如，设VRP问题中发货点任务数为7,车辆数为3,若某粒子的位置向量X 为：发货点任务号：1 2 3 4 5 6 7X v: 1 2 2 2 2 3 3
7、 X 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虽然该表 示方法的维数较高，但由于PSO算法在多维寻优问题有着非常好的特性，维数 的增加并未增加计算的复杂性，这一点在实验结果中可以看到五、模型的建立与求解在本题中，需要分别计算以下几个内容，计算需求点与中心仓库及各需求 点间距离，利用粒子群优化算法，求出函数的全局最优位置和最后得到的优
8、化极 值。5.1需求点与中心仓库及各需求点间距离利用直角三角形勾股定理，求斜边长度。A（x,yJ，B（x2, y2），直角坐标系中求A,B两点之间距离 AB二,（y2 -力）2 （X2-xJ2距离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.314
9、59.13565.276574.73372.42245.27738.58811.314067.11973.027613.41618.11143.41755.22759.13567.11906.324671420.39649.40661.465.27673.0276.324605.2粒子群优化算法算法实现过程步骤1初始化粒子群 粒子群划分成若干个两两相互重叠的相邻子群； 每个粒子位置向量X v的每一维随机取1K （车辆数）之间的整数，Xr 的每一维随机取1L（发货点任务数）之间的实数； 每个速度向量V v的每一维随机取-（K - 1）（K - 1）（车辆数）之间 的整数,V r的每一维随机取-（
10、L - 1）（L - 1）之间的实数； 用评价函数Eval评价所有粒子； 将初始评价值作为个体历史最优解P i ,并寻找各子群内的最优解P l和总群体内最优解P g步骤2重复执行以下步骤，直到满足终止条件或达到最大迭代次数 对每一个粒子，计算V v、V r；计算X v、X r,其中X v向上取整；当V、X超过其范围时按边界取值 用评价函数E va I评价所有粒子； 若某个粒子的当前评价值优于其历史最优评价值，则记当前评价值为该历史最优评价值，同时将当前位置向量记为该粒子历史最优位置Pi ; 寻找当前各相邻子群内最优和总群体内最优解，若优于历史最优解则更新P I、P g针对本题0表示中心仓库,设
11、车辆容量皆为q= 1. 0,由3辆车完成所有任务，初始化群体个数n= 40;惯性权重w = 0. 729;学习因子c1= c2= 1.49445; 最大代数MaxDT -50 ;搜索空间维数（未知数个数） D = 7;算法得到的最优值的代数及所得到的最优解，预计迭代次数50,共进行20次运算运算次数12345678910总距离217.81230.41217.81217.81 3Q3.04217.81303.04217.81217.81230.41运算次数11121314151617181920总距离217.81217.81230.41217.81 2*17.81217.81217.81217.
12、81217.81217.81从实验结果分析，15次达到已知最优解，得到的最优总路径为:0； 7 6； 0； 1一； 0； 2； 3； 4一； 5； 0 对应的行车路线为：车辆一：0760车辆二：010车辆三:0 2 3 4 5 0行车总距离217.81粒子群优化算法达到最优路径50次的代数723217717137411928113314212311718224135836201038565359215762567305592921638943148129379六、模型的评价粒子群优化算法结果分析方法达到最优路径次数未达最优路径次数达到最优路径平均代数达到最优路径平均时间（S）粒子群50028.
13、363.04分析PSO方法,可以看出它与GA等其他演化算法的最大不同在于1）迭代运算中只涉及到初等运算，且运算量非常少；2）每个粒子能直接获取群体历史经验和个体历史经验，比在其他方法中使用精英集（elit ism ）的方法更有效；3）整个粒子群被划分为几个的子群，且子群之间有一定重叠，从而使收敛于局 部最优解的几率大大减少L正因为如此，本文将PSO应用于带时间窗车辆路径问题求解中，取得了很好的 效果，有着运算速度快、解的质量与个体数目相关性小、所获得的解质量高等诸 多优点七、模型的改进和推广7.1模型的改进针对粒子群优化算法存在的问题，提出了一种新的改进算法基于粒子进 化的多粒子群优化算法。该
14、算法采用局部版的粒子群优化方法，从“粒子进化” 和“多种群” 两个方面对标准粒子群算法进行改进。 多个粒子群彼此独立地搜索 解空间， 保持了粒子种群的多样性， 从而增强了全局搜索能力而适当的 “粒子进 化”可以使陷入局部最优的粒子迅速跳出，有效的避免了算法“早熟” ，提高了 算法的稳定性。将基于粒子进化的多粒子群优化算法用于求解非线性方程组。该算法求解 精度高、收敛速度快，而且克服了一些算法对初值的敏感和需要函数可导的困难， 能较快地求出复杂非线性方程组的最优解。 数值仿真结果显示了该算法的有效性 和可行性，为求解非线性方程组提供了一种实用的方法。7.2 模型的推广 作为物流系统优化中的重要一环，合
