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


Degree Name

Master of Science (MS)

Department / School

Electrical Engineering and Computer Science

First Advisor

Manki Min


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.


Includes bibliographical references (pages 79-82).



Number of Pages



South Dakota State University


In Copyright - Non-Commercial Use Permitted