Contraflow Transportation Network Reconfiguration for Evacuation Route Planning

Given a transportation network having source nodes with evacuees and destination nodes, we want to find a contraflow network configuration, i.e., ideal direction for each edge, to minimize evacuation time. Contraflow is considered a potential remedy to reduce congestion during evacuations in the con...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2008-08, Vol.20 (8), p.1115-1129
Main Authors: Sangho Kim, Shekhar, S., Min, M.
Format: Article
Language:English
Subjects:
Algorithms
Capacity planning
Computation
Computer networks
Congestion
Contraflow
Evacuation
Evacuation Route Planning
Evacuations & rescues
Graph theory
Heuristic
Homeland security
Hurricanes
Mathematical analysis
Mathematical models
Networks
Optimization
Roads
Space exploration
Studies
Telecommunication traffic
Terrorism
Traffic control
Transportation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a transportation network having source nodes with evacuees and destination nodes, we want to find a contraflow network configuration, i.e., ideal direction for each edge, to minimize evacuation time. Contraflow is considered a potential remedy to reduce congestion during evacuations in the context of homeland security and natural disasters (e.g., hurricanes). This problem is computationally challenging because of the very large search space and the expensive calculation of evacuation time on a given network. To our knowledge, this paper presents the first macroscopic approaches for the solution of contraflow network reconfiguration incorporating road capacity constraints, multiple sources, congestion factor, and scalability. We formally define the contraflow problem based on graph theory and provide a framework of computational workload to classify our approaches. A greedy heuristic is designed to produce high quality solutions with significant performance. A bottleneck relief heuristic is developed to deal with large numbers of evacuees. We evaluate the proposed approaches both analytically and experimentally using real world datasets. Experimental results show that our contraflow approaches can reduce evacuation time by 40% or more.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2007.190722