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

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

摘要

粒子群优化算法中,粒子群由多个粒子组成,每个粒子的位置代表优化问题在D 维搜索空间中潜在的解。根据各自的位置,每个粒子用一个速度来决定其飞行的方向和距离,然后通过优化函数计算出一个适应度函数值(fitness)。粒子是根据如下三条原则来更新自身的状态:(1)在飞行过程中始终保持自身的惯性;(2)按自身的最优位置来改变状态;(3)按群体的最优位置来改变状态。本文主要运用运筹学中粒子群优化算法解决车辆路径问题。车辆路径问题 由Dan tzig 和Ram ser 于1959年首次提出的, 它是指对一系列发货点(或收货点) , 组成适当的行车路径, 使车辆有序地通过它们, 在满足一定约束条件的情况下, 达到一定的目标(诸如路程最短、费用最小, 耗费时间尽量少等) , 属于完全N P 问题, 在运筹、计算机、物流、管理等学科均有重要意义。粒子群算法是最近出现的一种模拟鸟群飞行的仿生算法, 有着个体数目少、计算简单、鲁棒性好等优点, 在各类多维连续空间优化问题上均取得非常好的效果。本文将PSO 应用于车辆路径问题求解中, 取得了很好的效果。

针对本题，一个中心仓库、7个需求点、中心有3辆车，容量均为1，由这三辆车向7个需求点配送货物，出发点和收车点都是中心仓库。1233,1,7.k q q q l =====货物需求

量12345670.89,0.14,0.28,0.33,0.21,0.41,0.57

g g g g g g g =======，且m a x i k g q ≤。利用matlab 编程，求出需求点和中心仓库、需求点之间的各

个距离，用ij c 表示。求满足需求的最小的车辆行驶路径，就是求

m i n i j i j k i j k Z c x =∑∑∑

。经过初始化粒子群，将初始的适应值作为每个粒子的个

体最优解，并寻找子群内的最优解以及全局的最优解。重复以上步骤，直到满足终止条件。本题的最短路径由计算可知为217.81。

关键字：粒子群算法、车辆路径、速度

一、问题的重述

一个中心仓库序号为0，7个需求点序号为1~7，其位置坐标见表1，中心有3辆车，容量均为1，由这三辆车向7个需求点配送货物，出发点和收车点都是中心仓库。求满足需求的距离最小的车辆行驶路径。

表1 仓库中心坐标和需求点坐标及需求量

二、问题假设

1．现实生活中中心仓库以及各个需求点之间军事直线连接，两点之间距离即为坐标系中两点坐标间距离。

2．不因天气及失火等原因车辆停止运输。

3．每个需求点由一辆车供应货物。

三、符号说明

2

3

四、 问题分析

4.1算法分析

车辆路径问题（VRP ）可以描述为有一个中心仓库，拥有K 辆车，容量分别为),,2,1(K k q k =，负责向L 个需求点配送货物，货物需求量为

),,2,1(L i g i =，且k i q g m a x m

a x ≤；ij c 表示从点i 到j 的距离。求满足需求的距离最小的车辆行驶路径。

将中心仓库编号为0，需求点编号为1，2，…，L 。

数学模型为:

m in ij ijk i j k Z c

x =∑∑∑

s.t.k q y g i k ki i ?≤∑,

L i y k ki ,,2,1,1 ==∑

k L j y x kj i ijk ?==∑;,,1,0,

k L i y x

ki j ijk

?==∑;,,1,0,

4 S x X ijk ∈=)(

k

L j i x ijk ?==;,,1,0,,10 或 k L i y ki ?==;,,1,0,10 或

其中，???=否则车配送由需求点01k i y ki

，???=否则0行驶驶从车1j i k x ijk 在本题中，1233,1,7.k q q q l =====货物

需求量12345670.89,0.14,0.28,0.33,0.21,0.41,0.57g g g g g g g =======，利用粒子群

优化算法，经过初始化粒子群，将初始的适应值作为每个粒子的个体最优解，并寻找子群内的最优解以及全局的最优解。重复以上步骤，直到满足终止条件。

4.2举例具体演算分析

例如, 设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 算法在多维寻优问题有着非常好的特性, 维数的增加并未增加计算的复杂性, 这一点在实验结果中可以看到

五、 模型的建立与求解

5

在本题中，需要分别计算以下几个内容，计算需求点与中心仓库及各需求点间距离，利用粒子群优化算法，求出函数的全局最优位置和最后得到的优化极值。

5.1需求点与中心仓库及各需求点间距离

利用直角三角形勾股定理，求斜边长度。1122(,)(,)A x y B x y ，，直角坐标系中求A,B

两点之间距离AB =

5.2粒子群优化算法 5.2.1算法实现过程 步骤1 初始化粒子群

① 粒子群划分成若干个两两相互重叠的相邻子群;

② 每个粒子位置向量X v 的每一维随机取1～ K (车辆数) 之间的整数, X r 的每一维随机取1～L (发货点任务数) 之间的实数;

③ 每个速度向量V v 的每一维随机取- (K - 1)～ (K - 1) (车辆数) 之间的整数,V r 的每一维随机取- (L - 1)～ (L - 1) 之间的实数; ④ 用评价函数Eval 评价所有粒子;

⑤ 将初始评价值作为个体历史最优解P i , 并寻找各子群内的最优解P l 和

6 总群体内最优解P g

步骤2 重复执行以下步骤, 直到满足终止条件或达到最大迭代次数

①对每一个粒子, 计算V v 、V r ; 计算X v 、X r , 其中X v 向上取整; 当V 、X 超过其范围时按边界取值

② 用评价函数E va l 评价所有粒子;

③ 若某个粒子的当前评价值优于其历史最优评价值, 则记当前评价值为该历史最优评价值, 同时将当前位置向量记为该粒子历史最优位置P i ;

④ 寻找当前各相邻子群内最优和总群体内最优解, 若优于历史最优解则更新P l 、P g

5.2.2针对本题

0表示中心仓库, 设车辆容量皆为q = 1. 0, 由3辆车完成所有任务，初始化

群体个数n = 40; 惯性权重w = 0. 729;学习因子 c 1= c 2= 1. 49445; 最大代数50MaxDT =；搜索空间维数（未知数个数）7;D =

算法得到的最优值的代数及所得到的最优解，预计迭代次数50，共进行20次运算

从实验结果分析，15次达到已知最优解，得到的最优总路径为：

0760*******→→→→→→→→→→

对应的行车路线为：

车辆一：0760→→→

车辆二：010→→

车辆三:023450→→→→→

行车总距离 217.81

粒子群优化算法达到最优路径50次的代数

六、模型的评价

粒子群优化算法结果分析

分析PSO 方法, 可以看出它与GA 等其他演化算法的最大不同在于

1) 迭代运算中只涉及到初等运算, 且运算量非常少;

2) 每个粒子能直接获取群体历史经验和个体历史经验, 比在其他方法中使用精英集(elit ism ) 的方法更有效;

3) 整个粒子群被划分为几个的子群, 且子群之间有一定重叠, …… 此处隐藏：4793字，全部文档内容请下载后查看。喜欢就下载吧 ……