The Fixed-Charge Transportation Problem: A Computational Study with a Branch-and-Bound Code

This paper presents the computational experience obtained with an experimental branch-and-bound code for the fixed-charged transportation problem. The code calculates simple penalties and uses a modern transportation routine to solve the linear programming relaxation. The findings of the investigation are as follows: (i) the solution times for problems with similar variable and fixed arc costs are highly variable, but performance definately worsens as fixed costs increase relative to variable costs with demands remaining constant, (ii) computational times decrease as total supply increases if other variables are held constant, (iii) computational times tend to vary inversely with the ratio of number of destinations to number of sources for ratios greater than unity if other variables are held constant, and (iv) problems with about 200 arcs may be solved if the fixed costs do not play too large a role, while problems with fewer than 100 arcs may blow up. We found no way to predict solution time as a function of problem characteristics.