A Branch-and-Bound Method for the Fixed Charge Transportation Problem
为固定费用运输问题提出一种新的条件惩罚，比现有惩罚更强，能显著减少枚举和求解时间，并分析了问题参数对难度的影响。
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.