Optimization Models and Algorithms for Evacuation Planning
Date
2020
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Faculty of Mathematics
Abstract
An important strategy, to save a life from natural or human-created disasters, is to
evacuate the population from the disastrous zones to safe places. Intelligent evacuation
planning requires a carefully designed traffic plan with optimal use of the facilities
available.
Reversing the direction of the traffic flow in the appropriate road segments, known as a
contraflow approach, has been an important strategy in evacuation planning. To avoid
unnecessary arc reversals, we introduce partial contraflow approach and design strongly
polynomial algorithms to solve maximum static, maximum dynamic, and quickest flow
problems with partial arc reversals, and polynomial-time algorithms to solve maximum
static/dynamic abstract partial contraflow problems. Sometimes the travel time on an
arc may change when it is reversed. We propose a network transformation that helps
convert the existing contraflow algorithms to the ones with orientation-dependent transit
times.
To address the dependency of transit times in the flow, we extend the contraflow
approach to inflow-dependent transit times and load-dependent transit times. Realizing
the NP-hardness of such problems, we propose strongly polynomial
(2 + )-approximation algorithms to solve the corresponding contraflow/partial
contraflow problems.
If facilities are to be adjusted on arcs to facilitate evacuation, there may be an increase
in the evacuation time. We introduce the quickest FlowLoc model to address such a
problem. We prove that the single facility case of the problem can be solved in strongly
polynomial time. Proving NP-hardness of the multi-facility case, we propose two
heuristics. Taking the case of a Kathmandu road network, the faster heuristic has an
average optimality gap of 3.48% and an average running time of 0.17 seconds. The
corresponding values for the slower heuristic are 0.18% and 1.02 seconds. The
algorithms for quickest FlowLoc problem with arc reversals are also designed.
With an objective to maximize the static/dynamic flows, and minimize quickest flow, the
problem of choosing a single shelter location are modeled as MaxStatic, MaxDynamic,
Quickest sink location problems respectively. We establish that each of such a problem can be solved in strongly polynomial time with or without arc reversals.
By reversing the direction of the traffic flow towards the sink, a contraflow
configuration may obstruct the paths towards the source. We model the problem of
maximizing the dynamic contraflow saving a path not exceeding a given length as a
mixed binary integer linear programming problem. The analogous problem of
minimizing the evacuation time is modeled as a mixed binary integer programming
problem with a fractional objective. A linearization strategy is suggested so that the
algorithms to solve the mixed integer linear programming problems can be used. The
problem of minimizing the path length and maximizing the dynamic contraflow has
been modeled as a bicriteria optimization problem. A procedure using -constrained
method is constructed to obtain efficient solutions. The solutions, using available
software solvers, considering a road network of Kathmandu city can be obtained
within 1 second. We also model the problem of minimizing the path length and
evacuation time as a bicriteria problem and construct a procedure to solve it.
We model a path saving model maximizing the dynamic contraflow to optimize a
general objective, as a bilevel program. To solve the problem, we replace the lower
level problem by Karush-Kuhn-Tucker (KKT) conditions converting it to a single level
non-linear binary integer program. We linearize it using a big M method and also
suggest a procedure to tune M.
Description
Keywords
Evacuation planning, Facility allocation