A solution approach to the fixed charge network flow problem using a dynamic slope scaling procedure

In this paper, we consider the Fixed Charge Network Flow Problem (FCNFP) wh ich is known to be NP-hard. It has many practical applications including tr ansportation, network design, communication, and production scheduling. Alt hough many exact methods have been developed to solve the FCNFP, their comp utational requirements increase exponentially with the size of the problem. Hence, heuristic approaches are needed to solve suboptimally large-scale p roblems. Here, we propose a new approach for solving the general capacitated (or unc apacitated) FCNFP by adapting an economic viewpoint of the fixed cost. A ne w concept of the dynamic slope scaling procedure is presented and some comp utational results on a wide range of test problems are reported. The larges t problem has 202 nodes and 10 200 arcs. The results show that the proposed procedure generates solutions within 0% to 0.65% of optimality in all case s. (C) 1999 Elsevier Science B.V. All rights reserved.