Transshipment Contraflow on Multi-Terminal Networks

Abstract

Contraflow technique is the widely accepted model on network optimization. It allows arc reversal that increases the arc capacities. The earliest arrival transshipment contraflow is an important model that transship the given flow value by sending the maximum amount at each time point from the beginning within given time period by reversing the direction arcs from the sources to the sinks at time zero. This problem has not been solved polynomially on complex networks, i.e., multi-terminal networks yet. However, its 2-value-approximation solution has been found by Pyakurel and Dhamala [13] in pseudopolynomial time complexity. Moreover, they have claimed that for the special case of zero transit time on each arc, the 2-value-approximation solution can be computed in polynomial time complexity. In this paper, we solve their claim presenting an efficient algorithm.