Please use this identifier to cite or link to this item:
Title: Efficient computation of evacuation routes on a three-dimensional geometric network
Authors: Tang, HJ
Elalouf, A
Levner, E
Cheng, TCE 
Keywords: Real-time emergency routing
No-notice building evacuation
Dynamic programming
Fully polynomial-time approximation scheme
Fully polynomial-time approximately feasible scheme
Issue Date: 2014
Publisher: Pergamon Press
Source: Computers and industrial engineering, 2014, v. 76, p. 231-242 How to cite?
Journal: Computers and industrial engineering 
Abstract: 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.
ISSN: 0360-8352
EISSN: 1879-0550
DOI: 10.1016/j.cie.2014.08.003
Appears in Collections:Journal/Magazine Article

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Aug 21, 2017

Page view(s)

Last Week
Last month
Checked on Aug 21, 2017

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.