Effective evacuation route planning algorithms by updating earliest arrival time of multiple paths

Manki Min, Jonguk Lee, Sunho Lim

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

More and more natural disasters are happening around the globe and in such urgent situations, effective evacuation planning is one of the most critical tools for human safety. Evacuation planning algorithms are different from traditional network routing algorithms in the sense that the objective is to minimize the time when the last evacuee arrives at the destination. Among the existing evacuation planning algo- rithms, CCRP++ finds good solutions but its computation time is not scalable in terms of the number of the evacuees. In addition, in order to improve the computation time from the base algorithm CCRP, CCRP++ makes non-global up- date of earliest arrival time of each source node which results in unnecessarily large evacuation time. In this paper we investigated the two factors (evacua- tion time and computation time) of CCRP++ and proposed three algorithms, DMP, SMP, and EET, that significantly improve both factors. All four algorithms take the trans- portation network as the input and output the complete evacuation scenarios in which individualized evacuation plan for each evacuee is determined. Our first algorithm DMP significantly reduces the number of the shortest path find- ings during the evacuation iteration which is the main rea- son of large computation time of CCRP++. In addition, by updating the earliest arrival time of each found path ef- ficiently, the evacuation time of DMP output is on average reduced compared to that of CCRP++ output. Our sec- ond algorithm SMP further reduces the computation time by first finding the limited number of shortest paths before the evacuation iteration while maintaining the reduced evac- uation time. Our third algorithm EET focuses on reducing the evacuation time of SMP output even in the worst-case scenarios by efficiently and effectively estimating the evacu- ation time and by using it to determine the source node to be evacuated in each round. The computation results show that EET successfully reduces the evacuation time, espe- cially when DMP/SMP outputs were worse than CCRP++. Due to its algorithmic complication, EET has slightly in- creased computation time compared to SMP, but still re- mains comparable to DMP.

Original languageEnglish
Title of host publicationProceedings of the 3rd ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems, MobiGIS 2014 - In Conjunction with the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL 2014
EditorsShashi Shekhar, Chi-Yin Chow
PublisherAssociation for Computing Machinery, Inc
Pages8-17
Number of pages10
ISBN (Electronic)9781450331425
DOIs
StatePublished - Nov 4 2014
Event3rd ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems, MobiGIS 2014, Held in Conjunction with the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL 2014 - Dallas, United States
Duration: Nov 4 2014 → …

Publication series

NameProceedings of the 3rd ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems, MobiGIS 2014 - In Conjunction with the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL 2014

Conference

Conference3rd ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems, MobiGIS 2014, Held in Conjunction with the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL 2014
CountryUnited States
CityDallas
Period11/4/14 → …

Keywords

  • Evacuation routing
  • Scalable
  • Suboptimal

Fingerprint Dive into the research topics of 'Effective evacuation route planning algorithms by updating earliest arrival time of multiple paths'. Together they form a unique fingerprint.

Cite this