动态网络下多源多汇应急疏散问题算法

提出了一个时间依赖容量约束的动态网络下多源多汇的人群应急疏散问题,基于分组疏散的思想和TAG时间依赖网络的最短路算法,设计了一个启发式求解算法。算法将多源多汇问题转化为单源单汇问题,对各源点的待疏散人群采取分组疏散,并为每组人群找到一条满足时变容量约束的最早到达时间的路径及时刻表。最后进行了方法的应用分析。该算法能适用于大规模时变网络的人群应急疏散。

The Algorithm of Multi-Source and Multi-Sink Emergency Evacuation Problem on Dynamic Networks

This paper considers a multi-source and multi-sink emergency evacuation problem on time-dependent capacity constrained networks.Based on grouping evacuation idea and the shortest path algorithm on time aggregated graphs（TAG）,a heuristic algorithm is designed,which converts multi-source and multi-sink problem into single source and source sink problem,and takes grouping evacuation method.Each group is assigned the route with the earliest destination arrival time meeting time-dependent capacity constraint to evacuate.An example is demonstrated finally.The algorithm can be used to solve the emergency evacuation problem on large-scale time-variant networks.