Off-campus South Dakota State University users: To download campus access theses, please use the following link to log into our proxy server with your South Dakota State University ID and password.

Non-South Dakota State University users: Please talk to your librarian about requesting this thesis through interlibrary loan.

Document Type

Thesis - University Access Only

Award Date

2014

Degree Name

Master of Science (MS)

Department / School

Electrical Engineering and Computer Science

First Advisor

Manki Min

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.

Library of Congress Subject Headings

Evacuation of civilians -- Mathematical models Emergency management -- Planning
Algorithms

Description

Includes bibliographical references (pages 61-64)

Format

application/pdf

Number of Pages

75

Publisher

South Dakota State University

Rights

In Copyright - Non-Commercial Use Permitted
http://rightsstatements.org/vocab/InC-NC/1.0/

Download

Share

COinS