Back to results

South Dakota State University

Accurate Evacuation Routing Algorithm

Abstract

dc:description.abstract

We live in the 21st century where technological advances have greatly improved human lives. However nature does present its challenges in the form of tsunamis, tornadoes, floods, wild fires, hurricanes, volcanoes etc. Efficient evacuation route planning is of paramount importance to reduce loss of lives during such disasters. The problem to find the shortest path between two nodes is studied extensively in graph theory. Many commercial applications like Google Maps and Map Quest provide us the shortest path to navigate from source to destination. Dijkstra’s algorithm is one of the bases for finding the shortest path. However the problem of evacuation route planning is much more complex than just finding the shortest path. Evacuation routing needs to consider the finite capacity of the paths used for evacuation. It also needs to consider the hundreds or thousands of evacuees that need to be evacuated. So there is a need to find more paths, including longer paths. In addition, not all multiple paths may be used at the same time because of the shared edges between the paths. Computation time (execution time hereafter) and evacuation time are two key properties which determine the effectiveness of evacuation algorithms. This thesis proposes a graph theory based evacuation routing algorithm called Forward Backward Shortest Path (FBSP). FBSP uses a novel idea to determine multiple routes by combining multiple paths at a time unlike other evacuation routing algorithms such as Shortest Multiple Path (SMP) that uses just the shortest paths between the source nodes and destination nodes. The additional routes help to reduce the shared edge problem faced by SMP. The proposed approach has improved evacuation time over SMP. The proposed algorithm was evaluated by experimental analysis on simulated graphs. Salient features of FBSP algorithm are larger number of evacuation paths and a lower evacuation time than other evacuation routing algorithm such as SMP.

Degree

thesis:*
Name thesis:degree_name
Master of Science (MS)
Level thesis:degree_level
Thesis - University Access Only
Discipline thesis:degree_discipline
Electrical Engineering and Computer Science

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Patel, Nisha
Contributors dc:contributor
  • Manki Min

Rights

dc:rights
Statement dc:rights
  • <p>In Copyright - Non-Commercial Use Permitted<br /><a href="http://rightsstatements.org/vocab/InC-NC/1.0/">http://rightsstatements.org/vocab/InC-NC/1.0/</a></p>
Language dc:language
en

Identifiers

dc:identifier.*
Repository record dc:identifier
https://openprairie.sdstate.edu/etd/2031

Chain of custody

source
Harvested from
South Dakota State University
Base URL
openprairie.sdstate.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Patel, Nisha. Accurate Evacuation Routing Algorithm. Thesis - University Access Only thesis, https://openprairie.sdstate.edu/etd/2031