Efficient Dynamic Flow Algorithms for Evacuation Planning

Abstract

The large scale calamities caused by different natural or human-created disasters are challenging issues to protect life and their surroundings. A great loss of people and socio-economic damages of our society on such disasters is due to the lack of proper planning and their implementation rather than the disaster itself. These issues draw increasing attention of the researchers towards different aspects of disaster management. It is a complex task to develop a significant and universally accepted solution strategy to handle such issues. During such disasters, the primary concern is to protect the life, property, and their surroundings with a minimum loss as far as possible. There are different solution approaches to have a significant solution for an evacuation planning problem. Contraflow, the lane reversal strategy, is one of the widely accepted solution approaches for evacuation planning as it maximizes the outbound capacities of roads by reversing the required road directions and makes the traffic smooth. This significantly increases the flow value and decreases the evacuation time. The abstract flow model deals with the flow paths (routes) that satisfies the switching property. This concept can be embedded in the contraflow technique to have the mathematical formulation on abstract contraflow models with efficient algorithms for solving such abstract contraflow problems. In this work, different efficient solution procedures are presented for maximum dynamic, lexicographically maximum, and earliest arrival abstract contraflow problems. This approach maximizes the flow value in a given time and seeks to eliminate the crossing conflicts. The earliest arrival flow problem is one of the most important aspects of evacuation planning with a given capacity and travel time. The objective of the problem is to send the maximum number of evacuees from the given sources to the sinks as quickly as possible. It maximizes the flow value at each time instances simultaneously. Here, we study the earliest arrival flow problem with the contraflow approach having supplies and demands in abstract network. v During the evacuation planning problem, one of the essential components is the facility location as it correlates the pre- and post-disaster management. Appropriate facility locations and transportation facilities play a vital role in the solution of evacuation planning problems. Here, the network facility location and the contraflow approach are incorporated into the flow models and some efficient algorithms are presented to locate the facility with an objective of minimum flow loss on the evacuation network. Our facility location contraflow solutions obtain optimal plans concerning the given and as well as arbitrary locations. With limited resources, it is not an easy task to develop a universally accepted model to handle different aspects and challenges of the evacuation planning problem. However, the budget-constrained network flow improvement approach plays a significant role to evacuate the maximum number of people within the given time horizon for the budget provided. We consider an evacuation planning problem that aims to shift the maximum number of evacuees from a danger area to a safe zone in limited time under the budget constraints for network modification. In this work, different flow improvement strategies for fixed switching costs will be investigated namely integral, rational, and either to increase the full capacity of an arc or not at all. A solution technique on a static network is extended to the dynamic one. Moreover, we introduce the static and dynamic maximum flow problems with lane reversal strategy and also propose efficient algorithms for their solutions. Here, the contraflow approach reverses the direction of arcs concerning the lane reversal costs to increase the flow value. As an implementation of an evacuation plan may demand a large cost, the solutions proposed in this thesis with budget-constrained problems play an important role in practice. In this thesis, the contraflow models and their solutions strategies have been established and investigated in an abstract network topology. To allocate the facility during the evacuation process FlowLoc problems and their solution have been introduced in the evacuation network. The arc switching costs have been considered for the first time in the evacuation network. These optimization methods play significant roles in maximizing the flow and minimizing the evacuation time, and also have the great support for logistics and emergency vehicle movements in disasters.