2012 | OriginalPaper | Buchkapitel
A Dartboard Network Cut Based Approach to Evacuation Route Planning: A Summary of Results
verfasst von : KwangSoo Yang, Venkata M. V. Gunturi, Shashi Shekhar
Erschienen in: Geographic Information Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Given a transportation network, a population, and a set of destinations, the goal of evacuation route planning is to produce routes that minimize the evacuation time for the population. Evacuation planning is essential for ensuring public safety in the wake of man-made or natural disasters (e.g., terrorist acts, hurricanes, and nuclear accidents). The problem is challenging because of the large size of network data, the large number of evacuees, and the need to account for capacity constraints in the road network. Promising methods that incorporate capacity constraints into route planning have been developed but new insights are needed to reduce the high computational costs incurred by these methods with large-scale networks. In this paper, we propose a novel scalable approach that explicitly exploits the spatial structure of road networks to minimize the computational time. Our new approach accelerates the routing algorithm by partitioning the network using dartboard network-cuts and groups node-independent shortest routes to reduce the number of search iterations. Experimental results using a Minneapolis, MN road network demonstrate that the proposed approach outperforms prior work for CCRP computation by orders of magnitude.