第八组—粒子群算法计算车辆最优路径问题

经济管理学院

管理建模仿真

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

任课教师：胡玉真 老师

2015年5月

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

摘 要：粒子群算法是一种新出现的智能优化算法，本文将其应用于车辆路径最优问题。通过构造车辆路径问题的粒子群表达方法，建立了相应的粒子群算法。通过粒子群算法，能够快速、有效地求得车辆路径问题的优化解。同时我们得出 当车辆数增加，必须增加粒子数来避免出现收敛于局部最优。而且达到最优路径所用时间也越长。当车辆数目一定时，粒子群数目越大，搜索时间越长。当ω值较小时，容易陷入局部最优。随着ω值增大，出现最优路径值的次数增大，实验准确率上升。因此粒子群算法是求解车辆路径问题的一个较好方法。

关键字：粒子群算法；车辆路径问题

一、引言

车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，每个客户都有同数量的货物需求，而配送中心负责向客户提供货物，由一个车队负责分送货物，车队中车的数量的有限的，配送中心组织适当的行车路线使车辆能够有序地通过每个需求点。目标是不仅使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。这类问题有着很强的应用背景，在运筹、计算机、物流、管理等学科均有重要意义。VRP问题吸引了众多领域的专家学者的目光。现实中的车辆路径问题，有许多约束，如有配送里程约束，车型约束等等，问题复杂且求解难度大。近年来，研究者们先后将一般启发式算法和神经网络、遗传算法、禁忌搜索和模拟退火等智能化启发式算法用于VRP问题，取得了较好的效果。粒子群算法( particle swarm optimization，PSO)是近年来出现的一种模拟鸟群飞行捕捉食物的仿生算法，它是从随机解出发，通过迭代寻找最优解。通过适应度来评价。它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。因此本文运用粒子群算法来求解车辆路径问题。

二、文献综述

目前，对VRP问题的求解算法主要分为两大类，精确算法和启发式算法。精

1

确算法主要用于解决具体问题所建立的具体数学模型，并利用数学方法进行逐步求解最终求出其精确的最优解；启发式算法是基于直观、凭经验或受自然界的一些生物原理的启发，从而开发出的能够朝着最优解的方向搜索或靠近的一类算法。精确算法是以牺牲时间和空间的复杂度为代价来换取问题的精确解。对于VRP问题，精确算法只适用于求解小规模的问题中；而启发式算法通常能够在时间和空间复杂度以及解的质量中获得一个平衡，能够以较快的时间求得一个较优的解，这也是近些年来越来越多的学者开始致力于启发式算法的研究各类组合优化问题的原因。在实际的应用中，它们也显示出了它们独特的优势。

启发式算法可以归结为两大类：传统启发式算法和现代启发式算法。尤其是现代启发式算法（如粒子群算法、模拟退火、遗传算法、禁忌搜索和蚁群算法等）正在引起越来越多的学者的关注并投入大量的精力进行深入研究。近年来也有一些学者已经开始尝试混合算法（即将两种或多种算法融合在一起，取长补短）的研究，并将其应用于VRP问题的研究之中，并且也取得了一些值得借鉴的成果，但混合算法的研究还处于起步阶段，缺乏严格的理论证明和效率分析。肖健梅，黄有方在粒子群优化算法中引入随机交换序、PMX算子求解VRP【1】；叶伟采用混合量子粒子群算法对带时间窗的车辆路径问题进行求解【2】。魏明通过离散粒子群算法求解车辆路径问题，能够有效的避免陷入局部最优，但是求解效率不高

【3】。李宁运用优化粒子群算法研究车辆路径问题并且与遗传算法作了对比试验。 结果表明，粒子群算法可以快速、有效求得车辆路径问题的优化解，是求解车辆路径问题的一个较好方案【4】。李德富为了避免粒子群算法求解车辆路径问题容易陷入局部最优，提出了扫描粒子群算法。同时将该算法与经典的粒子群算法和遗传算法做了对比实验，结果表明改进型粒子群算法可以更快速、更有效求得车辆路径问题的最优解【5】。罗先国将局部版粒子群算法应用于非满载车辆路径问题，研究表明该算法提高了搜索最优路径的成功率，能更有效地求解非满载车辆路径问题【6】。

三、粒子群算法的阐述

粒子群算法由Kennedy和Eberhart在1995年提出，该算法模拟鸟类集群飞行觅食的行为。群鸟觅食实际是一个最佳决策过程，与人类决策过程相似。群鸟在觅食过程中，每只鸟的初始状态处于随机位置，且飞行方向也是随机的。每只鸟都不知道食物在哪里，但是随着时间推移，这些处于随机位置的鸟类通过互相学习，信息共享和个体不断积累寻找食物的经验，自己组织聚集成一个群落，并逐渐朝

2

唯一的目标--食物前进。每只鸟能通过一定经验和信息估计目前所处的位置对于寻找到食物有多大价值，即多大的适应值。每只鸟能够记住自己所找到的最好位置，称为局部最优（pbest）。此外还能记住群体中所有个体所能找到的最好位置，称为全局最优（gbest）。整个鸟群的觅食中心都趋向全局最优移动。在生物学上称为同步效应。通过鸟群觅食的为之不断移动，即不断迭代，可以使鸟群朝食物步步逼近。

在PSO算法中，鸟被抽象为没有质量和体积的粒子，并延伸到N维空间，粒子I在N维空间的位置表示为矢量Xi＝(x1，x2，…，xN)，飞行速度表示为矢量Vi＝(v1，v2，…，vN)。每个粒子都有一个由目标函数决定的适应值(fitness value)，并且知道自己到目前为止发现的最好位置(pbest)和现在的位置Xi，这个可以看作是粒子自己的飞行经验．除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值)。这个可以看作是粒子同伴的经验，粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。

1、PSO 算法数学表示如下：

PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”(pbest，gbest)来更新自己。在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。

Vi??*Vi?c1*rand()*(pbesti?Xi)?c2*rand()*(gbesti?Xi)

Xi?Xi?Vi

其中，i＝1，2，...，M。M是该群体中粒子的总数。群体总数一般取20～40，实验表明，对于多数问题，30个粒子就够用了。对较难或特定类别的问题可以取到100～200。粒子数量越多，搜索范围越大，越容易找到全局最优，算法时间也越长。Vi 是粒子的速度；pbest和gbest如前定义；rand()是介于（0、1）之间的随机数；Xi是粒子的当前位置。c1和c2是学习因子。在每一维，粒子都有一个最大限制速度Vmax如果某一维的速度超过设定的Vmax ，那么这一维的速度就被限定为Vmax。粒子群算法是通过调整每一次迭代时每一个粒子在每一维度上移动一定的距离来进行的。速度的改变是随机的，不希望受控制的粒子搜索轨道被扩展到问题空间越来越广阔的范围，并最终大道无穷。如果粒子要进行有效的搜索，必须采取某些措施，使搜索幅度得到衰减。使用一个参数vmax对粒子的速度进行限制。参数vmax有利于防止搜索范围毫无意义地发散，防止粒子群由于飞翔速度过大而之间略过最优目标值。通常vmax设定为每维变化范围的10%-20%。ω称为惯性因

3

子且非负。ω值较大，全局寻优能力强，局部寻优能力弱；ω值较小，全局寻优能力弱，局部寻优能力强。

2、PSO 算法的流程：

Step1：初始化一群微粒(群体规模为m)，包括随机位置和速度；

Step2：评价每个微粒的适应度；

Step3：对每个微粒，将其适应值与其经过的最好位置pbest作比较，如果较好，则将其作为当前的最好位置pbest；

Step4：对所有微粒的最好位置pbest作比较，选出当前群体中的最好位置gbest； Step5：根据上面连个公式调整微粒速度和位置；

Step6：未达到结束条件则转Step2。

一般终止条件设定为一个足够好的适应值或达到一个预设的最大迭代代数Gk 。

四、车辆路径问题的描述以及数学模型

车辆路径问题（VRP）可以描述为有一个中心仓库，拥有K辆车，容量分别为qk(k?1,2,?,K)，负责向L个需求点配送货物，第i个需求点所需货物需求量为gi(i?1,2,?,L)，且maxgi?maxqk即第i个需求点所需货物量的

最大值不能超过第k辆车所能运载的最大货物量。cij表示从点i到j的运输成本，它的含义可以是距离、费用、时间等，在本文中代表距离。求满足货运需求的距离最短的车辆行驶路径。如果我们将中心仓库编号为0，其余需求点编号为1，2，…，L。任意一个需求点用i（i=1，2，…，L）来表示。定义变量如下：

yki???1

?0需求点i由k车配送否则

xijk???1

?0车k从i行驶到j否则

车辆优化调度数学模型：

（1）minZ????cijxijk

ijk

（2）s.t.giyki?

iL?qk,?k(k?1,2...K)

4