Abstract
dc:description.abstractWe 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