University of Minnesota Driven to Discover
U of MNUniversity of Minnesota
Center for Transportation Studies

Related Research

Research by Shashi Shekhar


Evacuation Planning: A Capacity Constrained Routing Approach

Presentation by Quingsong Lu, Deptartment of Computer Science and Engineering

September 14, 2004

Getting out of town for the weekend can be a real hassle after noon on any given Friday during the summer. Try it during rush hour, and you might as well add an extra hour or two to your travel time. But can you imagine if all 4.5 million inhabitants of a major metropolitan area like the Twin Cities tried to leave at the same time because of a natural disaster or a terrorist attack? Is such an evacuation even possible?

Computer science and engineering professor Shashi Shekhar and graduate student Qingsong Lu approached the problem using novel geo-spatial algorithms to produce evacuation plans that identify routes and schedules to evacuate affected populations to safety. Lu presented the research September 14 at an ITS Institute seminar titled "Evacuation Planning: A Capacity Constrained Routing Approach."

During the presentation, Lu provided an overview of evacuation planning, which identifies paths and schedules to move at-risk population out of the city to safe areas in the event of terrorist attacks, catastrophes, or natural disasters. The goal of the research is to identify near-optimal evacuation routes and schedules to minimize evacuation time despite limited transportation network capacity and the possibly large at-risk population.

A traditional linear programming approach uses a time-expanded network and aims at finding the optimal solution, which is computationally exorbitant and requires huge amounts of computer memory due to the extremely large size of the expanded transportation network, according to Lu. But the researchers developed a new heuristic approach to determine competent evacuation plans and significantly reduce the computational cost. They call their algorithm the "capacity-constrained routing planner" or CCRP.

The team’s proposed CCRP approach has two key ideas. First, it models node and edge attributes as time series rather than fixed numbers. Second, CCRP iteratively considers all pairs of sources and destinations. In each iteration, CCRP schedules evacuation of a group across the closest source-destination pair. As a result, the node and edge capacities are updated to reflect the decreased remaining capacity due to the already-routed vehicles.

Using a fictional disaster at the Monticello nuclear power plant just northwest of the Twin Cities metropolitan area, the research team was able to show that their new methods lowered evacuation time for a 10-mile radius relative to existing plans by providing higher capacities near the destination and by choosing shorter routes.

In conclusion, the researchers found that CCRP, using original network and time series to model network capacity, produced high-quality solutions at a reduced computational cost compared to optimal solution algorithms. In addition, CCRP can quickly find a feasible solution for a large transportation network with resource constraints (e.g. computer memory, computation time) and can provide upper bound on optimal evacuation time for linear programming approach.

Shekhar, a CTS Faculty Scholar, has worked with CTS and the ITS Institute for many years. Shekhar and Lu’s evacuation planning research using of high-performance computing techniques to reduce computation time is sponsored by the U.S. Army Research Lab (AHPCRC/ARL). The Federal Highway Administration is sponsoring follow-up work to determine contra-flow configurations of the transportation networks to increase outbound capacities and reduce total evacuation time. The National Science Foundation sponsored earlier foundational work on efficient storage and management of transportation network map databases. Other project collaborators include Sangho Kim and the Minnesota Department of Transportation’s Eil Kwon, Sonia Pitt, and Mike Sobolesky.