A dartboard network cut based approach to evacuation route planning: A summary of results

Kwang Soo Yang, Venkata M.V. Gunturi, Shashi Shekhar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationGeographic Information Science - 7th International Conference, GIScience 2012, Proceedings
Pages325-339
Number of pages15
DOIs
StatePublished - Oct 23 2012
Event7th International Conference on Geographic Information Science, GIScience 2012 - Columbus, OH, United States
Duration: Sep 18 2012Sep 21 2012

Publication series

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

Other

Other7th International Conference on Geographic Information Science, GIScience 2012
CountryUnited States
CityColumbus, OH
Period9/18/129/21/12

Keywords

  • dartboard network cut
  • evacuation route planning
  • routing and scheduling algorithm
  • spatial network

Fingerprint Dive into the research topics of 'A dartboard network cut based approach to evacuation route planning: A summary of results'. Together they form a unique fingerprint.

Cite this