Temporally Repeated Maximum Dynamic Flow with Intermediate Storage

The maximum dynamic flow problem intends to send the maximum amount of flow from a fixed node (source) to another fixed node (sink/destination) within the given time horizon. The storage of flow at intermediate shelters that do not reach the destination for some reason is one of the important issues in the network flow problem. Similarly, in the case of a two-way network, flow improvement by reversing the direction of arcs towards the destination is another widely accepted technique. Flow with intermediate storage and contraflow are very relevant issues for the evacuation planning, which can shift the maximum number of evacuees from danger zones to safe places. In this paper, we introduce a novel technique of temporally repeated flow to solve the maximum dynamic flow problem with intermediate storage for general network topology. We present a polynomial time algorithm to solve the problem. We discuss the earliest arrival flow problem with intermediate storage and its solution procedure on the series-parallel graph by holding the excess flow at intermediate nodes. We also introduce a maximum dynamic contraflow problem with intermediate storage and solve the problem by using temporal repetition of flows in polynomial time. We extend these problems in continuous time settings by using natural transformation. For the case illustration, we apply our algorithm to find maximum flow with intermediate storage using Python codes by taking the data of the Kathmandu road network.