The Tug Fleet Size Problem for Barge Line Operations: A Polynomial Algorithm

In this paper the problem of minimizing the number of tugs required to transport a given number of barges between different ports in a river system is considered. The problem has traditionally been viewed as a vehicle routing problem and thus routing heuristics have been used. Advantage is taken of the feature that transfer time at ports is negligible, and the problem is modeled differently. A one-pass algorithm is developed which solves the problem in O(n) time. Extensions are made dealing with general river system structures and stochasticity in the demand pattern.