Winter 2005

Shashi Shekhar

Televised images of traffic jams stretching for miles as Hurricanes Rita and Katrina approached the Gulf Coast earlier this year brought home once again the difficulty of evacuating large urban areas. Mass evacuations are among the most difficult challenges faced by transportation professionals, but planning for a complete evacuation of a specific city is difficult because such evacuations are only rarely necessary. As a result, developing evacuation plans has been carried out largely on the basis of engineers’ judgment and “educated guesses” about how to best make use of the road system.

Professor Shashi Shekhar of the computer science and engineering department points out that no area can afford to ignore the possibility that mass evacuation may be necessary. While Minnesota may be safe from even the largest hurricane, other disasters—some man-made—could threaten our area. For example, the Monticello nuclear power plant is situated a mere 40 miles from the Twin Cities, and while it enjoys an excellent safety record, a terrorist attack aimed at disrupting the reactor could have catastrophic consequences. Shekhar’s research team used a scenario based on just such an event in its research.

In order to develop a better evacuation plan, Shekhar turned to the tools of computer modeling and traffic simulation, which are widely used by researchers and traffic managers to understand and predict the operation of traffic systems under normal conditions. But because evacuations are so radically different from normal traffic flow conditions, modeling them required the researchers to develop new techniques.

In the type of model used in this research, the network of roads and highways is modeled as a “graph” of line segments, or “edges” (roads) connecting “nodes” (intersections). Such a model captures the physical form of the transportation network, but does not take into account the operational differences between, for example, city streets and multi-lane highways—the “logical” transportation network. To model the logical transportation network, with its different traffic capacities, directions of travel, and turning restrictions at intersections, it is necessary to assign different capacities to each edge and node in the network model. Varying distances between nodes, and different speeds possible on different types of roads, are modeled by assigning a travel time to each edge in the network. In addition, each node (an intersection and the area around it) is assumed to have a certain initial number of occupants.

Given such a model, the challenge for evacuation planning is to find ways to direct vehicle traffic to move the greatest number of people from areas designated as unsafe to areas designated as safe. These methods may include modifying the logical transportation network by changing the direction of travel on certain roads, or changing the traffic control at selected intersections using the traffic signal control system or by placing traffic control officers in the field to direct drivers as needed.

Effective evacuation planning aims to move large numbers of people quickly.

Previously, computational techniques for solving evacuation problems often relied on the mathematical programming (MP) approach, which is widely used in optimization problems involving flow within transportation networks. Mathematical programming techniques are proven to produce optimal solutions to network flow problems and are known to work well for computing evacuation plans for smaller networks such as a single building. However, according to Shekhar, the high computational cost associated with current MP methods makes it difficult to scale MP methods up to problems involving extensive urban transportation networks with large numbers of evacuees. In addition, traditional MP approaches require the user to set an upper limit on evacuation time in order to derive a solution; this is rarely feasible in practice, as the goal is to evacuate the area in the smallest possible amount of time.

Editor’s note: Henry Liu’s research (see article in this issue) on evacuation traffic management explores a different approach, based on non-linear programming.

Heuristic algorithms are an alternative to mathematical programming for solving problems such as finding the shortest path between two points in a network. Unlike MP approaches, heuristic algorithms are not guaranteed to find the best possible solution to a network flow problem. Their advantage over the MP approach lies in the fact that they require much smaller computational resources to find an acceptable solution to a large network flow problem, making them more practical for metropolitan-scale evacuation planning. But existing heuristic algorithms, Shekhar found, suffered from their own limitations in regard to evacuation planning: existing heuristic algorithms did not take into account capacity constraints on the different types of links and nodes within a transportation network, and therefore were of limited use in determining how to move large numbers of evacuees.

Shekhar's research team focused its efforts on the development of a novel and more practical form of heuristic algorithm for evacuation planning—one that would take into account the capacity constraints built into transportation networks, but would determine a good solution to any large-scale evacuation problem in much less time than a mathematical programming approach would require. After developing two preliminary algorithms, this effort culminated in the Capacity Constrained Route Planner (CCRP) algorithm.

The CCRP algorithm takes capacity into account by modeling the capacity of each node and edge as a time series, reflecting the fact that the available capacity may vary as vehicles move through the system from one area to another. The algorithm evaluates all possible pairs of sources and destinations iteratively, scheduling the evacuation of a group of vehicles to the closest source-destination pair and then updating the node and edge capacities throughout the network to reflect the capacity taken up by the best available path between the selected pair.

The researchers used a hypothetical disaster at the Monticello nuclear power plant as the basis for their evacuation scenario. Using Geographic Information Systems (GIS) enabled the researchers to accurately model the entire transportation network around the affected area by incorporating population data for each part of the network. The existing evacuation plan for the surrounding area (drawn up by human planners) could then be compared with the results of the CCRP algorithm using traffic simulation tools.

The researchers observed several key differences between the existing evacuation plan and the plan developed by the CCRP algorithm. The existing plan made heavy use of two major highways leading out of the evacuation area, while the CCRP algorithm suggested using a larger number of roads, including several smaller roads, to reduce traffic congestion. Also, the results of the comparison suggested that the existing plan’s reliance on a small number of key routes would likely lead to congestion near the destination area due to exceeding the capacity constraints of the network. The CCRP algorithm avoided this problem by using a richer set of routes near the destination area. In the final analysis, the CCRP algorithm was able to significantly reduce total evacuation time relative to the existing plan for the 10-mile radius around the power plant.

The significant security implications of this work led to Shekhar
being invited to present the results at a Congressional Breakfast
on GIS and Homeland Security in 2004; his group has also published
seveal technical papers on their work.

Shekhar says his group is now working toward developing “a science of evacuation planning” by examining assumptions underlying current approaches and studying novel ideas to overcome them. For example, current evacuation plans primarily include evacuation routes. In contrast, CCRP can produce evacuation schedules in addition to evacuation routes to facilitate staged evacuation to reduce congestion. The researchers are also studying computer algorithms to identify contra-flow configuration of road networks to further reduce evacuation time.

In addition, Shekhar’s group is participating in transferring research results to practice. For example, the CCRP algorithm was recently used in a Minnesota Department of Transportation evacuation planning project encompassing the Minneapolis-St. Paul metropolitan area. Shekhar and graduate students Quingsong Lu and Sangho Kim helped transportation professionals and first responders use the CCRP algorithm to develop evacuation plans for many scenarios as mandated by the Department of Homeland Security.