Lexicographic Maximum Flow Allowing Intermediate Storage

Abstract

In a capacitated network, an optimum solution of the maximum flow problem is to send as much flow as possible from the source node to the sink node as efficiently as possible by satisfying the capacity and conservation constraints. But, because of the limited capacity on the arcs, total amount of flow out going from the source may not reach to the sink. If the excess amount of flow can be stored at the intermediate nodes, total amount of flow outgoing from the source can be increased significantly. Similarly, different destinations have their own importance with respect to some circumstances. Motivated with these scenarios, we introduce the lexicographic maximum flow problems with intermediate storage in static and dynamic networks by assigning the priority order to the nodes. We extend this notion to arc reversals approach, a flow maximization technique, which is widely accepted in evacuation planning as it increases the outbound arc capacities by using the arc capacities on the opposite direction as well. Travel times along the anti-parallel arcs is considered to be unequal and we take into account the travel time of the reversed arcs to be equal to the travel time of the non-reversed arc towards which the arc is reversed. We present polynomial time algorithms for the solution of these problems.