微粒群算法在自然灾害等引起的变化路径运输问题中的应用研究

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

2、配送，变化路径0 引言2021年11月15日下午发生在上海胶州路的一场高楼大火失去了58条珍贵的生命。有人质疑过消防人员未能及时赶到，事发地点所处市中心，狭小的马路和拥挤的车流量或许是原因之一。如何更快的到达现场实施救援始终是传统路面交通的一大难题。同样的，近几年来我国因雪灾、地震、火灾等自然灾害和交通堵塞、车祸等人为因素引起的运输路径不畅通的问题，致使物流企业的配送运输带来了巨大的经济损失，面临着严峻的考验。虽然变化路径运输问题的可研究面相当广，但就历史罕见的雪灾和大地震等等的这类情况下，将变化路径运输问题针对物流配送业的车辆路径运输问题进行研究，更具有现实意义，故本文将变化路径运输问题简化

3、为车辆路径问题来研究。同样的，如何选取恰当的车辆路径，加快对客户需求的响应速度，提高效劳质量，增强客户对物流环节的满意度，降低效劳商运作本钱，已经成为物流配送企业在物流业中生存一个重要条件。假设企业无法使运输本钱降低，那么往往难以生存，所以研究车辆路径问题是物流配送企业的根底。而将路径的变化考虑进车辆路径问题中，并求得最优路径，就能成为企业的竞争优势，并大大提升在同行业中的竞争力。因此，研究车辆路径问题受到了相当大的重视，除此之外还有其重要的理论意义。要想使车辆路径问题的解到达最优，必然需要将各类算法运用其中来研究，这样不仅可以推动相关算法的研究，如模拟退火算法、遗传算法、神经网络、人工智能等

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

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

6、述车辆路径问题的示意图见下列图图1-1：图1-1 车辆路径问题的示意图根据上图，可将车辆路径问题描述如下：有一个配送中心D即图1-1中的场站，共有K辆车，每辆车的运输能力为qk (k = 1，2，K)，车辆从配送中心D出发，完成运输任务后回到配送中心，每个发货点唯一接受一辆车的效劳一次，共有N个发货点的任务需要完成，第i个送货点i = 1，2，N的货物需求量是gii = 1，2，N，cij表示从第i个发货点到第j个发货点i j，i，j = 1，2，N的运输本钱，问题的目标函数通常有车辆数和运输本钱，首先要最小化车辆数，然后最小化总运输本钱，并满足以下条件：每条运输路径上各送货点的需求量之和不超

7、过每辆汽车的运输能力；每条运输路径的长度不超过汽车一次配送的最大距离；每个送货点的需求必须满足且只能由一辆车送货。3 数学模型根据文献【2】，由上述问题描述，将配送中心编号为0，发货点编号为1，N，任务及配送中心均以点ii = 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保

8、证每个发货点都能得到车辆的配送效劳 j xijk = ykjxijk 0,1yki 0,1i，j = 0，1，Ncij表示从第i个发货点到第j个发货点i j，i毕业论文提纲，j= 1，2，N的运输本钱，其含义可以是距离、费用、时间等。本文因为研究的侧重点在运输路径的变化，故在此cij表示距离。2 微粒群算法1 根本思想微粒群算法最早是在1995年由美国心理学家James Kennedy和电气工程师Russell Eberhart共同提出的，并在1995年的IEEE国际神经网络学术会议上正式发表了题为Particle Swarm Optimization;的文章，标志着微粒群算法的诞生。微粒群算

9、法的根本思想1是受他们早期对许多鸟类的群体行为进行建模与仿真研究结果的启发，并且利用了生物学家Frank Heppner的生物群体模型，这一模型反映了：鸟类被吸引飞向栖息地。具体描述如下：一开始每一只鸟均无特定目标进行飞行，直到有一只鸟飞到栖息地，当设置期望栖息比期望留在鸟群中具有较大的适应值时，每一只鸟都将离开群体而飞向栖息地，随后就自然形成了鸟群。由于鸟类使用简单的规那么确定自己的飞行方向与飞行速度实质上，每一只鸟都试图停在鸟群中而又不相互碰撞，当一只鸟飞离鸟群而飞向栖息地时，将导致它周围的其他鸟也飞向栖息地。这些鸟一旦发现栖息地，将降落在此，驱使更多的鸟落在栖息地，直到整个鸟群都落在栖息

10、地。鸟类寻找栖息地与对一个特定问题寻找解很类似，符合信念的社会认知观点。于是受其启发Eberhart和Kennedy对模型进行修正，便有了可以广泛求解优化问题的微粒群算法。2 数学表示由参考文献【1】和【5】可知，微粒群算法的数学表示如下：设搜索空间的维数为n，微粒总数为k。fX为目标函数，对于最小化问题，目标函数的值越小越好，目标函数的值也通常被称为适应值。设：第i个微粒的当前位置记为：Xi =xi1,xi2,xin；第i个微粒的当前飞行速度记为：Vi =vi1,vi2,vin；第i个微粒所经历的最好位置记为：Pi =pi1,pi2,pin,也称为pbest。当微粒在此位置时，具有最好的适应

11、值，我们称其为个体最正确位置;。每次飞行;后，微粒的当前适应值比前面所有飞行的适应值优，那么个体最正确位置用当前位置替代；反之那么保存不变。所有微粒所经历的最好位置表示为g，即Pg，为所有Pii=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;为权重因子,根据

12、文献【3】，w较大适用于对解空间进行大范围探查，w较小适于进行小范围开挖；c1，c2为加速度常数，可加快收敛且不易陷入局部最优，c1调节微粒飞向自身最好位置方向的步长，c2调节微粒向全局最好位置飞行的步长，通常在02之间取值；r1，r2为两个相互独立的随机数，在0,1之间满足均匀分布；vij通常将搜索范围限制在一定的空间范围 之内，为了使微粒在搜索空间内飞行而不离开，将vij设定在一定区间内内变化。3 流程及其流程图根本微粒群算法的流程可描述为：Step 1：初始化一群微粒，包括随机位置和速度。初始化过程：设定群体规模为n；对任意i，j，在内服从均匀分布产生xij；对任意i，j，在内服从均匀分

13、布产生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 变化路径的PS

14、O求解1表达式如何将微粒群算法应用于车辆路径问题的关键是要构造一个正确而且适宜的微粒表达式，并且要使每个微粒与其每个解对应。如前所述，VRP问题要求每个发货点都必须得到车辆的配送效劳，而且每个发货点的效劳只能限制一辆车来完成。由参考文献【3】的思想并根据本文所用实例做出适当的调整，可以构造出这样的问题：首先，假设构造一个N维的空间微粒的位置向量z，使它对应于有N个发货任务点的VRP问题，其中z的数值代表车辆编号。例如，某VRP问题中有8个发货点任务，车辆数为3，某个微粒的位置向量z =，表示第1、6、7个任务点由第1辆车配送；第2、3、8个任务点由第2辆车配送；第4、5个任务点由第3辆车配送。

15、然后再采用整数编码，即对于N个发货点，k辆车的VRP问题，将1N的整数随机排列并赋给每个发货点，再在发货点序列中插入k-1个0，这样把发货点序列分成k段，每一段就代表一辆车的行车路径。由此产生一组新的种群，种群中每个微粒即对应一个N+k-1维向量，也就是问题一个解。例如，设某VRP问题有3辆车运输，6个发货点，假设某微粒的位置向量X为：5 3 0 6 1 4 0 2，那么表示该粒子对应的路径为：第1辆车：0530；第2辆车：06140；第3辆车：020。这样的表达方式有效地解决了车辆的编码, 而且将VRP转成一个TSP问题, 便于采用传统TSP问题处理方法来求解VRP问题。2求解步骤在第二局部

16、中可知，虽然微粒群算法在求解连续空间的问题上表现出很好的优越性，但是对于离散问题如VRP问题就不是很方便了。微粒群算法中，微粒下一个位置是通过速度的更新来进行的，但其难以表达。因而实现过程中，在根本微粒群算法的根底上要对其作相应的改良：微粒的下一个位置是通过与全局极值的交叉，最后再变异产生的，这样不仅能简单表示微粒的位置，而且经过变异后还能防止了算法陷入局部极值的可能。根据上面的表达式并且借鉴文献【4】的思想，具体算法步骤如下： 初始化参数：设微粒数为n，随机产生n个初始解初始路径C0，给每个变量w、c1、c2赋值，最大迭代次数为T，有N个发货点，每个发货点的需求量为g，车辆数目为k，车辆载重

17、为q。 根据当前位置计算每个微粒的适应值各路径的长度d，设置当前微粒的适应值为个体极值pbest，取其中最优值为全局极值gbest杂志网。While(迭代次数 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位进行交叉，那

18、么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)End While 最后输出全局极值gbest及取到全局极值时的最优路径。以上是将微粒群算法应用于车辆路径问题的算法步骤，假设要适用于变化路径运输问题，根据本人的理解，只需将受阻的某条或某几条路径两点间的距离相对于其他路径设为无穷大，然后按上面的步骤1步骤7开始计算适应值，由于两点间的距离无穷大其适应值肯定很大，那么每个粒子的最优路径肯定不会包含此两点所表示的受阻路径，从而能够得到全局极值，即最优路径值。3实例分析现根据参考文献【5】举一个有7个发货点任务的车辆路径问题，各任务节点坐标及货运量见下表3-1。其中序号0表示中心仓库，其