Premium
A parallel time‐varying earliest arrival path algorithm for evacuation planning of underground mine water inrush accidents
Author(s) -
Du Yuanze,
Wu Qiang,
Zhao Yingwang,
Zhang Xiaoyan,
Yao Yi,
Xu Hua
Publication year - 2020
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.5644
Subject(s) - vertex (graph theory) , computer science , algorithm , time complexity , shortest path problem , path (computing) , parallel computing , theoretical computer science , graph , computer network
Summary Evacuation planning is of importance to reduce casualties in underground mine water inrush accidents. Since the transit time depends on the water height along the spreading of the water inrush, finding a path with the minimum egress time through the roadway network is considered as a time‐varying shortest path problem. Such problem can be solved by the time‐varying earliest arrival path algorithm. However, although the algorithm can solve the problem in polynomial time, more improvements are demanded to meet the real‐time requirements of practical applications. In this study, a parallel time‐varying earliest arrival path algorithm is proposed in this regard. The vertex‐hyperedge network is recommended to represent the adjacency of vertices. Three parallel strategies, including the time‐based decomposition, adjacent‐vertex‐based decomposition, and the adjacent‐vertex‐based decomposition using vertex‐hyperedge network, are proposed for parallelism implementation. The OpenMP interface is employed to evaluate the performance of the proposed strategies on a share‐memory multi‐core computer. The experiment results show that all three strategies can decrease the run time of the algorithm while maintaining the reasonable accuracy. The best strategy is adjacent‐vertex‐based decomposition using vertex‐hyperedge network, which results in the 2‐fold speedup when the number of threads meets the degree of concurrency of the topology structure.