Dynamic Network Contraflow Evacuation Planning Problem
Date
2020
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Department of Mathematics
Abstract
Evacuation planning problem gives effcient way-out on existing road network that attempts
to shift evacuees from risk zone to safer in minimum time with minimum casualty during
disasters. Its domain based on network
ow problems has been
ourished with models and
solutions with various network attributes. A common feature on almost all of these models
is that the
ow function obeys conservation constraints at each intermediate vertex. In
particular, maximum dynamic
ow (MDF) problem, earliest arrival
ow (EAF) problem
and quickest
ow (QF) problem have great applicability in evacuation planning problems.
Contra
ow approach recon gures the network identifying ideal direction and reallocating
available capacity for each arc to improve
ow egress time and/or improve the number of
ow units from source to sink. This thesis sketches a brief survey of models and results
on contra
ow evacuation planning problems. Continuous time model for maximum dynamic
contra
ow (MDCF) problem is studied with its e cient solution. Thesis also extends
contra
ow model for multi-network. Network modi cation strategy is applied to give polynomial
time algorithms to solve the problems; namely, MDCF problem and earliest arrival
contra
ow (EACF) problem based on extended model with discrete as well as continuous
time setting. The former problems are considered in general networks whereas the latter
problems in two terminal series parallel (TTSP) networks. Arc reversibility is allowed only
once at time zero in each of the cases.
Evacuation models with intermediate temporary shelters could be extra bene t while implementing
them. This thesis formulates, as another contribution,
ow model for network
with capacitated vertices of given priority order in which
ow conservation may be violated.
This violation makes possible for
ow units to be held at intermediate vertices which turns
out to be applicable in modeling an evacuation planning problem with intermediate holding
of evacuees at temporary shelters despite sending them into the sink. Based on this model,
maximum
ow problem is considered and proposed a polynomial solution for static case and
pseudo-polynomial solution for dynamic case. Also, polynomial solutions for MDF problem
and QF problem modeled on uniform path length (UPL) network and for EAF problem modeled
on UPL-TTSP network are proposed. As the nal contribution, contra
ow approach is
linked to evacuation problems with capacitated prioritized vertices.
Keywords: Network
ow models, Contra
ow, Capacitated vertices, Evacuation planning
problem, Disaster management.
Description
Keywords
Network ow models, Evacuation planning problem, Capacitated vertices, Disaster management