Successive linear approximation procedure for generalized fixed-charge transportation problems

This paper develops a new heuristic procedure for solving a generalization of the fixed-charge transportation problem in which there are resource losses in addition to the fixed charges. The losses may be evaporation losses when the commodity is a liquid, heat losses in an electrical distribution network, or deterioration losses in distribution networks involving perishable commodities such as, for example, food items. The proposed procedure consists of solving a sequence of pro-rated problems. It is different from heuristic procedures that have been developed for solving the standard fixed charge transportation problem, in that it is not based on extreme point enumeration. Problems involving up to 2100 arcs with fixed charges and resource losses are experimented with. The results show that the proposed approach is viable for solving medium-to-large sized problems.