Efficient Dynamic Flow Algorithms for Evacuation Planning Problems with Partial Lane Reversal

Contraflow technique has gained a considerable focus in evacuation planning research over the past several years. In this work, we design efficient algorithms to solve the maximum, lex-maximum, earliest arrival, and quickest dynamic flow problems having constant attributes and their generalizations...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics (Basel) 2019-10, Vol.7 (10), p.993
Main Authors: Pyakurel, Urmila, Nath, Hari Nandan, Dempe, Stephan, Dhamala, Tanka Nath
Format: Article
Language:English
Subjects:
Algorithms
Approximation
contraflow configuration
Control theory
dynamic flow
Earthquakes
Emergency preparedness
Evacuation
evacuation planning
Heuristic
Humanitarianism
Integer programming
logistic supports
Mathematics
network optimization
Optimization techniques
partial lane reversals, algorithms and complexity
Planning
Polynomials
Reconfiguration
Road design
Time dependence
Traffic congestion
Traffic flow
Transit time
Transportation networks
Tsunamis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Contraflow technique has gained a considerable focus in evacuation planning research over the past several years. In this work, we design efficient algorithms to solve the maximum, lex-maximum, earliest arrival, and quickest dynamic flow problems having constant attributes and their generalizations with partial contraflow reconfiguration in the context of evacuation planning. The partial static contraflow problems, that are foundations to the dynamic flows, are also studied. Moreover, the contraflow model with inflow-dependent transit time on arcs is introduced. A strongly polynomial time algorithm to compute approximate solution of the quickest partial contraflow problem on two terminal networks is presented, which is substantiated by numerical computations considering Kathmandu road network as an evacuation network. Our results show that the quickest time to evacuate a flow of value 100,000 units is reduced by more than 42% using the partial contraflow technique, and the difference is more with the increase in the flow value. Moreover, the technique keeps the record of the portions of the road network not used by the evacuees.
ISSN:2227-7390
2227-7390
DOI:10.3390/math7100993