Evacuation Route Planning: Novel Spatio-temporal Network Models and Algorithms


Shashi Shekhar : Biography , Homepage


Computer Science Department, University of Minnesota.




Efficient tools are needed to identify routes and schedules to evacuate affected populations to safety in the event of natural disasters or terrorist attacks. This problem is challenging due to violation of key assumtions (e.g. stationary ranking of alternative routes, Wardrop equilibrium) behind popular shortest path algorithms (e.g. Dijktra's, A*) and microscopic traffic simulators (e.g. DYNASMART). Time-expanded graphs (TEG) and mathematical programming based paradigm neither scale up to large urban scenarios. We present a new approach, namely Capacity Constrained Route Planner (CCRP), with ideas such as time-aggregated graph (TAG) and an ATST function to provide earliest-Arrival-Time given any Start-Time. Experiments with DHS scenarios (e.g. Nuclear power plant, terrorism) with Twincities GIS datasets (e.g. population, transportation) show that the proposed approach is much faster than the state of the art. A key Transportation Science insight suggests that walking the first mile, when appropriate, may speed-up evacuation by a factor of 2 to 3 for many scenarios. Geographic Information science (e.g. Time Geography) contributions include novel spatio-temporal networks representation (e.g. TAG). Computer Science contributions for shortest path problems include charaterization of graph theory limitations (e.g. non-stationary ranking of routes, non-FIFO behaviour) and novel ideas to overcome those in designing scalable algorithms.

DETAILS: TAG models node/edge attributes as functions of time rather than fixed numbers. Thus node/edge capacities, node occupancies, etc. are modeled as time-series. Second, it iteratively considers all pairs of sources and destinations. In each iteration, it schedules evacuation of a group of evacuees across the closest source-destination pair. Special graphs construction is used eliminate redundant computation in this step. Non-stationary ranking of alternative routes during a evacuation is addressed by a linear-cost earliest-arrival-index on input TAG with travel-time-series. Experiments with real and synthetic transportation networks show that the proposed approach scales up to much larger networks, where software based on linear programming method crashes. In addition, linear programming approach needs an estimate of upper bound on total evacuation time to construct TEG represntation by replicating transportation network for every time-instant during evacuation. Incorrect estimate of upper bound on total evacuation time may lead to either a failure to produce any solution or excessive computational costs. For smaller networks, where software based on linear programming can be used, CCRP produces high quality solutions with evacuation times comparable to those achieved by linear programming methods.

Evaluation of our methods for evacuation planning for a disaster at the Monticello nuclear power plant near Minneapolis/St. Paul Twin Cities metropolitan area shows that the new methods lowered evacuation time relative to existing plans by identifying and removing bottlenecks, by providing higher capacities near the destination and by choosing shorter routes. In 2005, CCRP was used for evacuation planning (transportation component) for the Minneapolis-St. Paul twin-cities metropolitan area. It facilitated explorations of scenarios (e.g. alternative locations and times) as well as options (e.g. alternative transportation modes of pedestrian and vehicle). It also led to an interesting discovery that walking able-bodied evacuees (instead of letting them drive) reduces evacuation time significantly for small area (e.g. 1-mile radius) evacuations.

In future work, we plan to formally characterize the quality of solutions identified by the CCRP approach. We will explore new ideas, e.g. phased evacuations and contra-flow, to further reduce evacuation times. In addition, we would like to improve modeling of other transportation modes such as public transportation.

Back to spatial@ucsb