| 
Shashi Shekhar
Computer Science and Engineering
Effective evacuation planning aims to move large numbers
of people quickly.
|
|
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.
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.
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.
Written by Peter Park Nelson
Reprinted with permission from the winter 2005 edition of Sensor,
a publication of the Center for Transportation Studies.
|
