Please use this identifier to cite or link to this item:
|Efficient Dynamic Flow Algorithms for Evacuation Planning
|Dhungana, Ram Chandra
|Department of Mathematics
|Central Department of Mathematics
|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 signiﬁcant 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 signiﬁcant solution for an evacuation planning problem. Contraﬂow, 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 trafﬁc smooth. This signiﬁcantly increases the ﬂow value and decreases the evacuation time. The abstract ﬂow model deals with the ﬂow paths (routes) that satisﬁes the switching property. This concept can be embedded in the contraﬂow technique to have the mathematical formulation on abstract contraﬂow models with efﬁcient algorithms for solving such abstract contraﬂow problems. In this work, different efﬁcient solution procedures are presented for maximum dynamic, lexicographically maximum, and earliest arrival abstract contraﬂow problems. This approach maximizes the ﬂow value in a given time and seeks to eliminate the crossing conﬂicts. The earliest arrival ﬂow 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 ﬂow value at each time instances simultaneously. Here, we study the earliest arrival ﬂow problem with the contraﬂow 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 contraﬂow approach are incorporated into the ﬂow models and some efﬁcient algorithms are presented to locate the facility with an objective of minimum ﬂow loss on the evacuation network. Our facility location contraﬂow 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 ﬂow improvement approach plays a signiﬁcant 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 modiﬁcation. In this work, different ﬂow improvement strategies for ﬁxed 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 ﬂow problems with lane reversal strategy and also propose efﬁcient algorithms for their solutions. Here, the contraﬂow approach reverses the direction of arcs concerning the lane reversal costs to increase the ﬂow 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 contraﬂow 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 ﬁrst time in the evacuation network. These optimization methods play signiﬁcant roles in maximizing the ﬂow and minimizing the evacuation time, and also have the great support for logistics and emergency vehicle movements in disasters.
|Appears in Collections:
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.