Abstract
In this paper we consider the classical capacitated facility location problem. A branch and bound algorithm is presented which measurably improves upon the recent results of Akinc and Khumawala. The use of a specialized Lagrangean relaxation results in significantly tighter bounds than those for the traditional continuous relaxation. These bounds, when combined with penalties derived from the Lagrangean relaxation, enable many integer variables to be fixed at specific values. This results in fewer branches, and indeed for certain test problems taken from the literature, branching is not required. Average computation time for a battery of test problems from the literature has been reduced (conservatively) by a factor of 3.
Similar content being viewed by others
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Nauss, R. An Improved Algorithm for the Capacitated Facility Location Problem. J Oper Res Soc 29, 1195–1201 (1978). https://doi.org/10.1057/jors.1978.263
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.1978.263