Article ID: | iaor19911105 |
Country: | United States |
Volume: | 36 |
Issue: | 9 |
Start Page Number: | 1092 |
End Page Number: | 1105 |
Publication Date: | Sep 1990 |
Journal: | Management Science |
Authors: | Karwan Mark H., Zionts Stanley, Palekar Udatta S. |
Keywords: | combinatorial analysis, optimization |
In this paper the authors 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. The authors 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.