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

Multi-commodity flow problems concern 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 send the 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 arrive at the common intermediate node 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 the multi-commodity flow problems. In this paper, we introduce the maximum static and maximum dynamic multi-commodity flow problems with proportional capacity sharing and present polynomial time algorithms to solve the problems. Similarly, we investigate the maximum dynamic multi-commodity flow problem with flow-dependent capacity sharing and present a pseudo-polynomial time solution strategy.