Efficient computation of evacuation routes on a three-dimensional geometric network

Huajun Tang, Amir Elalouf, Eugene Levner, T. C.E. Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 Citations (Scopus)


We consider a real-time emergency evacuation problem that seeks to compute a set of rapid evacuation routes in a building. Given a three-dimensional geometric structure of the evacuation network, an emergency evacuation route is a sequence of movements of people away from the threat or actual occurrence of a hazard (such as a fire, a hidden bomb) to a safe exit in the network. In such a network each room/crossing/exit in the building is designated as a node and the corridors/staircases/links between the rooms are edges. The evacuation times assigned to the edges are normally distributed random variables. This stochastic routing problem subject to deadline constraints is NP-hard. We provide a new pseudo-polynomial-time dynamic programming algorithm to solve this problem. Based on this algorithm, we construct two types of approximation algorithm, namely a fully polynomial-time approximation scheme providing "almost-optimal" solutions and a fully polynomial-time approximately feasible scheme yielding a best "almost feasible" solution. We present a case study and results of computational experiments to illustrate the working and efficacy of the proposed solution methods, respectively.
Original languageEnglish
Pages (from-to)231-242
Number of pages12
JournalComputers and Industrial Engineering
Publication statusPublished - 1 Jan 2014


  • Dynamic programming
  • Fully polynomial-time approximately feasible scheme
  • Fully polynomial-time approximation scheme
  • No-notice building evacuation
  • Real-time emergency routing

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this