{"id":{"repo_id":"sdstate","oai_identifier":"oai:openprairie.sdstate.edu:etd-3058"},"canonical_url":"https://search.ndltd.org/etd/sdstate/oai:openprairie.sdstate.edu:etd-3058","repository":{"repo_id":"sdstate","name":"South Dakota State University","base_url":"https://openprairie.sdstate.edu/do/oai/"},"display":{"title":"Accurate Evacuation Routing Algorithm","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Patel, Nisha"],"institution":null,"degree_name":"Master of Science (MS)","degree_level":"Thesis - University Access Only","degree_discipline":"Electrical Engineering and Computer Science","degree_department":null,"school":null,"contributors":["Manki Min"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":null,"date_issued":"","date_published":null,"updated_at":"2026-11-19T08:58:21Z","subjects":[],"languages":["en"],"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>"],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://openprairie.sdstate.edu/etd/2031","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://openprairie.sdstate.edu/etd/2031","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://openprairie.sdstate.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Aopenprairie.sdstate.edu%3Aetd-3058","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Manki Min"]},{"key":"dc:creator","label":"Author","values":["Patel, Nisha"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2017-11-27T08:00:00Z"]},{"key":"dc:date.created","label":"Dc Date Created","values":["2014-01-01T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering and Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis - University Access Only"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science (MS)"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["<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>"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://openprairie.sdstate.edu/etd/2031"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Accurate Evacuation Routing Algorithm"]}]}],"canonical_facts":{"dc:contributor":["Manki Min"],"dc:creator":["Patel, Nisha"],"dc:date.available":["2017-11-27T08:00:00Z"],"dc:date.created":["2014-01-01T08:00:00Z"],"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."],"dc:identifier":["https://openprairie.sdstate.edu/etd/2031"],"dc:language":["en"],"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>"],"dc:title":["Accurate Evacuation Routing Algorithm"],"thesis:degree_discipline":["Electrical Engineering and Computer Science"],"thesis:degree_level":["Thesis - University Access Only"],"thesis:degree_name":["Master of Science (MS)"]},"updated_at":"2026-11-19T08:58:21Z"}