Design and analysis of a fast approximation algorithm for multi-modal emergency evacuation routes in the 3D environment

Chi To Ng, T. C.E. Chen, A. Elalouf, E. Levner

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)

Abstract

We consider a multi-modal constrained routing problem arising in emergency evacuation situ-ations. Given a three-dimensional geometric structure of the evacuation network related to an area, such as a high-rise building or a city area with tense population, an emergency evacuation route is a sequence of move-ments of people away from the threat or actual occurrence of a hazard (e.g., a fire or a hidden bomb) to a safe exit of the area. The multi-modality condition corresponds to different possible ways and modes of evacuation (ambulances, trucks, helicopters, planes, etc.) and dictates specific demands to the solution algorithms. We provide a new pseudo-polynomial-time dynamic programming algorithm to solve this problem. Based on this algorithm, we construct a Fully Polynomial- Time Approximation Scheme (FPTAS), providing “almost-optimal” solutions in real time.
Original languageEnglish
Title of host publicationEnvironmental Science and Information Application Technology - Proceedings of the 2014 5th International Conference on Environmental Science and Information Application Technology, ESIAT 2014
PublisherCRC Press/Balkema
Pages307-312
Number of pages6
ISBN (Print)9781138028142
Publication statusPublished - 1 Jan 2015
Event5th International Conference on Environmental Science and Information Application Technology, ESIAT 2014 - Hong Kong, Hong Kong
Duration: 7 Nov 20148 Nov 2014

Conference

Conference5th International Conference on Environmental Science and Information Application Technology, ESIAT 2014
CountryHong Kong
CityHong Kong
Period7/11/148/11/14

ASJC Scopus subject areas

  • Information Systems and Management
  • Environmental Science(all)

Cite this