A Multiple-Source, Nearest Destination, Shortest Path Problem in Evacuation Assignments

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, the authors 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, the authors 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.

• Record URL:
  https://doi.org/10.1061/9780784413623.353
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/isbn/9780784413623
• Supplemental Notes:
  • © 2014 American Society of Civil Engineers.
• Corporate Authors:

  American Society of Civil Engineers

  1801 Alexander Bell Drive
  Reston, VA  United States  20191-4400
• Authors:
  • Lu, Wei
  • Han, Lee D
  • Liu, Cheng
  • Long, Kejun
• Conference:
  • 14th COTA International Conference of Transportation Professionals
  • Location: Changsha , China
  • Date: 2014-7-4 to 2014-7-7
• Publication Date: 2014-6

Language

• English

Media Info

• Media Type: Web
• Features: References;
• Pagination: pp 3691-3702
• Monograph Title: CICTP 2014: Safe, Smart, and Sustainable Multimodal Transportation Systems

Subject/Index Terms

• TRT Terms: Algorithms; Evacuation; Networks; Origin and destination; Shortest path algorithms; Simulation
• Subject Areas: Highways; Planning and Forecasting; Security and Emergencies; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01531418
• Record Type: Publication
• ISBN: 9780784413623
• Files: TRIS, ASCE
• Created Date: Jul 24 2014 3:22PM