基于应急救援路径规划选择的研究

武警警官学院信息工程系决策与指挥教研室 哈 达 刘永利 沈先耿

基于应急救援路径规划选择的研究

武警警官学院信息工程系决策与指挥教研室 哈 达 刘永利 沈先耿

在突发事件发生之后,应急救援人员在规划部署开进事发地的路线中反映出了较大的问题。针对此类情况,本文旨在研究将Dijkstra算法与层次分析法相结合,提供给救援决策者一个有效可行的路径选择方案,极大地提高了救援决策者在路径选择上的效率,从而使救援决策者能够及时应对,妥善处置,使损失降到最低。

应急救援;路径规划;Dijkstra;层次分析

0 引言

当今我国在处置突发事件的过程中,应急救援队伍虽都能在第一时间调动起来,但由于各类原因造成救援队伍不能在第一时间到达受灾地点,导致损失没能及时控制。究其原因,不难发现,没能选择一条最优的路径是造成这个被动局面的一个主要原因。所以如何选择一条最优的路线是现在救援人员处置应急事件最需要解决的问题之一。开进路线规划问题的研究与实现的目的就是为了解决这个问题,为今后救援人员处置应急任务时,选择一条最优的路线提供思路及方法。

1 相关理论

Dijkstra算法是用来解决从一个起始点出发到其他各个点的最短路径问题,主要是针对有向图的。它解决问题的方式是从一个顶点即起始点出发,并且以这个点作为中心点,一层一层的选择计算,最后连接到终点。它是一种具有代表性的很典型的最短路径算法,发展较为成熟。如今,常常使用两种表达方法,分别是永久和临时标号方式以及OPEN,CLOSE表达方式。本文是使用第一种方式。另外Dijkstra算法还有不能有负权边在图中的要求。Dijkstra算法的本质是一种标号法:也就是给图的每一个顶点记一个数,这些数被称为这些顶点的标号,这些标号被分为临时标号和固定标号两种。

层次分析法(AHP)是萨蒂在上世纪70年代初在帮助美国国防部研究"根据各个工业部门对国家福利的贡献大小而进行电力分配"课题时研究出来的。这位美国运筹学家、匹茨堡大学的教授提出的这种方法是一种在面对多目标时,用权重来分层次、以权重来排序的一种决策分析方法[3]。这种决策分析方法是将定性与定量相结合,来应对多目标的复杂问题。它是利用决策者累积的经验也就是对事物特征的认知来确定能够让目标实现的要素之间的重要程度之比,是将感性认识进行定量化的过程。它给予所有决策方案的所有标准的权数,而后观察这些权数来确定方案间的好坏,在处理那些用定量方法很难解决的问题上有很大的作用。

2 路径选择建模

2.1 基于Dijlstra优化算法的选择

Dijkstra算法是找出从一个起始点到图中任意一点的最短路径,时间复杂度为O(n2)当其使用邻接矩阵存储网络拓扑结构时,需要存储空间为nXn。不难看出,当节点数n的增大,它所需要的存储空间就会成倍的巨涨。这就导致存储效率和计算效率的降低。考虑到这个情况,在查找研究了多种优化算法后,选择了最为适合本文的研究方法。那就是:传统的Dijkstra算法在选择节点时重复工作过多,这就导致算法的效率降低。而选择的优化方法就是让算法在处理节点时是只对最短路径上节点的相邻点进行处理,从而不考虑到其他节点。这样所需要的存储空间就会减少,从而达到提高效率的目的。这样在使用Dijkstra算法处理现实事件时,效率就会更高,就更有利于救援队伍处理应急事件。

2.2 层次分析法最优路选择

在处理应急事件问题时最主要考虑的问题就是找到一条最佳的路径到达目的地。然而在现实情况里,最短不一定最优。在处理应急问题时,不能仅仅只考虑时间。还需要考虑其他影响救援的因素,比如道路的疏通程度。因此本文在用Dijkstra算法找出最短路径后,再用层次分析法辅助决策,来确定最优路径。思路如下:

首先要进行的是对灾难等级的划分,不同的灾难程度对道路的破坏程度不同,在不同的灾难情况下,救灾物资的时效性、安全性、经济性的优先等级也不相同。这里是对每段运输路径的破坏程度进行评定。随着卫星地图的发展,这些工作时可以迅速评定出来。如果卫星遭到破坏,用航拍等技术也能大致确定各条道路的破坏情况。然后根据破坏程度规划出能够直接使用到的道路和经过维修能够使用的道路。这里道路的长度用时间来计算。在路况没有受到破坏的情况下,设计时速为60km/h,对于破坏的道路等级进行划分为不同的时速,然后加上需要维修的时间就是这路径的长度权重。然后用Dijkstra算法找出最短路径以及次短路径。

然后使用层次分析法来对比最短路径与次短路径。根据路径的时效性、经济性、安全性进行评定,作为层次分析法的一个比较矩阵。最优路径和次短路径就是可供选择的两个方案,然后这两个方案的时效性就是其上一步最短路径算出来的时间权重,安全性指标就是对道路的破坏程度、经济性就是需要维护道路的难度。最后对其进行层次分析法就能够得到最优结果。

3 结束语

本文以实用的角度,从根本问题的需求出发。在研究救援队伍现在抢险救灾物资配送中遇到的实际问题,一个能够快速选取最优路径的方法即Dijkstra算法。为了更好的在处置突发事件时提供帮助,本文对算法的优化方式进行了选择并找到了最好的优化方案,提高了其运算速度。然后将Dijkstra算法和层次分析法结合起来处理现实问题。该方法是针对不同的灾情的实际需求和灾情对路面的破坏程度做出的方法。根据需要配送到的地方的时效性、经济性、安全性进行评定。作为层次分析法的一个成对比较矩阵。最优路径和次短路径就是可供选择的两个方案,然后这两个方案的时效性就是其上一步最短路径法算出来的时间权重,安全性指标就是对道路的破坏程度、经济性就是需要维护道路的难度。然后对进行层次分析法就能够得到最优结果。

今后对有关选择最优路径还可以从以下几个方面进一步研究:(1)将数学模型与实际出现的情况相结合,如汶川、玉树地震。研究在实际情况下是否有更加优化的路径选择方法解决问题。 (2)将理论实体化,设计软件用于实现。

哈达,武警警官学院信息工程系决策与指挥教研室助教。