Evacuation planning: A capacity constrained routing approach

Qingsong Lu, Yan Huang, Shashi Shekhar

Research output: Chapter in Book/Report/Conference proceedingChapter

70 Scopus citations

Abstract

Evacuation planning is critical for applications such as disaster management and homeland defense preparation. Efficient tools are needed to produce evacuation plans to evacuate populations to safety in the event of catastrophes, natural disasters, and terrorist attacks. Current optimal methods suffer from computational complexity and may not scale up to large transportation networks. Current naive heuristic methods do not consider the capacity constraints of the evacuation network and may not produce feasible evacuation plans. In this paper, we model capacity as a time series and use a capacity constrained heuristic routing approach to solve the evacuation planning problem. We propose two heuristic algorithms, namely Single-Route Capacity Constrained Planner and Multiple-Route Capacity Constrained Planner to incorporate capacity constraints of the routes. Experiments on a real building dataset show that our proposed algorithms can produce close-to-optimal solution, which has total evacuation time within 10 percent longer than optimal solution, and also reduce the computational cost to only half of the optimal algorithm. The experiments also show that our algorithms are scalable with respect to the number of evacuees.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsHsinchun Chen, Daniel D. Zeng, Therani Madhusudan, Richard Miranda, Jenny Schroeder, Chris Demchak
PublisherSpringer Verlag
Pages111-125
Number of pages15
ISBN (Print)354040189X, 9783540401896
DOIs
StatePublished - 2003

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2665
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint Dive into the research topics of 'Evacuation planning: A capacity constrained routing approach'. Together they form a unique fingerprint.

Cite this