Office for Technology Commercialization
http://www.research.umn.edu/techcomm
612-624-0550

Efficient Evacuation Route Planning and Emergency Management

Technology #20120196

Questions about this technology? Ask a Technology Manager

Download Printable PDF

Image Gallery
Transportation NetworkEvacuation Routes for Emergency SituationsRoute Planning for Emergency Management
Categories
Researchers
Shashi Shekhar, PhD
Professor, Department of Computer Science, College of Science and Engineering
External Link (www.cs.umn.edu)
Managed By
Andrew Morrow
Technology Licensing Officer
Patent Protection

US Patent Pending 20150051944

Route Planning and Emergency Management for Emergency Situations and Large Events

Evacuation route planning to effectively evacuate people in a man-made or natural disaster is of increasing importance with growing populations. The efficient emergency management software produces high quality solutions for emergency evacuation and large event transportation planning. This technology significantly reduces the computational cost compared to existing software because of a dartboard network structure using node-independent paths to speed up the capacity constrained routing problem . The evacuation route planning system is scalable to the number of people being moved and the size of the transportation network. The software can be used to compare transportation modes such as driving and walking for different zones, and it reduces risk by identifying critical locations with unusually high evacuation times through sector evaluations. The route planning algorithm identifies and highlights the most efficient set of routes to minimize the transit time for large events and emergency response situations.

MN-IP Try and Buy
This technology is available via a standard negotiated license agreement. Contact Andrew Morrow for specific details.

Route Planning is Efficient and Scalable for Large Transportation Networks

Conventional evacuation route planning simulation models that model traffic assignment are useful for evacuation scenarios with moderate size networks. However, traffic assignment models do not scale up for large size transportation networks in urban evacuation scenarios. This is due to the high computational costs caused by the tremendously increased size of the time-expanded network. In contrast, this emergency management algorithm generates evacuation route plans based on large-scale network dataset and guarantees fast responses for emergency situations. Using the more efficient dartboard network structure, the computation time is reduced by as much as 80% without sacrificing the quality of the solution. The algorithm accelerates routing by grouping multiple node-independent shortest routes to reduce the number of search iterations. The introduction of the dartboard network structure helps to explain how to organize and group evacuation routes, decreasing congestion in disaster situations.

Proven Evacuation Route Planning Software in Real Evacuation Scenarios

The algorithm used in the network has been evaluated using computer implementation and experiments. Experiments used a road map of Minneapolis, MN consisting of 8,868 nodes, 24,126 edges, and various population datasets. The test also used two different evacuation zones: one for a circular area and the other for a riverside area which is useful in different landscapes. Ten different test cases were evaluated based on different spatial location and network size.

BENEFITS OF EFFICIENT EVACUATION ROUTE PLANNING AND EMERGENCY MANAGEMENT:

  • Fast route evaluation algorithm
  • Enhances the scalability for large transportation networks
  • Reduces computational time by as much as 80%
  • Explains how to organize and group evacuation routes
  • Scalable to the number of people and the size of the network
  • Utilizes alternative transportation modes – walking, private vehicles, public transportation