APPROXIMATE SOLUTIONS TO LARGE-SCALE CAPACITATED FACILITY LOCATION-PROBLEMS
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
This article presents a heuristic algorithm for solving large scale capacitated facility location problems. The algorithm consists of solving a single source facility location problem and then solving a minimum cost network problem. The single source problem is solved by applying an iterative procedure in which lower bounds on the optimal objective value are generated through Lagrangian relaxation techniques. Upper bounds on the optimal objective value are obtained by modifying the Lagrangian solution to restore feasibility. The iterative procedure is terminated when the difference between the two bounds is within a prespecified tolerance. Further improvement of the objective value is attained by subjecting the single source solution to a network optimization code. The heuristic algorithm has been tested on over 300 problems, derived, in one form or another, from the Kuehn-Hamburger test problems. The testing has also been undertaken on the problems of Van Roy, which were generated using NETGEN. Computational results indicate that our approach can be effective in producing near-optimal solutions for problems with as many as 1000 customers and 100 potential facility locations. Most problems converged within 3 percent of the optimal value, requiring only a modest amount of computation on an IBM 3090. 1990.
