ArcUser

• ArcUser Main
• Current Issue
• Previous Issues
• Subscribe
• Advertise
• Submit an Article

Summer 2012 Edition

Out of Harm's Way

Enabling intelligent location-based evacuation routing

By Kaveh Shahabi, University of Southern California

This article as a PDF.

Editor's note: The author has created a tool for ArcGIS for Desktop and the ArcGIS Network Analyst extension that performs evacuation planning more intelligently and efficiently. For his work developing this tool, Shahabi received the USC Esri Development Center Student of the Year award.

Traditionally, evacuation planners use either simulation software (like agent-based modeling) or basic shortest path routing methods to predict and visualize emergency situations. The results are relatively static, one-size-fits-all evacuation plans.

ArcCASPER (Capacity-Aware Shortest Path Evacuation Routing) is a custom Network Analyst tool that uses a state-of-the-art routing algorithm to produce evacuation routes to the nearest safe area for each evacuee or group of evacuees. The CASPER algorithm determines realistic traversal speeds for each road segment based on road capacity and number of evacuees. It intelligently and dynamically takes into account road capacity and travel time to create routes that minimize traffic congestion and evacuation times.

Developed as an evacuation routing extension to ArcGIS Network Analyst, ArcCASPER is available from the ArcGIS Resource Center. The Network Analyst extension handles management of the transportation network dataset and computation of road attributes. Visualization of input points and final routes is done through ArcMap. ArcCASPER provides its three routing methods (shortest path, capacity constrained route planner [CCRP], and CASPER) as additional options to the standard Network Analyst capabilities.

Traffic Models and Evacuation Planning

In the 1970s, researchers began to estimate evacuation time for people living close to nuclear power plants. [Following the Three Mile Island accident in Pennsylvania in 1979, the Nuclear Regulatory Commission requested that utilities operating nuclear generating plants provide estimates of the time required to evacuate the populations surrounding those plants.] One of the early works that separated evacuation modeling from traditional traffic modeling was the NETVACI model. Later, the MASSVAC program was developed to simulate urban evacuation during a disaster. Until the early 1990s, the goal was simply to predict traffic conditions during an evacuation given population density and network topology. Today's research objective is more ambitious: attempting to enhance evacuation planning with optimality, applicability, scalability, and enforceability.

City transportation networks are not designed to handle the sudden evacuation of tens of thousands of people from their residences or workplaces to designated safe areas. Evacuees take what they think will be the fastest path, which most often results in heavy traffic congestion and an unsuccessful evacuation. Evacuations related to disasters such as fires, environmental incidents, or man-made events are not as predictable as tsunami evacuations and pose additional problems for planners.

ArcCASPER can help evacuation planners avoid such scenarios. The algorithm at the core of this tool combines the road capacity (number of lanes or road class) with its speed limit to macroscopically predict traversal speed. The algorithm then generates routes specific to each evacuee location while minimizing global evacuation time.

Looking at Evacuation Routing Solutions

Evacuation routing solutions can be divided into two main categories: descriptive and prescriptive. Descriptive solutions show what would happen in a given condition using simulation techniques. In contrast, prescriptive solutions devise optimized routing strategies to achieve an evacuation goal without necessarily performing a microscopic simulation. ArcCASPER uses a prescriptive method.

Finding paths and flows are fundamental graph theory problems in computer science. To benefit from solutions to these rich problems in graph theory, GIS data must first be modeled into a graph. The usual practice is to assume a graph edge for every road segment and a graph node for every road intersection. The original shortest path algorithm is based on the assumption that a positive cost value can be put on every edge.

In GIS, this can be inferred from the road segment length and speed limit. Later development made this algorithm applicable to real-world GIS problems by implementing turn costs and turn restrictions. Today, most driving direction services have this algorithm at their core. The maximum flow problem, which seeks to maximize flow within a network, also assumes that a positive capacity value can be put on every edge. Today, this algorithm is used to find utility network bottlenecks.

Evacuation routing is also another graph theory problem, which seeks to maximize evacuation flow while minimizing the cost. To do this, it takes into account two positive values for every edge: an edge cost and an edge capacity.

From the user's point of view, the process of planning evacuation routes is composed of three steps:

1. Gathering inputs
2. Selecting a routing method
3. Mapping the final routes

1. Gathering Inputs

The basic input requirement is an ArcGIS transportation network. It is critical to build the network dataset from the most up-to-date street data and use accurate turn restriction tables. The evacuee locations can be collected in a number of ways. The most straight forward method is to use high-resolution population data such as census blocks. For evacuating smaller communities, such as university campuses, cell phone locations could be used instead.

2. Selecting a Routing Method

Of the implemented route optimization methods in ArcCASPER, shortest path, CCRP, and CASPER, the most basic and traditional method is shortest path. Since the shortest path algorithm ignores road capacities, the process is fast, but its accuracy is low.

CCRP generates routes while constraining them to road capacities. For example, if there is a narrow pathway that some evacuees need to use, CCRP gives more priority to evacuees who have a longer predicted evacuation time. Once the narrow pathway is fully saturated and becomes a complete bottleneck, the algorithm routes the rest of the evacuees on alternate routes.

The third method, CASPER, takes a fuzzy approach instead of using hard constraints. The algorithm first sorts evacuees by their distance from the closest safe area. Then, starting from the evacuee farthest away, it finds the shortest path and assigns the evacuee to that path. It iteratively continues this process until there are no more evacuees left. During the analysis, CASPER dynamically updates each edge travel cost based on the number of assigned evacuees and the edge capacity. This heuristically minimizes the global evacuation time without any hard constraints. This fuzziness is CASPER's main strength. Based on the evacuation routing method used, the ArcCASPER tool generates a route that will guide each evacuee to the best safe area.

3. Mapping the Final Routes

Each route has a shape, length, total evacuation time, and assigned population. Since ArcCASPER is integrated with ArcGIS, the entire process, from inputs to configurations to mapping final routes, is performed in ArcMap. ArcMap's visualization and quantitative symbology tools help identify groups of evacuees with slow evacuation times. Furthermore, each segment of the transportation network can be queried for predicted usage and possible traffic congestion. Taken together, the outputs generated enable the network to be better understood so the locations of safe areas can then be adjusted. Re-running the process will then achieve even faster evacuation results.

Modeling a Real-World Example

Shortly after the Tohoku earthquake and tsunami near the coast of Japan in March 2011, the Pacific Tsunami Warning Center in Hawaii issued a widespread tsunami warning covering the entire Pacific Ocean. Local tsunami warnings were also issued for the coastal areas of California, all of Oregon, and some parts of Alaska.

The tsunami crossed the Pacific Ocean and hit California shores in less than a day. The impact of the tsunami on the continental United States was relatively slight. Only 6,000 residents were evacuated. However, if the event had been a nearby offshore earthquake, substantial numbers of the population may have required evacuation.

About 200,000 people live within a few minutes' driving distance from the coastline of San Francisco, California. This densely populated 30-square-mile area has local roads and few major highways. Without prior preparation, evacuating this many people to inland areas would not be efficient. The three methods available in ArcCASPER were used to plan evacuation routes for this scenario. This test used census block group population data for evacuees and a large safe zone inland.

The shortest path technique resulted in an evacuation scenario of about 22 hours. Because road capacities were not considered, all evacuees were routed by the shortest routes. Although on a normal day, the evacuation routes used represent, at most, a 10-minute drive, routing all evacuees the same way resulted in heavy traffic congestion on the main roads and longer than usual evacuation times.

The CCRP method predicted a 13-hour evacuation scenario. It generated routes that took a little longer than on a typical day. However, about 80 percent of the population was rescued in about 2 hours—a considerable improvement over the shortest path scenario.

The CASPER route optimization method far surpassed the other two methods. CASPER achieved a 20-minute evacuation scenario using the same network, population density, and safe area parameters.

The CCRP and CASPER methods are similar. Both try to balance the population over as many road segments as possible to decrease evacuation time. CASPER achieves far better results using most of the same road segments because it can predict traffic congestion and road segment delays more accurately. Table 1 summarizes the number of evacuees per road segment. Note that the shortest path method uses far fewer road segments and has a larger number of people per segment compared with the other two methods.

Method		Shortest Path	CCRP	CASPER
Total Road Segment		1,614	5,933	4,493
Person per road segment	Min	320	1	52
	Max	64,033	38,475	25,177
	Mean	6,942	2,143	2,669
	Standard Deviation	8,444	3,923	2,384

Table 1: Number of evacuees per road segment for all three methods

Conclusion

Traffic modeling plays an important role in evacuation planning. ArcCASPER makes available the CASPER algorithm, which has a realistic traffic model that predicts traffic congestion more accurately. This intelligent traffic model is based on road attributes and population density and is applicable to any evacuation scenario for any geographic location. In addition to its traffic model, the CASPER algorithm heuristically solves any evacuation routing problem whether it involves students running during a campus evacuation or people driving cars during an urban evacuation.

Using ArcCASPER, emergency management officials and policy makers can better understand urban evacuation and confidently make life-saving decisions. For more information, contact Kaveh Shahabi at kshahabi@usc.edu.

Acknowledgments

The author thanks the Esri Applications Prototype Lab team for its priceless help and support during the development of this project as well as the Esri Network Analyst team for its continuous technical support and for providing sample code for the ArcObjects C++ API.

About the Author

Kaveh Shahabi joined the University of Southern California computer science master program in the spring of 2008 and immediately joined the USC GIS lab as a programmer. He is now a computer science PhD student at the USC Spatial Sciences Institute. He also interned at the Esri Applications Prototype Lab during summer 2011. For more information, visit www-scf.usc.edu/~kshahabi/.

Download the ArcCASPER tool esri.com/arccasper.