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

(完整版)粒子群优化算法车辆路径问题(完整版)粒子群优化算法车辆路径问题(完整版)粒子群优化算法车辆路径问题粒子群优化算法计算车辆路径问题摘要粒子群优化算法中，粒子群由多个粒子组成，每个粒子的位置代表优化问题在D维搜索空间中潜在的解。根据各自的位置，每个粒子用一个速度来决定其飞行的方向和距离，然后通过优化函数计算出一个适应度函数值(fitness）。粒子是根据如下三条原则来更新自身的状态:（1）在飞行过程中始终保持自身的惯性；（2)按自身的最优位置来改变状态;（3）按群体的最优位置来改变状态。本文主要运用运筹学中粒子群优化算法解决车辆路径问题。车辆路径问题由Dantzig和Ramser于1959年首次提出的,它是指对一系列发货点(或收货点)，组成适当的行车路径，使车辆有序地通过它们,在满足一定约束条件的情况下,达到一定的目标（诸如路程最短、费用最小,耗费时间尽量少等)，属于完全NP问题，在运筹、计算机、物流、管理等学科均有重要意义.粒子群算法是最近出现的一种模拟鸟群飞行的仿生算法，有着个体数目少、计算简单、鲁棒性好等优点,在各类多维连续空间优化问题上均取得非常好的效果。本文将PSO应用于车辆路径问题求解中,取得了很好的效果。针对本题，一个中心仓库、7个需求点、中心有3辆车,容量均为1,由这三辆车向7个需求点配送货物，出发点和收车点都是中心仓库.货物需求量，且。利用matlab编程，求出需求点和中心仓库、需求点之间的各个距离，用表示。求满足需求的最小的车辆行驶路径，就是求。经过初始化粒子群,将初始的适应值作为每个粒子的个体最优解，并寻找子群内的最优解以及全局的最优解。重复以上步骤，直到满足终止条件。本题的最短路径由计算可知为.关键字:粒子群算法、车辆路径、速度问题的重述一个中心仓库序号为0，7个需求点序号为1~7，其位置坐标见表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．不因天气及失火等原因车辆停止运输。3．每个需求点由一辆车供应货物。符号说明配送货物车辆数需求点个数货物需求量配送货物车辆的容量从点i到j的距离需求点i由k车配送车k从i行驶到j问题分析4.1算法分析车辆路径问题（VRP)可以描述为有一个中心仓库,拥有K辆车，容量分别为，负责向L个需求点配送货物，货物需求量为，且；表示从点i到j的距离。求满足需求的距离最小的车辆行驶路径。将中心仓库编号为0，需求点编号为1，2，…，L。数学模型为:s.t.其中，，在本题中,货物需求量,利用粒子群优化算法，经过初始化粒子群,将初始的适应值作为每个粒子的个体最优解，并寻找子群内的最优解以及全局的最优解。重复以上步骤，直到满足终止条件。4.2举例具体演算分析例如，设VRP问题中发货点任务数为7，车辆数为3，若某粒子的位置向量X为：发货点任务号:1234567Xv：1222233Xr:1431221则该粒子对应解路径为：车1：0→1→0车2:0→4→5→3→2→0车3：0→7→6→0粒子速度向量V与之对应表示为Vv和Vr该表示方法的最大优点是使每个发货点都得到车辆的配送服务,并限制每个发货点的需求仅能由某一车辆来完成,使解的可行化过程计算大大减少Z虽然该表示方法的维数较高,但由于PSO算法在多维寻优问题有着非常好的特性，维数的增加并未增加计算的复杂性，这一点在实验结果中可以看到模型的建立与求解在本题中,需要分别计算以下几个内容,计算需求点与中心仓库及各需求点间距离,利用粒子群优化算法，求出函数的全局最优位置和最后得到的优化极值。5。1需求点与中心仓库及各需求点间距离利用直角三角形勾股定理，求斜边长度。,直角坐标系中求A，B两点之间距离距离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.0