Priority Based Flow Improvement with Intermediate Storage

Every models in the network flow theory aim to increase flow value from the sources to the sinks and reduce time or cost satisfying the capacity and flow conservation constraints. Recently, the network flow model without flow conservation constraints at the intermediate nodes has been investigated by Pyakurel and Dempe \cite{pyadem:2019}. In this model, if the incoming flow to a intermediate node is greater than the outgoing flow, then the excess flow can be stored at the node respecting its capacity. Moreover, the model works if sum of the outgoing arc capacities from the source of a network is greater than the minimum cut capacity and intermediate node has storage capacity. The excess flow has been sent as far as possible from the source. In two-terminal network, the maximum static flow and maximum dynamic flow problems with intermediate storage have been solved in polynomial time complexities. Motivated by this work, we study the lexicographic maximum flow problem with intermediate storage in a single source and multiple sink networks by assigning priority ordering. The problem is to maximize the flow value at each sink in fixed priority ordering and push the excess flow from the source as far as possible to the intermediate nodes. We present polynomial time algorithms to solve it in both static and dynamic networks.


Submitted to International Journal of Operations Research, Taiwan



View Priority Based Flow Improvement with Intermediate Storage