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

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

Optimization of Evacuation Routes Planning Algorithms for Flood Events

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.