A Lagrangian Relaxation Heuristic for Capacitated Facility Location with Single-Source Constraints |
| |
Authors: | John G Klincewicz Hanan Luss |
| |
Institution: | 1.AT&T Bell Laboratories,Holmdel |
| |
Abstract: | Facility location models are applicable to problems in many diverse areas, such as distribution systems and communication networks. In capacitated facility location problems, a number of facilities with given capacities must be chosen from among a set of possible facility locations and then customers assigned to them. We describe a Lagrangian relaxation heuristic algorithm for capacitated problems in which each customer is served by a single facility. By relaxing the capacity constraints, the uncapacitated facility location problem is obtained as a subproblem and solved by the well-known dual ascent algorithm. The Lagrangian relaxations are complemented by an add heuristic, which is used to obtain an initial feasible solution. Further, a final adjustment heuristic is used to attempt to improve the best solution generated by the relaxations. Computational results are reported on examples generated from the Kuehn and Hamburger test problems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|