地球信息科学学报 ›› 2016, Vol. 18 ›› Issue (3): 362-368.doi: 10.3724/SP.J.1047.2016.00362

• 地球信息科学理论与方法 • 上一篇    下一篇

洪灾应急疏散路径规划算法优化

李梦雅1,2(), 王军1,2(), 沈航1,3   

  1. 1. 华东师范大学地理科学学院,上海 200241
    2. 华东师范大学 地理信息科学教育部重点实验室,上海 200241
    3. 武汉大学资源与环境科学学院,武汉 430079
  • 收稿日期:2015-04-30 修回日期:2015-06-12 出版日期:2016-03-10 发布日期:2016-03-10
  • 作者简介:

    作者简介:李梦雅(1991-),女,湖北人,硕士生,主要从事灾害应急疏散研究.E-mail:wooddream2009@163.com

  • 基金资助:
    国家自然科学基金项目(71373084);上海市教育委员会科研创新重点项目(13ZZ035)

Optimization of Evacuation Routes Planning Algorithms for Flood Events

LI Mengya1,2(), WANG Jun1,2,*(), SHEN Hang1,3   

  1. 1. School of Geographic Sciences, East China Normal University, Shanghai 200241, China
    2. Key Laboratory of Geographic Information Science of Ministry of Education, East China Normal University, Shanghai 200241, China
    3. School of Resource and Environmental Sciences, Wuhan University, Wuhan 430079, China
  • Received:2015-04-30 Revised:2015-06-12 Online:2016-03-10 Published:2016-03-10
  • Contact: WANG Jun E-mail:wooddream2009@163.com;jwang@geo.ecnu.edu.cn

摘要:

应急疏散是救灾工作的重要环节,合理的路径规划能有效缩短疏散时间,减少人员伤亡.本文以疏散总时间最短为目标,考虑需求控制,容量限制,交通延误,公平分配和资源节约等约束条件,对经典Dijkstra算法进行改进;并采用混合拆分疏散方法,构建洪灾避难应急疏散路径规划模型.运用C#语言编写算法,求解最佳路径,基于自主开发的应急疏散分析工具MiniGIS,对规划路径进行动态模拟,依据反馈逐次优化算法.结果表明:理想算法,延时-改进算法,逆行-改进算法均能为县域尺度的洪灾避难疏散路径选择提供参考,但理想算法适用于组织简单,高度有序的疏散情景,延时-改进算法考虑了除交通拥堵之外的延误,与真实情况更为接近,逆行-改进算法避免了因中途路径调整而出现的"回头路",在时间最短次优的条件下,更有利于疏散过程管理与资源节约,其结果被认为是此次应急疏散路径规划的最优解.

关键词: 应急疏散, 路径规划, 算法优化, 洪灾避难, MiniGIS

Abstract:

Well-planned evacuation routes definitely contribute to reducing traffic congestions and mitigating logistics costs during an emergency evacuation. With an objective to minimize the total evacuation time, an approach to seek optimum evacuation routes in a capacity constrained road network was presented in this paper, and then it is carried out based on a scenario with severe surge floods affecting an island county in Zhejiang province, China. The classical Dijkstra algorithm is improved by addressing the issues aroused with respect to evacuees' demands, traffic congestion, and the equal accessibility to and assignment of relief resources. Besides, regarding the fact that, since the evacuee units contain a large population, it is hard to find a closest shelter with enough capacity at one time, thus the mixed split delivery model is adopted. Namely, a unit might be divided into several groups and sent to different shelters separately. Using C#, an applet with built-in algorithms named MiniGIS is developed for the visualization of the dynamic evacuation flow. As presented in this paper, the ideal algorithm, though being capable of finding out the optimal evacuation routes, is based on a highly ordered scenario in which only simple traffic congestion is considered. Next, the additional delay caused by mode transferring and slow down at road cross-sections, turnings and crowded segments is taken into consideration. In addition, the delay-improved algorithm, which records the state of each group at road conjunctions, is able to calculate the total delay if given the time when evacuation state swifts from one to another. Undoubtedly, it provides more reliable results than the ideal algorithm does; however, due to route adjustments, several retrogressions are captured in the routes planned by delay-improved algorithm using the tracking animation in MiniGIS, implying that a certain vehicle is required to return to a former earlier location before heading toward the destination according to the new planned route. Considering routes with retrogressions are not common and easily being identified and adjusted, such routes are artificially fixed and then input to the retrogression-improved algorithm, which would calculate the new evacuation time and meanwhile avoid redundant retrograde motions. Basically, though the total travel time would slightly exceed that of delay-improved algorithm, results of retrogression-improved algorithm is still regarded as the optimum solution giving priority to efficient evacuation management and resource economization.

Key words: emergency evacuation, routes planning, algorithm optimization, flood events, MiniGIS