Segmented arrival graph based evacuation plan assessment algorithm using linear programming

Manki Min, Sunho Lim

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The evacuation routing problem is NP-hard and hence no polynomial-time algorithm exists for the problem. There have been many studies on the evacuation planning heuristic algorithms but the in-depth comparison between them is not available especially in terms of the performance ratio. Without knowing the heuristic solution quality with respect to the optimal solution, we cannot accurately determine each heuristic algorithm's strengths and weaknesses that can lead to a better combination of heuristic algorithms. In this paper we present a Linear Programming (LP) based iterative algorithm to assess the evacuation planning algorithms in terms of the evacuation time. The proposed algorithm takes the paths that are found and/or used in a heuristic algorithm as the input and finds the minimum evacuation time using only those paths. To get the optimal solution, our algorithm repeatedly solves relaxed LP formulations formed from the concept of segmented arrival graphs. We segment the arrival graphs of paths based on the edge-sharing and construct the LP formulations along the segmented edges on the graphs. The computational experiment shows that the proposed algorithm computes the solution using time that is comparable to that of the heuristic algorithms as long as the number of paths is adequately maintained. Using the algorithm we perform the comparison between the existing heuristic algorithms, CCRP++, SMP, EET, and FBSP.

Original languageEnglish
Title of host publication11th Annual IEEE International Systems Conference, SysCon 2017 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509046225
DOIs
StatePublished - May 26 2017
Event11th Annual IEEE International Systems Conference, SysCon 2017 - Montreal, Canada
Duration: Apr 24 2017Apr 27 2017

Publication series

Name11th Annual IEEE International Systems Conference, SysCon 2017 - Proceedings

Conference

Conference11th Annual IEEE International Systems Conference, SysCon 2017
CountryCanada
CityMontreal
Period04/24/1704/27/17

Keywords

  • Evacuation Routing Assessment
  • Linear Programming Relaxation
  • Segmented Arrival Graphs

Fingerprint Dive into the research topics of 'Segmented arrival graph based evacuation plan assessment algorithm using linear programming'. Together they form a unique fingerprint.

  • Cite this

    Min, M., & Lim, S. (2017). Segmented arrival graph based evacuation plan assessment algorithm using linear programming. In 11th Annual IEEE International Systems Conference, SysCon 2017 - Proceedings [7934702] (11th Annual IEEE International Systems Conference, SysCon 2017 - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SYSCON.2017.7934702