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

论文导读:：“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辆车，每辆车的运输能力为q_k (k = 1，2，……，K)，车辆从配送中心D出发，完成运输任务后回到配送中心，每个发货点唯一接受一辆车的服务一次，共有N个发货点的任务需要完成，第i个送货点（i = 1，2，……，N）的货物需求量是g_i（i = 1，2，……，N），c_ij表示从第i个发货点到第j个发货点（i ≠ j，i，j = 1，2，……，N）的运输成本，问题的目标函数通常有车辆数和运输成本，首先要最小化车辆数，然后最小化总运输成本，并满足以下条件：

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

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

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

（3） 数学模型

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

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

x_ijk=

0，否则

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

y_ki=

0，否则

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

Min Z = ∑ ∑ ∑c_ijx_ijk 目标函数

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

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

∑x_ijk = y_ki

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

∑x_ijk = y_kj

x_ijk ∈{0,1}

y_ki ∈{0,1}

i，j = 0，1，…，N

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

2 微粒群算法

（1） 基本思想

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

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

（2） 数学表示

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

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

设：

第i个微粒的当前位置记为：X_i =（x_i1,x_i2,…,x_in）；

第i个微粒的当前飞行速度记为：V_i =（v_i1,v_i2,…,v_in）；

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

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

 1/2    1 2 下一页 尾页