A vertex ranking algorithm for the fixed-charge transportation problem

In many distribution problems, the transportation cost consists of a fixed cost, independent of the amount transported, and a variable cost, proportional to the amount shipped. In this paper, we propose an efficient algorithm for solving the fixed-charged transportation problem, based on Murty's extreme point ranking scheme. An improved lower bound on the fixed costs developed in the paper and dynamic updating of upper bound on linear costs and ranking limits are demonstrated to improve the computational requirements of Murty's scheme significantly. The ideas developed are illustrated with the aid of an example. Finally, a stopping criterion with an ∈-optimum solution is introduced using Balinski's approximation scheme.