An Enhanced Dynamic Slope Scaling Procedure with Tahu Scheme for Fixed Charge Network Flow Problems

In this thesis, a heuristic algorithm for solving large scale fixed charge network problems (FCNFP) based on the dynamic slope scaling procedure (DSSP) and tabu search strategies is presented. The proposed heuristic (the enhanced DSSP) integrates the DSSP with the classical short-term memory intensification and long-term memory diversification mechanism in the tabu search to improve the performance of the pure DSSP. With the feature of dynamically evolving memory, the enhanced DSSP evaluates the solutions in the search history and it iteratively adjusts the linear factors of the LP approximations of the FCNFP to produce promising search neighborhoods for good quality solutions. Comprehensive numerical experiments are included in this thesis, ranging from sparse to dense network problems generated randomly. The computational results of the pure DSSP, the enhanced DSSP and branch and bound (B&B) are compared in terms of solution quality and CPU time. The enhanced DSSP approach has higher solution quality than the pure DSSP and much less computation time than B&B.