### 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 language | English |
---|---|

Title of host publication | 11th Annual IEEE International Systems Conference, SysCon 2017 - Proceedings |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

ISBN (Electronic) | 9781509046225 |

DOIs | |

State | Published - May 26 2017 |

Event | 11th Annual IEEE International Systems Conference, SysCon 2017 - Montreal, Canada Duration: Apr 24 2017 → Apr 27 2017 |

### Publication series

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

### Conference

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

Country | Canada |

City | Montreal |

Period | 04/24/17 → 04/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

*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