Efficient Evacuation Route Planning and Emergency Management (20120196, Dr. Shashi Shekhar)

Technology No. 20120196

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
  • $5,000 for a six month trial
  • Trial fee is waived for MN companies or if sponsoring $50,000+ research with the University
  • No US patent costs during trial
  • $25,000 conversion fee (TRY to BUY)
  • Royalty rate of 3% (2% for MN company)
  • Royalty free for first $1M in sales

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.


  • 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

Shashi Shekhar, PhD
Professor, Department of Computer Science, College of Science and Engineering
External Link (www.cs.umn.edu)

  • swap_vertical_circlelibrary_booksReferences (0)
  • swap_vertical_circlecloud_downloadSupporting documents (0)
Questions about this technology?