TY - GEN
T1 - A multiple-source, nearest destination, shortest path problem in evacuation assignments
AU - Lu, Wei
AU - Han, Lee D.
AU - Liu, Cheng
AU - Long, Kejun
PY - 2014
Y1 - 2014
N2 - Simulation-based study is one of the major methods for evacuation planning. How to quickly build an origin-destination (OD) matrix from each source zone to their nearest destination becomes an issue. In this paper, we propose a new problem - Multiple-Source, Nearest Destination, Shortest Path (MSNDSP) - for generating an OD matrix in evacuation assignments. Compared to a benchmark study using Dijkstra's algorithm, we propose a new Super Node-based Trip Generator (SNTG) algorithm to improve the computing performance. The new algorithm significantly reduces the computational time through transforming the MSNDSP problem to a normal single-source, shortest path problem with a super-node concept. Experimental studies using real-world street networks and high-resolution LandScan USA population data indicate that the SNTG algorithm can provide OD output identical to the benchmark study, but the computing time is about 500 to 45,000 times faster in different network sizes. Discussion of this algorithm in other applications is also conducted.
AB - Simulation-based study is one of the major methods for evacuation planning. How to quickly build an origin-destination (OD) matrix from each source zone to their nearest destination becomes an issue. In this paper, we propose a new problem - Multiple-Source, Nearest Destination, Shortest Path (MSNDSP) - for generating an OD matrix in evacuation assignments. Compared to a benchmark study using Dijkstra's algorithm, we propose a new Super Node-based Trip Generator (SNTG) algorithm to improve the computing performance. The new algorithm significantly reduces the computational time through transforming the MSNDSP problem to a normal single-source, shortest path problem with a super-node concept. Experimental studies using real-world street networks and high-resolution LandScan USA population data indicate that the SNTG algorithm can provide OD output identical to the benchmark study, but the computing time is about 500 to 45,000 times faster in different network sizes. Discussion of this algorithm in other applications is also conducted.
KW - Emergency evacuation
KW - high performance computing
KW - shortest path
KW - traffic management
KW - traffic modeling and simulation
UR - http://www.scopus.com/inward/record.url?scp=84905974932&partnerID=8YFLogxK
U2 - 10.1061/9780784413623.353
DO - 10.1061/9780784413623.353
M3 - Conference contribution
AN - SCOPUS:84905974932
SN - 9780784413623
T3 - CICTP 2014: Safe, Smart, and Sustainable Multimodal Transportation Systems - Proceedings of the 14th COTA International Conference of Transportation Professionals
SP - 3691
EP - 3702
BT - CICTP 2014
PB - American Society of Civil Engineers (ASCE)
T2 - 14th COTA International Conference of Transportation Professionals: Safe, Smart, and Sustainable Multimodal Transportation Systems, CICTP 2014
Y2 - 4 July 2014 through 7 July 2014
ER -