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.
Thesis - University Access Only
Master of Science (MS)
Electrical Engineering and Computer Science
In emergency situations such as hurricane Sandy, an effective evacuation plan possibly with contraflows is required. In order to achieve an effective evacuation plan, evacuation time and computation time need to be short. In this thesis two aspects of evacuation algorithms are discussed: minimum time evacuation using contraflow and minimum time using evacuation routing planning. To make evacuation time shorter by using contraflow algorithm, Maximum Throughput Flow Contraflow Routing algorithm (MTFC) is presented. The MTFC shows similar evacuation time to the Greedy contraflow routing algorithm with shorter computation time. The Greedy algorithm is based on CCRP++ which is known as an effective local optimal evacuation planning algorithm. But CCRP++ has problems such as outdated earliest arrival time (EA), and long execution time. For a minimum time evacuation routing planning, approaches using dynamic and static multiple paths that will enhance CCRP++ are proposed in this thesis. The computational results of this algorithm show enhanced overall performance over the CCRP++ using MTFC as input data. The evacuation planner algorithm shows shorter evacuation time than CCRP++ in most cases and shorter execution time than CCRP++ in all cases.
Library of Congress Subject Headings
Includes bibliographical references (pages 79-82).
Number of Pages
South Dakota State University
In Copyright - Non-Commercial Use Permitted
Lee, Jonguk, "Time-efficient Evacuation Routing Algorithm Incorporating Contraflow" (2013). Electronic Theses and Dissertations. 1456.