Models and Algorithms of Abstract Flows in Evacuation Planning

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.