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

Author

Xinyan Pan, University of Tennessee, Knoxville

Date of Award

5-2004

Degree Type

Thesis

Degree Name

Master of Science

Major

Industrial Engineering

Major Professor

Dukwon Kim

Abstract

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.

Recommended Citation

Pan, Xinyan, "An Enhanced Dynamic Slope Scaling Procedure with Tahu Scheme for Fixed Charge Network Flow Problems. " Master's Thesis, University of Tennessee, 2004.
https://trace.tennessee.edu/utk_gradthes/4682