Abstract
A heuristic algorithm for solving large scale fixed charge network flow problems (FCNFP) based on the dynamic slope scaling procedure (DSSP) and tabu search strategies is presented. The proposed heuristic integrates the DSSP with short-term memory intensification and long-term memory diversification mechanisms in the tabu scheme 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 iteratively adjusts the linear factors in the linear approximation of the FCNFP to produce promising search neighborhoods for good quality solutions. The comprehensive numerical experiments on various test problems ranging from sparse to dense network structures are reported. The overall comparison of the pure DSSP, the enhanced DSSP, and branch and bound (B&B by cutting-edge MIP optimizer in CPLEX) is shown in terms of solution quality and CPU time. The results show that the enhanced DSSP approach has a higher solution quality than the pure DSSP for larger scale problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Barr, R.S., Glover, F. and Klingman, D. (1981). A new optimization method for large scale fixed charge transportation problems. Operation Research, 29, 448–463.
Cabot, A.V. and Erenguc, S.S. (1984). Some branch-and-bound procedures for fixed-cost transportation problems. Naval Research Logistics Quarterly, 31, 145–154.
Crainic, T.G., Frangioni, A. and Gendron, B. (2001). Bundle-based relaxation methods for multicommodity capacitated fixed charge network design. Discrete Applied Mathematics, 112, 73–99.
Crainic, T.G., Gendreau, M. and Farvolden, J. (2000). A Simplex-based tabu search Method for capacitated network design. INFORMS, J. Computing, 12(3), 223-236.
Gendron, B. and Crainic T.G. (1994). Relaxation for multicommodity capacitated network design problems Publication CRT-965, Centre de Recherche Sur Les Transports, University of Montreal,
Geoffrion, A.M. (1974). Lagrangean relaxation for integer programming. Mathematical Programming Study, 2, 82–114.
Glover, F. (1994). Optimization by ghost image processes in neural networks. Computers & Operations Research, 21(8), 801–822.
Glover, F. (1989). Tabu search: Part I ORSA. Journal on Computing, 1(3), 190–206.
Glover, F. (1990). Tabu search: Part II ORSA. Journal on Computing, 2(1), 4–32.
Glover, F. and Laguna, M. (1997). Tabu Search, Kluwer Academic Publishers, Hingham, MA,
Gray, P. (1971). Exact solution of the fixed-charge transportation problem. Operations Research, 19(6), 1529–1538.
Hochbaum D.S. and Segev, A. (1989). Analysis of a flow problem with fixed charges. Networks, 19, 291–312.
Kim, D. and Pardalos, P.M. (1999,). A solution approach to the fixed charge network flow problem using a dynamic slope scaling procedure. Operations Research Letters, 24, 195–203.
Magnanti, T. L., Mireault, P. and Wong, R.T. (1986). Tailoring Benders decomposition for uncapacitated network design. Mathematical Programming Study, 26, 112–154.
Palekar, U.S., Karwan, M.K. and Zionts, S. (1990). A branch-and-bound method for the fixed charge transportation problem. Management Science, 36(9), 1092–1105.
Steinberg, D.I. (1970). The fixed charge problem. Naval Research Logistics Quarterly, 17, 217–235
Suhl, U. (1985). Solving large scale mixed integer programs with fixed charge variables. Mathematical Programming, 32, 165–182.
Sun, M., Aronson, J.E., McKeown, P.G. and Drinka, D. (1998). A tabu search heuristic procedure for the fixed charge transportation problem. European Journal of Operational Research, 106, 441–456.
Author information
Authors and Affiliations
Additional information
Research has been partially supported by NSF and CRDF grants.
Rights and permissions
About this article
Cite this article
Kim, D., Pan, X. & Pardalos, P.M. An Enhanced Dynamic Slope Scaling Procedure with Tabu Scheme for Fixed Charge Network Flow Problems. Comput Econ 27, 273–293 (2006). https://doi.org/10.1007/s10614-006-9028-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10614-006-9028-4