Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/35806
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.
URI: http://hdl.handle.net/10397/35806
ISSN: 0360-8352
DOI: 10.1016/j.cie.2014.08.003
Appears in Collections:Journal/Magazine Article

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

Page view(s)

15
Last Week
0
Last month
Checked on Jan 22, 2017

Google ScholarTM

Check

Altmetric



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