Models and Algorithms of Abstract Flows in Evacuation Planning

Authors

  • Chhabi Lal Bhusal Tribhuvan Multiple Campus, Tribhuvan University, Nepal

DOI:

https://doi.org/10.3126/pp.v11i1.55501

Keywords:

Abstract flow, Contraflow, Algorithm, Lexicographically maximum abstract contraflow, Earliest arrival abstract contraflow

Abstract

Flows over time generalize classical network flows by introducing a notion of time. Each arc is equipped with a transit time that specifies how long flow takes to traverse it, while flow rates may vary over time within the given edge capacities. Ford and Fulkerson’s original 1956 max flow/min cut paper formulated max flow in terms of flows on paths. In 1974, Hoffman pointed out that Ford and Fulkerson’s original proof was quite abstract, and applied to a wide range of max flow-like problems. In this abstract model we have capacitated elements and linearly ordered subsets of elements called paths that satisfy switching property. When two paths P and Q cross at an element (node) then there must be a path that is a subset of the first path up to the crossing element and a subset of the second path after the crossing element. Contraflow is a widely accepted solution approach that increases the flow and decreases the evacuation time making the traffic smooth during evacuation by reversing the required road directions from the risk areas to the safe places. In this paper, we integrate the abstract flow with contraflow, give mathematical formulations of these models and present efficient polynomial time algorithms for solving the abstract contraflow problems.  

Downloads

Download data is not yet available.
Abstract
63
PDF
39

Author Biography

Chhabi Lal Bhusal, Tribhuvan Multiple Campus, Tribhuvan University, Nepal

Lecturer in Mathematics

Downloads

Published

2023-06-12

How to Cite

Bhusal, C. L. (2023). Models and Algorithms of Abstract Flows in Evacuation Planning. Prāgyik Prabāha, 11(1), 1–10. https://doi.org/10.3126/pp.v11i1.55501

Issue

Section

Articles