Maximum Multi-Commodity Flow with Proportional and Flow-dependent Capacity Sharing

Multi-commodity flow problem concerns with the transshipment of more than one commodities from respective sources to the corresponding sinks without violating the capacity constraints on the arcs. If the objective of the problem is to sent maximum amount of flow within given time horizon, then it becomes the maximum flow problem. In multi-commodity flow problem, flow of different commodities departing from their sources may arrive the common intermediate node at the same time and have to share the capacity through the arc. The sharing of the capacity in the common arc (bundle arc) is one of the major issues in multi-commodity flow problem. To deal with this problem, we propose the proportional capacity sharing and flow-dependent capacity sharing techniques.

If the sharing of the capacity of the bundle arc is set in proportion to the bottleneck capacity of incoming arcs of each commodities from their respective sources, then it is known as proportional capacity sharing. In this case, share of the capacity of bundle arc for each commodity is fixed and the multi-commodity flow problem is reduced to independent single commodity flow problems. To avoid the fractional flow, we can use ceiling and floor functions with appropriate manner. Similarly, if the sharing of the capacity of bundle arc is made according to the inflow rate of the flow of each commodity, then it is termed as flow-dependent capacity sharing. In this method, the share of capacity of bundle arc may not always be same as the flow may vary over time.


In this work, we present the maximum static as well as maximum dynamic multi-commodity flow problems with proportional as well as flow-dependent capacity sharings. We also present polynomial and pseudo-polynomial time algorithms for these problems according to the proportional and flow-dependent sharing techniques, respectively.