APPROACHES FOR SOLVING THE FIXED CHARGE TRANSPORTATION PROBLEM

The fixed charge transportation problem frequently arises in production systems, physical distribution, data processing problems, etc. The problem is a variation of the classical linear cost transportation problem. In addition to the linear costs associated with the transportation of a commodity from a supply to a destination, a fixed charge is assessed whenever transportation occurs between a supply and destination. This fixed charge may be different for every supply-destination pair.;We develop two heuristic procedures to solve the fixed charge transportation problem. These are the Iterative Linear Programming Heuristic and the Dual Setting Heuristic. The iterative linear programming heuristic is shown to give good feasible solutions.;We also develop an a priori characterization of the difficulty of a problem based on its data. We show that the difficulty of the problem is a function of the ratio of fixed costs and variable costs; the shape of the problem; the size of the problem; the arc density and the fixed charge arc density of the problem. We show that the rules defined are able to identify problems that are difficult to solve.;All methods were implemented and tested using a randomly generated fixed charge transportation problems. Results of these tests are reported.;This problem can be mathematically formulated as an integer programming problem. Numerous attempts have been made to solve this problem. All the successful attempts use a branch and bound strategy to the problem. The bounding used in these approaches is a linear programming bound augmented by suitable penalties. We develop new penalties which are superior to those used in the past. These penalties are shown to be computationally superior to other penalties. To accelerate the branch and bound process we examine duality-based bounds. In this context we study Lagrangean and surrogate bounds. We also examine the newly introduced Lagrangean decomposition relaxation. We introduce a surrogate decomposition relaxation and study its properties in the context of the fixed charge transportation problem. The duality-based bounds are found to be ineffective in accelerating the branch and bound process.