| Contraflow is one of the most critical solutions in evacuation route planning to resolve the congestion problem by reversing the direction of road segments. Solving the contraflow network reconfiguration problem requires an efficient evacuation route planner due to the exorbitant computational overheads. Contraflow and evacuation route planning are accompanied with a variety of techniques including combinatorial optimization, graph algorithm, data structure manipulation, and software development. This thesis deals with the contraflow network reconfiguration problems in conjunction with an evacuation route planner.;Given a transportation network having source nodes with evacuees and destination nodes, we want to find a contraflow network configuration, i.e., ideal direction for each edge, to minimize evacuation time. Contraflow is considered a potential remedy to reduce congestion during evacuations in the context of homeland security and natural disasters (e.g., hurricanes). This problem is computationally challenging because of the very large search space and the expensive calculation of evacuation time on a given network. Thus, heuristic approach supported by an efficient evacuation route planner is of critical importance to address the problems of scalability and high quality solution.;The first part of this thesis defines the problem of contraflow network reconfiguration in the context of evacuation route planning and presents the hardness of the problem. Several approaches are proposed to address the computationally expensive problem along with design decisions. The approaches are analytically and experimentally evaluated.;The second part of this thesis discusses the development of evacuation route planning system and its practical uses. Efficient software tools for general evacuation route planning as well as contraflow problem are introduced. Several interesting findings are presented in collaboration with domain experts using the tools.;Lastly, evacuation route planning algorithm is tuned by an improved data structure as well as heuristic. These ideas will help us reduce the calculation time of evacuation routes and contraflow configurations. |
