A Lagrangian heuristic algorithm for a public healthcare facility location problem

Dong-Guen Kim,  Yeong-Dae Kim


We consider a healthcare facility location problem in which there are two classes 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.

Keywords: facility location problem, healthcare facility, Lagrangian relaxation, heuristic

Contact Address :

Department of Industrial Engineering

Korea Advanced Institute of Science and Technology (KAIST)

373-1 Gusung-Dong, Yusong-Gu, Taejon 305-701, Korea

PHONE : +82-42-350-3160

FAX : +82-42-350-3110