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

粒子群优化算法
计算车辆路径问题
摘要
粒子群优化算法中,粒子群由多个粒子组成,每个粒子的位置代表优化问题在D维搜索空间中潜在的解。根据各自的位置,每个粒子用一个速度来决定其飞行的方向和距离,然后通过优化函数计算出一个适应度函数值(fitness)。粒子是根据如下三条原则来更新自身的状态:(1)在飞行过程中始终保持自身的惯性;(2)按自身的最优位置来改变状态;(3)按群体的最优位置来改变状态。本文主要运用运筹学中粒子群优化算法解决车辆路径问题。车辆路径问题由Dan tzig 和Ram ser 于1959年首次提出的, 它是指对一系列发货点(或收货点) , 组成适当的行车路径, 使车辆有序地通过它们, 在满足一定约束条件的情况下, 达到一定的目标(诸如路程最短、费用最小, 耗费时间尽量少等) , 属于完全N P 问题, 在运筹、计算机、物流、管理等学科均有重要意义。粒子群算法是最近出现的一种模拟鸟群飞行的仿生算法, 有着个体数目少、计算简单、鲁棒性好等优点, 在各类多维连续空间优化问题上均取得非常好的效果。本文将PSO 应用于车辆路径问题求解中, 取得了很好的效果。
针对本题,一个中心仓库、7个需求点、中心有3辆车,容量均为1,由这三辆车向7个需求点配送货物,出发点和收车点都是中心仓库。货物需求量,且。利用matlab编程,求出需求点和中心仓库、需求点之间的各个距离,用表示。求满足需求的最小的车辆行驶路径,就是求。经过初始化粒子群,将初始的适应值作为每个粒子的个体最优解,并寻找子群内的最优解以及全局的最优解。重复以上步骤,
直到满足终止条件。本题的最短路径由计算可知为。
关键字:粒子群算法、车辆路径、速度
问题的重述
一个中心仓库序号为0,7个需求点序号为1~7,其位置坐标见表1,中心有3辆车,容量均为1,由这三辆车向7个需求点配送货物,出发点和收车点都是中心仓库。求满足需求的距离最小的车辆行驶路径。
表1 仓库中心坐标和需求点坐标及需求量
序号
0
1
2
3
4
5
6
7
坐标
(18,54)
(22,60)
(58,69)
(71,71)
(83,46)
(91,38)
(24,42)
(18,40)
需求量
0





0..41

问题假设
,两点之间距离即为坐标系中两点坐标间距离。
。
。
符号说明
配送货物车辆数
需求点个数
货物需求量
配送货物车辆的容量
从点i到j的距离
需求点i由k车配送
车k从i行驶到j
问题分析

车辆路径问题(VRP)可以描述为有一个中心仓库,拥有K辆车,容量分别为,负责向L个需求点配送货物,货物需求量为,且;表示从点i到j的距离。求满足需求的距离最小的车辆行驶路径。
将中心仓库编号为0,需求点编号为1,2,…,L。
数学模型为:

.






其中,,
在本题中,货物需求量,利用粒子群优化算法,经过初始化粒子群,将初始的适应值作为每个粒子的个体最优解,并寻找子群内的最优解以及全局的最优解。重复以上步骤,直到满足终止条件。

例如, 设VRP 问题中发货点任务数为7, 车辆数为3, 若某粒子的位置向量X 为:
发货点任务号: 1 2 3 4 5 6 7
X v: 1 2 2 2 2 3 3
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 算法在多维寻优问题有着非常好的特性, 维数的增加并未增加计算的复杂性, 这一点在实验结果中可以看到
模型的建立与求解
在本题中,需要分别计算以下几个内容,计算需求点与中心仓库及各需求点间距离,利用粒子群优化算法,求出函数的全局最优位置和最后得到的优化极值。

利用直角三角形勾股定理,求斜边长度。,直角坐标系中求A,B两点之间距离
距离
0
1
2
3
4
5
6
7
0
0