Quickest Multi-commodity Flow Problem with Capacity Sharing

Abstract

The quickest multi-commodity flow problem arises when more than one commodity is to be transported from the specific source nodes to corresponding sink nodes through the arcs in an underlying dynamic network within the minimum possible time. Sharing of the capacity of the bundle (common) arcs is one of the major issues for the multi-commodity flow problem. In this paper, we deal with the quickest multi-commodity flow problem by sharing the capacity of bundle arcs using proportional and flow-dependent capacity sharing techniques, which reduce the multi-commodity flow problem into single commodity flow problems. We present the polynomial and pseudo-polynomial algorithms to solve the problem by proportional and flow-dependent sharing, respectively. A three dimensional time-expanded layer graph is introduced to solve the problem with flow-dependent capacity sharing technique.