一种灾害救援最短路径动态算法  

A Dynamic Algorithm to Acquire the Shortest Path in Rescue System

作　　者：宋晓宇[1] 夏杰夫[1] 赵明[1] 

机构地区：[1]沈阳建筑大学信息与控制工程学院,辽宁沈阳110168

出　　处：《沈阳建筑大学学报（自然科学版）》2011年第5期990-994,共5页Journal of Shenyang Jianzhu University：Natural Science

基　　金：国家科技支撑计划项目(2006BAJ06B08-03);辽宁省高等学校优秀人才支持计划项目(2008RC42)

摘　　要：目的解决非确定动态路径下救援物资运输车辆的最短路径求解问题,及时在发生重大自然灾害的情况下提供救援物资,减少灾害造成的经济损失和社会影响.方法采用Dijkstra算法建立好出救点到目标点的初始最短路径,依据此路径前行,若发现前方无法通行,则基于初始最短路径信息,修改源点为当前点,调用Dijkstra算法改从目标点到源点逆向求出当前适用最短路径.结果通过仿真实验对所提算法进行验证和分析,实验结果表明该算法能够正确有效计算出新最短路径,并且通过对比发现该算法比蛮力算法减少重新计算的时间约50%左右.结论所提出的动态算法适合重大灾害救援中动态路况下车辆最短路径的求解,对灾害救援路径选择有一定的参考价值.The paper aims to resolve the shortest path of rescue vehicles with uncertain path information, and provide relief goods timely to reduce economic damage and bad social influence caused by magnitude natural disaster. Dijkstra algorithm is used to establish an initial shortest path which is used by emergency vehicle. If it is impossible to go along, based on initial shortest path information and according to the change of road conditions, a new shortest path can be obtained using Dijkstra algorithm adversely. Through verification and analysis of simulation experiment, results show that dynamic algorithm is able to get the new shortest path correctly and effectively. It reduces about 50% of the computing time compared with the brute-force algo- rithm. The new dynamic algorithm can be applied in computing the shortest path in rescue system, which provides reference values in emergence path choosing during disaster rescue.

关 键 词：重大灾害 动态最短路径 DIJKSTRA算法 逆向求解 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]