论文导读：：“11·15”的上海特大火灾造成了巨大的人员与经济的损失。如果消防车辆能克服交通系统的不畅而更及时赶到的话，或许结果会不一样。因此如何将路径变化运输转化为车辆路径问题（Vehicle RoutingProblem, VRP），并求解恰当的行车路径，对于城市应急以及日常的物流配送企业都有着重大的现实意义及经济价值。文中将微粒群算法（Particle Swarm Optimization, PSO）应用于车辆路径问题，建立车辆路径问题的微粒群算法的数学描述，编译出此问题的程序，并对一个实例进行仿真分析。

　　论文关键词：微粒群算法，车辆路径问题，配送，变化路径

　　0 引言

　　2010年11月15日下午发生在上海胶州路的一场高楼大火失去了58条宝贵的生命。有人质疑过消防人员未能及时赶到，事发地点所处市中心，狭小的马路和拥挤的车流量或许是原因之一。如何更快的到达现场实施救援始终是传统路面交通的一大难题。同样的，近几年来我国因雪灾、地震、火灾等自然灾害和交通堵塞、车祸等人为因素引起的运输路径不畅通的问题，致使物流企业的配送运输带来了巨大的经济损失，面临着严峻的考验。虽然变化路径运输问题的可研究面相当广，但就历史罕见的雪灾和大地震等等的这类情况下，将变化路径运输问题针对物流配送业的车辆路径运输问题进行研究，更具有现实意义，故本文将变化路径运输问题简化为车辆路径问题来研究。同样的，如何选取恰当的车辆路径，加快对客户需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商运作成本，已经成为物流配送企业在物流业中生存一个重要条件。若企业无法使运输成本降低，则往往难以生存，所以研究车辆路径问题是物流配送企业的基础。而将路径的变化考虑进车辆路径问题中，并求得最优路径，就能成为企业的竞争优势，并大大提升在同行业中的竞争力。因此，研究车辆路径问题受到了相当大的重视，除此之外还有其重要的理论意义。要想使车辆路径问题的解达到最优，必然需要将各类算法运用其中来研究，这样不仅可以推动相关算法的研究，如模拟退火算法、遗传算法、神经网络、人工智能等，而且还能在此基础上提出新的算法，这为其他领域类似问题的解决提供了条件和手段。

　　本文采用的是微粒群算法（Particle Swarm Optimization, PSO）来求解车辆路径问题。PSO是一种模拟鸟类觅食机制的进化算法，它是由美国社会心理学家James Kennedy和电气工程师Russell Eberhart在1995年共同提出的一种新的群体智能算法[1]。自提出以来，在国外得到了相关领域众多学者的关注与研究，现在毕业论文提纲，它在函数优化、约束优化、极大极小问题、多目标优化等问题中均取得成功的应用，已经成为进化算法的一个重要分支。所以，我们将这一优化工具用于车辆路径问题的研究中。

　　1 车辆路径问题

　　（1）概念

　　车辆路径问题（Vehicle Routing Problem，简称VRP） 是物流配送优化中关键的一环，其自1959年G Dantzig和J.Ramser等开始进行了初步研究后，由于其应用的广泛性和经济上的重大价值，很快成为国内外学者研究的热点问题。历经多年的研究发现，VRP是NP难问题，将其中最典型的VRP定义为：对一系列发货点和/或收货点，组织适当的行车路径，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）的情况下，达到一定的目标（如路径最短、费用最小、耗费时间尽量少、使用车辆尽量少等）。

　　（2） 问题描述

　　车辆路径问题的示意图见下图（图1-1）：

　　图1-1 车辆路径问题的示意图

　　根据上图，可将车辆路径问题描述如下：

　　有一个配送中心D（即图1-1中的场站），共有K辆车，每辆车的运输能力为qk （k = 1，2，……，K），车辆从配送中心D出发，完成运输任务后回到配送中心，每个发货点唯一接受一辆车的服务一次，共有N个发货点的任务需要完成，第i个送货点（i = 1，2，……，N）的货物需求量是gi（i = 1，2，……，N），cij表示从第i个发货点到第j个发货点（i ≠ j，i，j = 1，2，……，N）的运输成本，问题的目标函数通常有车辆数和运输成本，首先要最小化车辆数，然后最小化总运输成本，并满足以下条件：

　　①每条运输路径上各送货点的需求量之和不超过每辆汽车的运输能力；

　　②每条运输路径的长度不超过汽车一次配送的最大距离；

　　③每个送货点的需求必须满足且只能由一辆车送货。

　　（3） 数学模型

　　根据文献[2]，由上述问题描述，将配送中心编号为0，发货点编号为1，…，N，任务及配送中心均以点i（i = 0，1，…，N）来表示杂志网。定义变量如下：

　　1，车k从点i行驶到点j

　　xijk=

　　0，否则

　　1，发货点i的任务由车k完成

　　yki=

　　0，否则

　　可以得出该问题的数学模型如下所示：

　　i j k

　　Min Z = ∑ ∑ ∑cijxijk 目标函数

　　i

　　s.t. ∑giyki ≤ qkk = 1，2，……，K 满足车辆的容量约束

　　∑yki = 1 保证每个发货点的需求仅能由一辆车来完成

　　i

　　∑xijk = yki

　　保证每个发货点都能得到车辆的配送服务

　　j

　　∑xijk = ykj

　　xijk ∈{0,1}

　　yki ∈{0,1}

　　i，j = 0，1，…，N

　　cij表示从第i个发货点到第j个发货点（i ≠ j，i毕业论文提纲，j= 1，2，……，N）的运输成本，其含义可以是距离、费用、时间等。本文因为研究的侧重点在运输路径的变化，故在此cij表示距离。

　　2 微粒群算法

　　（1） 基本思想

　　微粒群算法最早是在1995年由美国心理学家James Kennedy和电气工程师Russell Eberhart共同提出的，并在1995年的IEEE国际神经网络学术会议上正式发表了题为“Particle Swarm Optimization”的文章，标志着微粒群算法的诞生。

　　微粒群算法的基本思想1是受他们早期对许多鸟类的群体行为进行建模与仿真研究结果的启发，并且利用了生物学家Frank Heppner的生物群体模型，这一模型反映了：鸟类被吸引飞向栖息地。具体描述如下：一开始每一只鸟均无特定目标进行飞行，直到有一只鸟飞到栖息地，当设置期望栖息比期望留在鸟群中具有较大的适应值时，每一只鸟都将离开群体而飞向栖息地，随后就自然形成了鸟群。由于鸟类使用简单的规则确定自己的飞行方向与飞行速度（实质上，每一只鸟都试图停在鸟群中而又不相互碰撞），当一只鸟飞离鸟群而飞向栖息地时，将导致它周围的其他鸟也飞向栖息地。这些鸟一旦发现栖息地，将降落在此，驱使更多的鸟落在栖息地，直到整个鸟群都落在栖息地。鸟类寻找栖息地与对一个特定问题寻找解很类似，符合信念的社会认知观点。于是受其启发Eberhart和Kennedy对模型进行修正，便有了可以广泛求解优化问题的微粒群算法。

　　（2） 数学表示

　　由参考文献[1]和[5]可知，微粒群算法的数学表示如下：

　　设搜索空间的维数为n，微粒总数为k。f（X）为目标函数，对于最小化问题，目标函数的值越小越好，目标函数的值也通常被称为适应值。

　　设：

　　第i个微粒的当前位置记为：Xi =（xi1,xi2,…，xin）；

　　第i个微粒的当前飞行速度记为：Vi =（vi1,vi2,…，vin）；

　　第i个微粒所经历的最好位置记为：Pi =（pi1,pi2,…，pin），也称为pbest。当微粒在此位置时，具有最好的适应值，我们称其为“个体最佳位置”。每次“飞行”后，微粒的当前适应值比前面所有飞行的适应值优，则个体最佳位置用当前位置替代；反之则保留不变。

　　所有微粒所经历的最好位置表示为g，即Pg，为所有Pi（i=1，2，…，k）中的最优，也称为gbest。

　　根据上述定义，微粒群算法的进化方程可以表示如下：

　　vij（t+1）=w*vij（t）+c1*r1*（pij（t）-xij（t））+ c2*r2*（pgj（t）- xij（t））（2.1）

　　xij（t+1）= xij（t）+ vij（t+1）（2.2）

　　参数说明：

　　在上式（2.1）和（2.2）中：下标“i”表示第i个微粒；下标“j”表示微粒的第j维；“t”表示第t代；“w”为权重因子，根据文献[3]，w较大适用于对解空间进行大范围探查，w较小适于进行小范围开挖；c1，c2为加速度常数，可加快收敛且不易陷入局部最优，c1调节微粒飞向自身最好位置方向的步长，c2调节微粒向全局最好位置飞行的步长，通常在0～2之间取值；r1，r2为两个相互独立的随机数，在（0,1）之间满足均匀分布；vij通常将搜索范围限制在一定的空间范围[-Xmax，Xmax] 之内，为了使微粒在搜索空间内飞行而不离开，将vij设定在一定区间内[-vmax，vmax]内变化。

　　（3） 流程及其流程图

　　基本微粒群算法的流程可描述为：

　　Step 1：初始化一群微粒，包括随机位置和速度。

　　初始化过程：

　　①设定群体规模为n；

　　②对任意i，j，在[-Xmax，Xmax]内服从均匀分布产生xij；

　　③对任意i，j，在[-vmax，vmax]内服从均匀分布产生vij；

　　④对任意i，设yi = xi。

　　Step 2：评价每个微粒的适应度。

　　Step 3：对每个微粒，将其适应值与其经历过的最好位置pbest作比较，如果较好毕业论文提纲，则将其作为当前的最好位置pbest。

　　Step 4：对每个微粒，将其适应值与全局所经历的最好位置gbest作比较，如果较好，则重新设置gbest。

　　Step 5：根据式（3.1）、（3.2）变化微粒的速度和位置。

　　Step 6：如未达到结束条件（通常为足够好的适应值或达到一个预设最大Gmax），则返回Step 2。

　　根据上文的算法流程步骤，我们可以用图来形象地表示其流程，具体见图2-1：

　　图2-1 基本微粒群算法的流程图

　　3 变化路径的PSO求解

　　（1）表达式

　　如何将微粒群算法应用于车辆路径问题的关键是要构造一个正确而且合适的微粒表达式，并且要使每个微粒与其每个解对应。如前所述，VRP问题要求每个发货点都必须得到车辆的配送服务，而且每个发货点的服务只能限制一辆车来完成。由参考文献[3]的思想并根据本文所用实例做出适当的调整，可以构造出这样的问题：

　　首先，假设构造一个N维的空间微粒的位置向量z，使它对应于有N个发货任务点的VRP问题，其中z的数值代表车辆编号。例如，某VRP问题中有8个发货点任务，车辆数为3，某个微粒的位置向量z =[1 2 2 3 3 1 1 2]，表示第1、6、7个任务点由第1辆车配送；第2、3、8个任务点由第2辆车配送；第4、5个任务点由第3辆车配送。

　　然后再采用整数编码，即对于N个发货点，k辆车的VRP问题，将1～N的整数随机排列并赋给每个发货点，再在发货点序列中插入（k-1）个0，这样把发货点序列分成k段，每一段就代表一辆车的行车路径。由此产生一组新的种群，种群中每个微粒即对应一个（N+k-1）维向量，也就是问题一个解。

　　例如，设某VRP问题有3辆车运输，6个发货点，若某微粒的位置向量X为：5 3 0 6 1 4 0 2，则表示该粒子对应的路径为：

　　第1辆车：0→5→3→0；

　　第2辆车：0→6→1→4→0；

　　第3辆车：0→2→0。

　　这样的表达方式有效地解决了车辆的编码， 而且将VRP转成一个TSP问题， 便于采用传统TSP问题处理方法来求解VRP问题。

　　（2）求解步骤

　　在第二部分中可知，虽然微粒群算法在求解连续空间的问题上表现出很好的优越性，但是对于离散问题（如VRP问题）就不是很方便了。微粒群算法中，微粒下一个位置是通过速度的更新来进行的，但其难以表达。因而实现过程中，在基本微粒群算法的基础上要对其作相应的改进：微粒的下一个位置是通过与全局极值的交叉，最后再变异产生的，这样不仅能简单表示微粒的位置，而且经过变异后还能防止了算法陷入局部极值的可能。根据上面的表达式并且借鉴文献[4]的思想，具体算法步骤如下：

　　① 初始化参数：设微粒数为n，随机产生n个初始解（初始路径）C0，给每个变量w、c1、c2赋值，最大迭代次数为T，有N个发货点，每个发货点的需求量为g，车辆数目为k，车辆载重为q。

　　② 根据当前位置计算每个微粒的适应值（各路径的长度）d，设置当前微粒的适应值为个体极值pbest，取其中最优值为全局极值gbest杂志网。

　　While（迭代次数 < 最大迭代次数T） do

　　For j =1:n

　　③ 对第j个微粒的路径C0（j）与全局极值gbest交叉得到C'（j），然后与个体极值pbest交叉得到C"（j）。交叉方法是：取微粒某个位置的值，若它与要交叉的对象在该位不相等，则微粒这个位置的值等于要交叉的对象在该位的值，若相等则不交叉；交叉完后微粒会有两个位置的值一样，则将另一个位置的值换为交叉时的那个值。

　　例如，C0 = 1 2 3 4 5 6 7，取其第2位与7 6 5 4 3 2 1的第2位进行交叉，则C0交叉后的结果为1 6 3 4 5 2 7。

　　④ 对C"（j）变异得到C1（j）。方法是，从微粒中随机取两个位置，然后将包括这两个位置在内的子序列以反方向插入到原来位置。

　　例如，C"（j） = 1 6 3 4 5 2 7，取第3位和第6位进行变异，则C"（j）变异后得到的结果为C1（j） = 1 6 2 5 4 3 7。

　　⑤ 将交叉变异后的微粒进行判断是否满足车辆的载货量毕业论文提纲，若满足条件，则作为微粒的下一个位置，并计算适应值；若不满足则回到步骤（3）。

　　End For

　　⑥ 比较每个微粒新适应值与其个体极值的大小，若f（i）<pbest，则pbest = f（i），再在个体极值中选择全局极值gbest。

　　End While

　　⑦ 最后输出全局极值gbest及取到全局极值时的最优路径。

　　以上是将微粒群算法应用于车辆路径问题的算法步骤，若要适用于变化路径运输问题，根据本人的理解，只需将受阻的某条（或某几条）路径两点间的距离相对于其他路径设为无穷大，然后按上面的步骤1～步骤7开始计算适应值，由于两点间的距离无穷大其适应值肯定很大，则每个粒子的最优路径肯定不会包含此两点所表示的受阻路径，从而能够得到全局极值，即最优路径值。

　　（3）实例分析

　　现根据参考文献[5]举一个有7个发货点任务的车辆路径问题，各任务节点坐标及货运量见下表3-1。其中序号0表示中心仓库，其余序号1～7为发货点，由2辆车来完成所有发货任务，设每辆车的容量都是2。

　　表3-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）

　　货运量（gi）

　　-

　　0.89

　　0.14

　　0.28

　　0.33

　　0.21

　　0.41

　　0.57

　　用MATLAB 7.0编写程序，并选取微粒数为40，最大迭代次数为200，随机运行50次，最终得到gbest的最小值（即理想最优值）为196.77，最优行车路径为：第1辆车：0→1→2→0；

　　第2辆车：0→6→5→4→3→7→0。

　　两辆车的行车总距离为：75。

　　在50次的运算中，3次达到理想最优值196.77，达优率为88.87%，可见PSO求解VRP有较高的成功率，值得我们进一步探讨。

　　结论与小结

　　通过对课题的研究发现，PSO具有运算速度快、鲁棒性好的特点，是求解离散优化问题（如VRP）的有效算法。但由实验可知PSO算法易陷入局部最优。总而言之PSO对于解决VRP有较高的成功率，对于变化路径的运输具有较大的实际应用价值。

　　本文对VRP仅做了初步的研究，还存在很多问题，在今后的研究中相信还有大量有意义的工作有待开展。

　　参考文献

　　[1]曾建潮，介婧，崔志华。微粒群算法[M].北京：科学出版社。2004.

　　[2]李宁，邹彤，孙德宝。车辆路径问题的粒子群算法研究[J].系统工程学报， 2004，19（6）。

　　[3]张丽艳，庞小红，夏蔚军。带时间窗车辆路径问题的混合粒子群算法[J]，上海交通大学学报， 2006, 40（11）。

　　[4]高尚，杨静宇，群智能算法及其应用[M]，北京：中国水利水电出版社，2006

　　[5]谢晓峰，张文俊，杨之廉。微粒群算法综述[J].控制与决策，2003，18（2）：129-134.