TY - GEN

T1 - Segmented arrival graph based evacuation plan assessment algorithm using linear programming

AU - Min, Manki

AU - Lim, Sunho

N1 - Publisher Copyright:
© 2017 IEEE.

PY - 2017/5/26

Y1 - 2017/5/26

N2 - 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.

AB - 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.

KW - Evacuation Routing Assessment

KW - Linear Programming Relaxation

KW - Segmented Arrival Graphs

UR - http://www.scopus.com/inward/record.url?scp=85021440664&partnerID=8YFLogxK

U2 - 10.1109/SYSCON.2017.7934702

DO - 10.1109/SYSCON.2017.7934702

M3 - Conference contribution

AN - SCOPUS:85021440664

T3 - 11th Annual IEEE International Systems Conference, SysCon 2017 - Proceedings

BT - 11th Annual IEEE International Systems Conference, SysCon 2017 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 11th Annual IEEE International Systems Conference, SysCon 2017

Y2 - 24 April 2017 through 27 April 2017

ER -