一种多出口室内应急疏散路径规划算法

An algorithm for route planning applied in multi-exit indoor emergency evacuation

针对多源多汇多路径问题若分别以多个出口为源点,通过多次直接调用Dijkstra算法求解,节点会被多次重复扩展,导致算法搜索效率过低的问题,该文结合Dijkstra算法的执行原理和特点,提出了一种解决多出口室内应急疏散路径规划的新算法。首先通过引入一个连接所有出口节点的虚拟节点作为源点来改变原始网络结构,将多源多汇多路径规划问题转化为单源多汇多路径规划问题;然后以虚拟节点为源点,直接调用Dijkstra算法来搜索源点到各个汇点的最优路径。该算法有效避免了多次调用Dijkstra算法带来的重复搜索节点问题,提高路径搜索效率。实验结果表明,该算法运行时间随着路网总节点数的增加而增加,与出口数关系不大;当出口数越多时,该算法较之现有算法效率提升越明显,具有较高的实用性。

Aiming at the problem that if all of exits are used as the source nodes,and Dijkstra’s algorithm is called directly many times to solve the multi-source and multi-sink problem,as a result,the query efficiency of this method will be very low because many nodes of the graph are expanded repeatedly,a new algorithm was proposed to solve the problem according to the implementation principle and characteristics of Dijkstra’s algorithm.Firstly,by introducing a virtual node linking all exit nodes to change the structure of the original search network,the multi-source and multi-sink problem was converted into a single-source and multi-sink problem.And then using the virtual node as the source node,Dijkstra’s algorithm was called once directly to search the optimal paths from the source node to all sink nodes.The algorithm effectively avoided the repeated search node problem caused by multiple calls of Dijkstra’s algorithm and improved the path search efficiency.The experimental results showed that the operation time of the proposed algorithm increased with the increase of the number of network nodes,and had little relation with the number of exits.When the number of exits is more,the algorithm is more efficient than the existing algorithm,and has higher practicability.