Efficient Dynamic Flow Algorithms for Evacuation Planning
Date
2020
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Department of Mathematics
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.
Description
Keywords
Evacuation planning, Algorithm