Efficient continuous contraflow algorithms for evacuation planning problems

Urmila Pyakurel (), Tanka Nath Dhamala () and Stephan Dempe ()
Additional contact information
Urmila Pyakurel: Tribhuvan University
Tanka Nath Dhamala: Tribhuvan University
Stephan Dempe: TU Bergakademie Freiberg, Fakultät für Mathematik und Informatik

Annals of Operations Research, 2017, vol. 254, issue 1, No 16, 335-364

Abstract: Abstract A productive research in the emerging field of disaster management plays a quite important role in relaxing this disastrous advanced society. The planning problem of saving affected areas and normalizing the situation after any kind of disasters is very challenging. For the optimal use of available road network, the contraflow technique increases the outward road capacities from the disastrous areas by reversing the arcs. Number of efficient algorithms and heuristics handle this issue with contraflow reconfiguration on particular networks but the problem with multiple sources and multiple sinks is NP-hard. This paper concentrates on analytical solutions of continuous time contraflow problem. We consider the value approximation earliest arrival transshipment contraflow for the arbitrary and zero transit times on each arcs. These problems are solved with pseudo-polynomial and polynomial time complexity, respectively. We extend the concept of dynamic contraflow to the more general setting where the given network is replaced by an abstract contraflow with a system of linearly ordered sets, called paths satisfying the switching property. We introduce the continuous maximum abstract contraflow problem and present polynomial time algorithms to solve its static and dynamic versions by reversing the direction of paths. Abstract contraflow approach not only increases the flow value but also eliminates the crossing at intersections. The flow value can be increased up to double with contraflow reconfiguration.

Keywords: Evacuation planning; Contraflow; Abstract flow; Switching property (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2427-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:254:y:2017:i:1:d:10.1007_s10479-017-2427-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-017-2427-1

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().