Abstract
We consider a healthcare facility location problem in which there are two types of patients, low-income patients and middle- and high-income patients. The former can use only public facilities, while the latter can use both public facilities and private facilities. We focus on the problem of determining locations of public healthcare facilities to be established within a given budget and allocating the patients to the facilities for the objective of maximizing the number of served patients while considering preference of the patients for the public and private facilities. We present an integer programming formulation for the problem and develop a heuristic algorithm based on Lagrangian relaxation and subgradient optimization methods. Results of computational experiments on a number of problem instances show that the algorithm gives good solutions in a reasonable computation time and may be effectively used by the healthcare authorities of the government.
Similar content being viewed by others
References
Aboolian, R., Berman, O., & Krass, D. (2007). Competitive facility location and design problem. European Journal of Operational Research, 183, 40–62.
Benati, S. (2003). An improved branch & bound method for the uncapacitated competitive location problem. Annals of Operations Research, 122, 43–58.
Berman, O., & Krass, D. (2002). Expenditures locating multiple competitive facilities: spatial interaction models with variable expenditures. Annals of Operations Research, 111, 197–225.
Berman, O., Verter, V., & Kara, B. Y. (2007). Designing emergency response networks for hazardous materials transportation. Computers and Operations Research, 34, 1374–1388.
Bischoff, M., & Dachert, K. (2009). Allocation search methods for a generalized class of location–allocation problems. European Journal of Operational Research, 192, 793–807.
Choi, S. S., & Lee, L. H. (2007). The multi-period demand changing location problem. Journal of the Korean Institute of Industrial Engineers, 33, 439–446.
Colin, R. R. (1993). Modern heuristic techniques for combinatorial problems (pp. 243–298). New York: Wiley.
Daskin, M. S., & Dean, L. K. (2004). 3. Location of Health Care Facilities. In M. L. Brandeau, F. Sainfort, & W. P. Pierskalla (Eds.), Operations research and health care (pp. 43–76). Dordrecht: Kluwer Academic.
Dominguez, E., & Munoz, J. (2008). A neural model for the p-median problem. Computers and Operations Research, 35, 404–416.
Drezner, Z., Drezner, Z., & Scott, C. H. (2009). Location of a facility minimizing nuisance to or from a planar network. Computers and Operations Research, 36, 135–148.
Fathali, J., & Kakhki, H. T. (2006). Solving the p-median problem with pos/neg weights by variable neighborhood search and some results for special cases. European Journal of Operational Research, 170, 440–462.
Fisher, M. L. (1981). The Lagrangean relaxation method for solving integer programming problems. Management Science, 27, 1–18.
Galvao, R. D., Espejo, L. G., & Boffey, B. (2000). A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem. European Journal of Operational Research, 124, 377–389.
Hakimi, S. L. (1983). On locating new facilities in a competitive environment. European Journal of Operational Research, 12, 29–35.
Hale, T., & Moberg, C. (2003). Location science research: a review. Annals of Operational Research, 123, 21–35.
Hong, S. H., & Lee, Y. H. (2004). The maximal covering location problem with cost restrictions. Journal of the Korean Institute of Industrial Engineers, 30, 93–106.
Hochbaum, D. S. (1997). Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. In Approximation algorithms for NP-hard problems (pp. 94–143). Boston: PWS-Kent.
Infante-Macias, R., & Mufioz-Perez, J. (1995). Competitive location with rectilinear distances. European Journal of Operational Research, 80, 77–85.
Jia, H., Ordonez, F., & Dessouky, M. (2007). A modeling framework for facility location of medical services for large-scale emergencies. IIE Transactions, 39, 41–55.
Kim, D. G., & Kim, Y.-D. (2010). A branch and bound algorithm for determining locations of long-term care facilities. European Journal of Operational Research, 206, 168–177.
Kim, D.-G., Kim, Y.-D., & Lee, T. (2012). Heuristics for locating two types of public health-care facilities. Industrial Engineering & Management Systems, 11, 202–214.
Lim, S. K., & Kim, Y.-D. (2001). Plant location and procurement planning in knockdown production systems. Journal of the Operational Research Society, 52, 271–282.
Lorena, L. A. N., & Senne, E. L. F. (2004). Guided construction search metaheuristics for the capacitated p-median problem with single source constraint. Computers and Operations Research, 31, 863–876.
Marianov, V., & ReVelle, C. (1996). The queueing maximal availability location problem: a model for the siting of emergency vehicles. European Journal of Operational Research, 93, 110–120.
Marianov, V., & Taborga, P. (2001). Optimal location of public health centers which provide free and paid services. Journal of the Operational Research Society, 52, 391–400.
McGarvey, R. G., & Cavalier, T. M. (2005). Constrained location of competitive facilities in the plane. Computers and Operations Research, 32, 359–378.
Ndiaye, M., & Alfares, H. (2008). Modeling health care facility location for moving population groups. Computers and Operations Research, 35, 2154–2161.
Osman, I. H., & Ahmadi, S. (2007). Guided construction search metaheuristics for the capacitated p-median problem with single source constraint. Journal of the Operational Research Society, 58, 100–114.
Plastria, F., & Vanhaverbekea, L. (2008). Discrete models for competitive location with foresight. Computers and Operations Research, 35, 683–700.
Rahman, S., & Smith, D. K. (2000). Use of location-allocation models in health service development planning in developing nations. European Journal of Operational Research, 123, 437–452.
Resende, M. G., & Werneck, R. F. (2007). A fast swap-based local search procedure for location problems. Annals of Operations Research, 150, 205–230.
ReVelle, C., Scholssberg, M., & Williams, J. (2008). Solving the maximal covering location problem with heuristic concentration. Computers and Operations Research, 35, 427–435.
Toregas, C., Swain, R., ReVelle, C., & Bergman, L. (1971). The location of emergency service facilities. Operations Research, 19, 1363–1373.
Verter, V., & Lapierre, S. D. (2002). Location of preventive health care facilities. Annals of Operations Research, 110, 123–132.
Younies, H., & Wesolowsky, G. O. (2007). Planar maximal covering location problem under block norm distance measure. Journal of the Operational Research Society, 58, 740–750.
Zhang, Y., Berman, O., & Verter, V. (2009). Incorporating congestion in preventive healthcare facility network design. European Journal of Operational Research, 198, 922–935.
Zhang, Y., Berman, O., Marcotte, P., & Verter, V. (2010). A bilevel model for preventive healthcare facility network design with congestion. IIE Transactions, 42, 865–880.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kim, DG., Kim, YD. A Lagrangian heuristic algorithm for a public healthcare facility location problem. Ann Oper Res 206, 221–240 (2013). https://doi.org/10.1007/s10479-013-1378-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-013-1378-4