Lexicographic Static FlowLoc with/without Excess Storage

Abstract

Maximizing the flow value in a multi-terminal (multiple sources and multiple sinks) network using lexicographic supply from sources to sinks, reduce conflicts in the movement of flows toward the destinations. However, installing facilities on arcs reduce the arc capacities, which may hinder the maximum flow value. Nevertheless, such installations are necessary to supply facilities to the commodity. On the other hand, if intermediate nodes have storage capacity, the excess flow which cannot reach the sinks, can be stored at these nodes. As a result, the overall flow value can be improved. In this paper, we integrate the concepts of facility allocation together with intermediate storage and introduce lexicographic maximum static flow problems with and without intermediate storage. We investigate their corresponding flow models. The multi-facility problems are solved using heuristic approaches, whereas polynomial-time algorithms are presented for the single facility problem.