Dynamic Contraflow with Orientation Dependent Transit Times Allowing Intermediate Storage

Abstract

Contraflow is one of the best and widely accepted techniques in evacuation planning problems, where the reversal of arcs is made to increase the amount and decrease the time of ow transmission. At the time of evacuation, if the flow value leaving the source node exceeds the bottleneck capacity of the network, then the storage of excess flow at comparatively safer intermediate nodes can be a milestone to save the life of evacuees. In this paper, we introduce the maximum dynamic contraflow problem in a general network and earliest arrival contraflow problem in two-terminal series-parallel network with asymmetric transit times on anti-parallel arcs. We present polynomial time solution strategies with orientation dependent transit times by allowing the storage of flow at intermediate nodes.