A Branch-and-Bound Method for the Fixed Charge Transportation Problem

Abstract

In this paper we develop a new conditional penalty for the fixed charge transportation problem. This penalty is stronger than both the Driebeek penalties and the Lagrangean penalties of Cabot and Erenguc. Computational testing shows that the use of these penalties leads to significant reductions in enumeration and solution times for difficult problems in the size range tested. We also study the effect of problem parameters on the difficulty of the problem. The ratio of fixed charges to variable costs, the shape of the problem, arc density in the underlying network and fixed charge arc density are shown to have a significant effect on problem difficulty for problems involving up to 40 origins and 40 destinations.