A Lagrangian heuristic algorithm for a public healthcare facility location problem

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.

1 Introduction

Governments of most developed and developing countries provide public services such as healthcare services to low-income people who have difficulty paying for private services due to expensive costs. Meanwhile, private service providers seek to maximize profit by getting more middle- and high-income customers. Since middle- and high-income people may also use public service facilities if the service provided by the public facilities is good, there may be competition between public and private facilities. In this paper, we consider a problem of determining locations of public healthcare facilities to be newly established and allocating potential patients to the public facilities under such circumstances (of competition between public and private healthcare facilities).

In the problem considered in this study, patients, who are potential users of the healthcare facilities, are scattered over the country, and they can be grouped into patient groups according to their locations. Each group of patients is represented by a demand point, which may be a candidate location for the facilities. The total budget for the establishment of the facilities is limited. Also, each facility has its own capacity, i.e., the number of sickbeds. There are two classes of patients in each patient group: low-income patients and middle- and high-income patients. Low-income patients mean patients requiring governmental healthcare assistance, while the other two groups of patients do not require governmental assistance. The middle- and high-income patients will be denoted as high-income patients for short in the remaining of this paper. It is assumed in this study that each class of patients in each patient group can be assigned to at most one facility.

Usually, low-income people are assigned to the public facilities according to the government policy. If they use the public facilities assigned to them, they can get services free or at significantly lower costs. In general, low-income patients have difficulty using a facility located far from their homes, and they can use facilities that are located within a reachable distance (or travel time). On the contrary, high-income patients use their most favorite facility considering not only distance but also equipment, cost, service quality, etc., even though they are not located near their homes. Since high-income patients pay normal cost (not discounted cost for low-income patients) even in the public facilities, the public facilities want and try to get more high-income patients.

In Korea, the costs of healthcare services provided by public facilities are different depending on the economic condition of patients. By the national basic living security act and the medical care assistance act, (low-income) people requiring governmental healthcare assistance are entitled to use public healthcare facilities free or at lower cost. Since the public facilities serve high-income people at normal cost, the government considers tradeoffs between satisfying the need of low-income patients for healthcare services and getting higher profit by serving high-income patients. Considering such situation of Korea, we focus on the problem with the objective of maximizing the weighted sum of the number of low-income patients and the number of high-income patients served by the public facilities. We assume that there already exist a number of public and private facilities.

There have been research articles on facility location problems in various areas such as distribution systems, transportation networks, telecommunication networks and healthcare systems (Hale and Moberg 2003; Fathali and Kakhki 2006; Drezner et al. 2009). Studies on facility location problems can be classified into two groups. One group of studies focuses on the problems of determining facility locations with the objective of minimizing the cost or minimizing the number of facilities while satisfying demands (Lim and Kim 2001; Lorena and Senne 2004; Choi and Lee 2007; Osman and Ahmadi 2007; Resende and Werneck 2007; Dominguez and Munoz 2008; Bischoff and Dachert 2009). In the other group of studies, researchers deal with the problems with the objective of maximizing the number of demand locations covered by a given number of facilities while assigning demand locations to the facilities within a reachable distance (Galvao et al. 2000; Hong and Lee 2004; Berman et al. 2007; Younies and Wesolowsky 2007; ReVelle et al. 2008).

There have also been many research articles on facility location problems in healthcare systems (Rahman and Smith 2000; Daskin and Dean 2004). Toregas et al. (1971) consider the location problem of emergency medical service (EMS) facilities as a set covering problem of finding the minimum number of facilities required to satisfy the demand for the service, and Jia et al. (2007) deal with the problem of determining locations of EMS facilities for a large-scale EMS system. On the other hand, Marianov and ReVelle (1996) develop a probabilistic model for determining the locations of EMS facilities, and Verter and Lapierre (2002) consider a problem of locating preventive healthcare facilities for preventive such as blood tests and cancer screening exams. In addition, Ndiaye and Alfares (2008) deal with a problem of locating public facilities for nomadic patient groups, and Kim and Kim (2010) develop a branch and bound algorithm for locating long-term care facilities. Recently, Zhang et al. (2009, 2010) consider congestion in preventive healthcare facility network design problems, and Kim et al. (2012) deal with a facility location problem in which there are two types of public healthcare facilities.

A number of researchers consider cases in which there is competition among the facilities. There are two groups of studies on facility location problems in which competition among the facilities is considered. In one group of the studies, it is assumed that demands are assigned to the facilities with the shortest travel distance or travel time (Hakimi 1983; Infante-Macias and Mufioz-Perez 1995; Marianov and Taborga 2001; Plastria and Vanhaverbekea 2008), while in the other group, it is assumed that demands are assigned to the facilities with the highest utility, or preference, which is given as a function of several factors such as distance, equipment, and service quality (Berman and Krass 2002; Benati 2003; McGarvey and Cavalier 2005; Aboolian et al. 2007).

In this paper, we consider a healthcare facility location problem of determining the locations of public facilities to be newly established and allocating potential patients to the facilities under the assumption that there are existing public and private facilities and there is competition among the facilities. We develop a heuristic algorithm for the problem based on Lagrangian relaxation and subgradient optimization methods. This paper is organized as follows. Section 2 presents a detailed description of the problem with assumptions made in this study and a mathematical formulation for the problem. A heuristic algorithm for the problem is developed in Sect. 3, and performance of the algorithm is evaluated through a series of tests on a number of randomly generated problem instances and results are reported in Sect. 4. Finally, Sect. 5 concludes the paper with a short summary and discussions on possible extensions.

2 The public healthcare facility location problem

There are two types of patients, low-income patients who require governmental healthcare assistance and high-income patients who do not require. There are two types of (existing or newly established) healthcare facilities, public and private healthcare facilities. The goals of the public and private healthcare facilities are different. While the goal of private healthcare facilities is usually to maximize profits, that of public healthcare facilities is to provide healthcare service for all people, especially for the disadvantaged or low-income people.

When the public healthcare system is designed and operated, the government must consider both the level of governmental healthcare assistance on the low-income patients and the cost of operating the system that depends on the profitability of facilities. Since the budget required for the public healthcare facilities is supported by the government, it wants to reduce the cost of operating them or increase profit by serving more high-income patients, who pay normal costs (not discounted costs). Therefore, the government wants to maximize both the number of low-income patients and the number of high-income patients served by the public facilities. In this research, assuming that the government has pre-determined weights (importance) for the low-income patients and the high-income patients, we give relative weights to these two types of patients (based on the importance) in the problem considered here.

The public healthcare facility location problem considered in this study is to determine the locations of public healthcare facilities and to allocate low-income patients to existing and newly established facilities with the objective of maximizing the weighted sum of the number of low-income patients and the number of high-income patients served by the public facilities with a given budget for establishment of new public facilities.

The following assumptions are made in this research.

• (1) There are public facilities and private facilities that have been already established.

• (2) Patients in a region are represented with a patient group. Each patient group is specified by the number of patients in the region and the representative location of the region. Patients in a patient group have the same preference for healthcare facilities.

• (3) Low-income patients can use a public facility selected (and assigned to them) from those within a given reachable distance (or travel time).

• (4) High-income patients use their most favorite (public or private) facility.

• (5) The preferences of the high-income patients for the public and private facilities, including those to be newly established, are given. (They depend on the distance to the facilities, cost, quality of the service, and so on.)

• (6) A new public facility can be located at one of the (representative) locations of the patient groups.

• (7) No more than one facility can be located at a location. That is, at each location, there is currently at most one facility, public or private.

• (8) The capacity (number of sickbeds) of each (existing or candidate) facility is given and the establishment cost for each candidate facility is known. The capacity of a candidate facility can be given or determined by considering information of the associated location, such as population of the location and the number of private healthcare facilities in the location.

• (9) There is a limit on the total budget for the establishment of new public facilities.

For a clearer description of the problem considered in this paper, we give a mathematical formulation for the problem. In the formulation and throughout this paper, the following notation is used.

J :

set of patient groups (facility locations)

i, j, l :

indices for patient groups and/or facility locations (i, j, l∈J)

L _i :

number of low-income patients in patient group i

H _i :

number of high-income patients in patient group i

d _ij :

distance between the location of patient group i and the facility at location j (travel time may be used instead of distance)

D :

(given) reachable distance of low-income patients

c _ij =1:

if d _ij ≤D, and 0 otherwise, that is, the low-income patients of patient group i can use the public facility at location j if c _ij =1

p _ij :

preference of the high-income patients of patient group i for the facility at location j

a _j :

cost of establishing a public facility at location j

b _j :

capacity of (candidate or existing) facility j

w :

weight for low-income patients (when the weight for high-income patients is 1), w≥0

B :

total budget for the establishment of new public facilities

s _j =1:

if there is an existing public facility at location j, and 0 otherwise

t _j =1:

if there is an existing private facility at location j, and 0 otherwise

S={j∣s _j =1}:

i.e., the set of facility locations where there are existing public facilities

T={j∣t _j =1}:

i.e., the set of facility locations where there are existing private facilities

x _ij :

binary decision variable that is equal to 1 if low-income patients of patient group i are to be served by the (public) facility at location j, and 0 otherwise

y _ij :

binary variable that is equal to 1 if high-income patients of patient group i are to be served by the (public or private) facility at location j, and 0 otherwise

z _j :

binary decision variable that is equal to 1 if a new public facility is to be established at location j, and 0 otherwise

An integer programming formulation for the problem is given below.

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

In the objective function, ∑ _i∈J ∑ _j∈J∖T c _ij L _i x _ij and ∑ _i∈J ∑ _j∈J∖T H _i y _ij are the total number of low-income patients and the total number of high-income patients served by public healthcare facilities, respectively. Constraint sets (2) and (3) ensure that low-income patients and high-income patients of each patient group are allocated to at most one public facility, respectively. By (4), low-income patients can be allocated to only public facilities. Constraint set (5) ensures that at most one facility can be located at a candidate facility location. That is, if there is an existing public or private facility at a location, the location is not to be selected for a new public facility. Also, constraint set (6) ensures that the number of patients served by a facility does not exceed its capacity, while (7) ensures that high-income patients of each patient group are served by their preferred facility among the private or public facilities established or to be established. Note that the left-hand side of (7) represents the preference of patient group i for a selected facility while the right-hand side represents the preference of the patient group for a facility at location j. This constraint becomes effective only if there is a facility at location j, i.e., s _j +t _j +z _j =1. Constraint (8) is the budget constraint for the establishment of new public facilities. The number of integer variables in this model is 2n ²+n, and the number of constraints is 4n ²+5n+1, where n is the number of patient groups (facility locations), |J|.

3 The solution approach

Since it takes an excessive amount of time to obtain optimal solutions for problems of reasonable sizes using an integer programming solver, we develop a heuristic algorithm in this study. Note that a special case of this problem, the maximal covering problem, is proven to be NP-hard (Hochbaum 1997). The suggested heuristic algorithm is based on Lagrangian relaxation and subgradient optimization methods. Foundations of the Lagrangian relaxation method and surveys on successful applications to capacitated facility location problems are given in Fisher (1981) and Colin (1993). Note that from solutions of relaxed problems obtained by Lagrangian relaxation and subgradient optimization methods, the solution of original problem is founded relatively easily and quickly.

3.1 Lagrangian relaxation

We relax the original problem [P] by dualizing constraints (2) and (3) with Lagrangian multipliers λ _i ≥ 0 and μ _i ≥ 0, respectively. Let λ and μ be the vectors of the multipliers. Then, the relaxed problem can be given as follows. Note that the solution values of this relaxed problem are upper bounds on the optimal solution value of [P].

(12)

(13)

In this study, we solve [LR], or determine the values of x _ij , y _ij and z _j , in two steps. First, we determine the values of z _j , or locations of public facilities to be established, considering the effect of establishing a public facility at each candidate location, i.e., the number of patients served by the facility. Then, we determine the values of x _ij and y _ij , or assign patients to the facilities, to maximize the weighted sum of the numbers of two types of patients served by public facilities.

To evaluate the effect of establishing a public facility at a candidate location, we disregard constraint (8) for the time being and let [LR′] denote this relaxed problem without (8). For a set of given values λ and μ, [LR′] can be decomposed into subproblems, one subproblem for each candidate location, j∉T. The objective function value of the subproblem associated with location j is used for the measure of the effect. Note that at location j∈T, a public facility cannot be established, and hence x _ij =0 for j∈T. The subproblem associated with location j, [SP _j ], can be given as follows.

(4′)

(5′)

(6′)

(7′)

(9′)

(10′)

(11′)

Note that the composition of feasible solutions of [SP _j ] for all j may result in an infeasible solution of [LR′]. To obtain a feasible solution of [LR′] using [SP _j ] and to reduce the size of the input data with pre-processing, we modify the formulation as follows. Let F _j and G _j denote the set of high-income patient groups that might use a facility at location j and the set of low-income patient groups that can use a facility at location j, respectively, i.e., F _j ={i|p _ij ≥max _{k∈(S∪T∪{j})} p _ik } and G _j ={i|c _ij =1}. We replace (6′) and (7′) in [SP _j ] with

$$ \sum_{i \in G_{j}} L_{i}x_{ij} + \sum _{i \in F_{j}} H_{i}y_{ij} \leq b_{j}(s_{j} + t_{j} + z_{j}). $$

(6″)

With (6′) and (7′), one can obtain a solution in which high-income patients are served by their preferred facility and the number of patients served by a facility does not exceed its capacity. Also, (6″) ensures that the sum of the number of low-income patients assigned to a facility and the number of high-income patients who prefer the facility, the left-hand side, does not exceed the capacity of the facility, right-hand side. However, if (6′) and (7′) are used in [SP _j ], patients who prefer existing facilities to facility j can be assigned to facility j in a solution of [SP _j ], which violates constraint (7) in [LR′]. On the other hand, if (6″) is used instead, only those patients who prefer facility j to existing facilities are assigned to facility j since not only facility j but all existing facilities (in S and T) are considered together in F _j , and hence resulting solutions are feasible to [LR′].

Next, to evaluate the effect of establishing a public facility at candidate location j, we assume that there is a public facility at the location, i.e., s _j +z _j =1 and t _j =0. In this case, constraints sets (4′), (5′), and (11′) can be disregarded since they are satisfied by this assumption (s _j +z _j =1 and t _j =0), and constraint (6″) can be substituted with constraint (6‴). Then, we have the following subproblems.

(6‴)

Note that [SP′ _j ] with given λ _j and μ _j is a 0–1 knapsack problem, in which low-income patients to be assigned to facility j are to be selected within the capacity of facility j, b _j , considering high-income patients that will choose facility j. The solution of [$\mathrm{SP}'_{j}$], values of x _ij and y _ij , is obtained with a dynamic programming algorithm in our solution approach.

Once the solutions of [SP′ _j ] are obtained for a given set of values for λ _i and μ _i , we determine the values for z _j ’s considering (8), the budget constraint, in [LR]. Let $V _{j}^{*}$ denote the solution value of [SP′ _j ]. Then, the objective function of [LR] can be given as $\sum_{j \in J} V_{j}^{*}(z_{j} + s_{j}) + \sum_{i \in J\backslash T} (\lambda_{i} + \mu_{i})$. Note that

Since $\sum_{j \in J} V_{j}^{*}s_{j}$and ∑ _i∈J∖T (λ _i +μ _i ) are given, we can determine the values of z _j ’s by solving the following 0–1 knapsack problem, for which an optimal solution is obtained with a dynamic programming algorithm. Note that we only need to consider j∉T in this knapsack problem (to determine the values of z _j ).

(8)

(11)

Let $z_{j}^{*}$ be the solution of [KP]. Then, the solution of [LR], i.e., the values of z _j , x _ij and y _ij , is obtained using the values of $z_{j}^{*}$’s as follows. First, the values of z _j are set to $z_{j}^{*}$ for all j, and then for each j, if $s _{j} +z_{j}^{*}=1$, values of x _ij and y _ij are set to the same values as those obtained in [SP′ _j ]; otherwise (if $s _{j} +z_{j}^{*}=0$), we set x _ij =0 and y _ij =0.

3.2 Finding the best Lagrangian multipliers

To find a good solution in the Lagrangian heuristic algorithm, or to find a good upper bound on the optimal solution, we need to find good, or appropriate, values for the Lagrangian multipliers, and the following Lagrangian dual problem, [LD], is used for the purpose.

$$[\mathrm{LD}] \min_{\boldsymbol{\lambda} \geq \mathbf {0},\boldsymbol{\mu} \geq \mathbf{0}}\mathrm{Z}(\boldsymbol{\lambda},\boldsymbol{\mu}) $$

Note that solutions of [LD] serve as upper bounds for [P]. In this study, we use the subgradient optimization method described in Fisher (1981) to solve [LD] and obtain values for the Lagrangian multipliers. For given multipliers at iteration $k, \lambda_{i} ^{k}$ and $\mu_{i} ^{k}$, the Lagrangian multipliers at the next iteration are set as

where $\hat{x}_{ij}$ and $\hat{y}_{ij}$ are the solution of [LR] obtained at iteration k. The step size for the multipliers for iteration k, t ^k is computed as

$$t^{k} = \pi^{k} \bigl(Z \bigl[\boldsymbol{\lambda} ^{k},\boldsymbol{\mu} ^{k} \bigr] - Z_{\mathrm{LB}} \bigr) \Big/ \biggl( \biggl \Vert \sum_{i \in J} \hat{x} {}_{ij} - 1 \biggr \Vert ^{2} + \biggl \Vert \sum _{i \in J} \hat{y} {}_{ij} - 1 \biggr \Vert ^{2} \biggr), $$

where π _k is a scalar step size satisfying 0<π _k ≤2 and Z _LB is the best lower bound (on the solution value of [P]) obtained so far. Initially, the value of π _k is set to 2, i.e., π ₀=2, and π _k is halved if the lower bound (the solution value of [LD]) has not been improved for a given number of iterations. This rule performs well empirically, even though the convergence of the solution to the optimal solution is not guaranteed.

3.3 Obtaining a feasible solution

Since the solutions of the relaxed problems may be infeasible to the original problem [P], we develop a heuristic procedure to convert an infeasible solution to a feasible solution. First, assuming new facilities are established at locations which are selected in the solution of [LR], we assign patient groups, i’s, such that ∑ _j∈J x _ij ≥1 or ∑ _j∈J y _ij ≥1 in the solution of [LR], to the facilities. Starting from the patient group with the largest number of high-income patients, high-income patients in those patient groups are assigned to their preferred facility among all established facilities. Also, starting from the patient group with the largest number of low-income patients, low-income patients in those patient groups are assigned to the facility of which the remaining capacity is largest among facilities within the reachable distance from the patient group. Then, we additionally assign patient groups that are not assigned yet to facilities with positive remaining capacity as follows: high-income patients are assigned to their most favorite facility and low-income patients are assigned to the facility with the maximum remaining capacity among facilities within the reachable distance, until there is no facility with sufficient remaining capacity. The solution obtained with this procedure is always feasible, because new public facilities are established within the total budget limit and patients are assigned to the facilities considering the capacity of facilities and the reachable distance.

A procedure of the heuristic is given below. Here, $\hat{z}_{j}$, $\hat {x}_{ij}$ and $\hat{y}_{ij}$ denote the solutions of [LR]. In addition, [i] and {i} denote the index of the patient group with the ith largest number of high-income patients among all patient groups and the index of the patient group with the ith largest number of low-income patients, respectively.

Procedure 1

(Obtaining feasible solution)

Step 1.:

Let $z _{j} \leftarrow\hat{z}_{j}$ for all j.

Step 2.:

For i=1 to |J|, do: if $\sum_{j \in J} \hat {y}_{[i]j} \geq 1$ and if there is enough remaining capacity at the most favorite facility of high-income patients at patient group [i] among facilities, j’s, such that $\hat{y}_{[i]j}=1$, assign those high-income patients to that facility; otherwise, continue (for the next i).

Step 3.:

For i=1 to |J|, do: if $\sum_{j \in J} \hat {x}_{\{ i\} j} \geq 1$ and if there are public facilities with enough remaining capacity for low-income patients of patient group {i}, assign those low-income patients to a public facility with the maximum remaining capacity among public facilities within the reachable distance; otherwise, continue.

Step 4.:

For i=1 to |J|, do: if ∑ _j∈J y _[i]j =0 and if there is enough remaining capacity at the most favorite facility of high-income patients at patient group [i], assign those high-income patients to that facility; otherwise, continue.

Step 5.:

For i=1 to |J|, do: if ∑ _j∈J x _{i}j =0 and if there are public facilities with enough remaining capacity for low-income patients of patient group {i}, assign those low-income patients to a public facility with the maximum remaining capacity among public facilities within the reachable distance; otherwise, continue.

3.4 Procedure of the Lagrangian heuristic algorithm

In the Lagrangian heuristic developed in this study, [LR] is solved for each set of values for λ and μ, while Procedure 1 is executed to find a good feasible solution once in 10 times of solution of [LR]. The heuristic is terminated when one of the following three conditions is satisfied: (1) the iteration count (k) reaches a predetermined limit, K; (2) the difference between a feasible solution value and an upper bound is less than a predetermined limit, called the error limit, ε; and (3) the step size, π _k , is less than a predetermined value, π ^T. It can be terminated as well when an optimal solution is found (when the solution of the relaxed problem is feasible for the original problem). The overall solution procedure of the Lagrangian heuristic can be summarized as follows.

Procedure 2

(LAGH)

Step 1.:

Set k←0, l←0, π _k ←2, λ←0 and μ←0.

Step 2.:

If k>K or π _k <π ^T, stop; otherwise, go to step 3.

Step 3.:

Obtain an upper bound by solving [SP′ _j ] and [KP] with a dynamic programming algorithm, and let k←k+1. If the solution is feasible to the problem [P], terminate. The current solution is optimal. Otherwise, go to step 4.

Step 4.:

If the upper bound is better than the lowest upper bound obtained so far, let l←0; otherwise, let l←l+1 and modify Lagrangian multipliers using the subgradient optimization method.

Step 5.:

If l is a multiple of 10, halve the value of π _k . If k is a multiple of 10, go to step 6; otherwise, go to step 2.

Step 6.:

Find a feasible solution using procedure 1. If (UB–LB)/LB<ε, where LB is the solution values of the best feasible solution found so far and UB is the smallest upper bound obtained so far, stop; otherwise, go to step 2.

4 Computational experiments

To evaluate the performance of the suggested heuristic algorithm, computational experiments were performed on a number of randomly generated instances and instances of a real situation of two provinces in Korea. The facility location problems associated with these instances were solved by CPLEX 10.0, a commercial software package for integer programming problems, as well as the heuristic algorithm suggested in this paper, which was coded in C++. We set the values of the parameters for the stopping condition of the Lagrangian relaxation heuristic as K=500 and π ^T=0.001, after tests on a number of candidate values (detailed results of these tests are not given here). Computational experiments were performed on a personal computer with an Intel Dual Core processor operating at 3.2 GHz clock speed and 2 GB RAM.

For the tests, we randomly generated 108 instances, one instance for each of all combinations of three levels (100, 200, and 400) for the number of patient groups (|J|), three levels (0.5, 1, and 2) for the weight of low-income patients relative to high-income patients (w), two levels ($1200/\sqrt{|J|}$ and $1600/\sqrt{|J|}$ ) for the reachable distance (D), two levels (80|J| and 120|J|) for the total budget (B), and three levels (0 %, 5 % and 10 %) for the ratio of the number of existing private facilities to the number of patient groups (|T|/|J|). The number of existing public facilities, |S|, was set to the integer closest to |T|/2.

These parameter values were set in a way that the resulting instances reflect the current situation in Korea and the healthcare service plan which was announced in ‘Vision 2030’ by Korean government. Note that there are over 100 districts (patient groups) in a metropolitan area and over 250 districts in total in Korea. By varying reachable distance (D), weight (w) and total budget (B), one can consider various scenarios, which can help the healthcare services authorities to determine the operational policy of the public healthcare service system. Other data were generated as follows. Here, U(x,y) and DU(x,y) denote the uniform distribution with range (x,y) and the discrete uniform distribution with range [x,y], respectively.

• (1) The x-coordinate and the y-coordinate of the location of each patient group were independently generated from U(0,1000).

• (2) The number of low-income patients in each patient group was generated from DU(50,100).

• (3) The number of high-income patients in each patient group was generated from DU(100,200).

• (4) The capacity of facility (b _j ) at each candidate location was generated from DU(300,700).

• (5) The establishment cost of a facility at each candidate location (a _j ) was set to c ^f+c ^v⋅b _j , where c ^f and c ^v were generated from DU(200,400) and U(1,3), respectively.

• (6) The preference of patient group i for the facility at location j(p _ij ) was set to p ^f+p ^v/d _ij , where d _ij is the distance between i and j, and p ^f and p ^v were generated from U(0,10) and U(500,1000), respectively.

To avoid excessive computation time for the test, we set the upper limit of the CPU time for each problem instance to 3 hours. In fact, we set the upper limits to longer times (e.g., 72, 48, 24, 12, 6 hours) on a number of instances, but found the solutions with such longer time limits were the same as those with 3-hour limit. We evaluate the performance of the heuristic algorithm by comparing the solutions with optimal solutions or upper bounds and by comparing CPU times required for the heuristic algorithm and CPLEX. In cases in which optimal solutions were found with CPLEX, solutions obtained from the suggested heuristic were compared with the optimal solutions. In cases where optimal solutions were not found, heuristic solutions were compared with upper bounds obtained from the CPLEX through LP relaxation of [P]. Note that CPLEX provides upper bounds in these cases. In the tests on the instances with 400 patient groups, CPLEX could not find feasible solutions, due to excessive memory requirement.

Table 1 shows results of the tests on problem instances with 100 patient groups. As can be seen from the table, a majority of the instances could not be solved to the optimality by CPLEX within the time limit of 3 hours. In these cases, the table gives the solution values of the best solutions obtained by CPLEX within the time limit. The average percentage gap of the heuristic solutions from the optimal solutions (that were obtained from CPLEX) was 0.73 %, and the heuristic algorithm gave solutions with gaps of less than 1 % in 31 problems out of 36. All the 100-patient group problems were solved within 25 seconds by the heuristic algorithm, while 22 problem instances out of 36 were not solved to the optimality by CPLEX within 3 hours. Both methods, the heuristic algorithm and CPLEX, required longer CPU time in cases where the total budget is larger. Especially, optimal solutions were not found by CPLEX in most cases where the total budget is large or there are no existing facilities. This may be because there are more alternatives for the establishment of facilities that need to be considered in those cases.

Table 1 Results of tests on the 100-patient group problems

Similar results were obtained from the tests on the problem instances with 200 patient groups, as shown in Table 2. In these tests, a feasible solution could not be found by CPLEX in problems in which there are no existing facilities, due to excessive memory requirement. The average percentage gap was 1.28 % in problems in which optimal solutions were obtained from CPLEX, and in 30 problems out of 36, the heuristic algorithm gave solutions with gaps of less than 2 %. The average gap from upper bounds was 1.87 % (with the maximum of 3.09 %) in problems in which solutions were not found by CPLEX. The heuristic algorithm gave solutions within 90 seconds for all the problem instances, while most of them could not be solved to the optimality by CPLEX within the time limit of 3 hours. As in the previous test, both methods required longer CPU time in cases in which the total budget is larger.

Table 2 Results of tests on the 200-patient group problems

Table 3 shows results of the tests on problem instances with 400 patient groups. (Note that real healthcare facility problems in Korea are of this size.) CPLEX could not find feasible solutions for these instances, due to excessive memory requirement. The average percentage gap from the upper bounds was 1.22 % and the maximum percentage gap was 2.03 %. The heuristic algorithm gave solutions with gaps of less than 1 % in 10 problems out of 36, and gave solutions with gaps of more than 2 % in only 2 problems. All the problem instances with 400 patient groups were solved within 350 seconds by the heuristic algorithm and the average CPU time was 208 seconds. As in the previous two tests, the heuristic algorithm required longer CPU time in cases in which there are more patient groups and less existing facilities.

Table 3 Results of tests on the 400-patient group problems

To see which factors have impacts on the percentage gap, we performed analysis of variance and give results in Table 4. As can be seen from the table, the percentage gap was affected by the number of patient groups (|J|) and the reachable distance (D). That is, the percentage gap is smaller when there are less patient groups and the reachable distance is longer. This may be because the procedure for obtaining a feasible solution works well in those cases. On the other hand, the percentage gap was not much affected by the total budget (B) and the weight of low-income patients relative to high-income patients (w).

Table 4 Results of the analysis of variance (impact on percentage gap)

In addition, we show the effect of the weight of the low-income patients with respect to high-income patients (w) and the reachable distance of low-income patients (D) on the percentages of low-income and high-income patients served by the public facilities and the number of newly established facilities. Note that when the government plans to establish new public facilities, it generally considers not only the number of facilities to be established but also the service levels of public facilities. Table 5 shows the results. The ratio (or percentage) of the low-income patients served by the public facilities to all low-income patients was affected by the two factors, w and D, more than the ratio of the high-income patients served by the public facilities and the number of newly established facilities. The weight, w, has significant impact on the percentage of the low-income patients as well as the percentage high-income patients served by the public facilities, while the reachable distance, D, does not.

Table 5 Results of tests on the effect of D and w

In real situations, the government can determine their policy by varying scenarios with various value for the parameters such as the weight of the low-income patients with respect to high-income patients (w) and the reachable distance of low-income patients (D), and make a decision on the locations of new public facilities by considering results (the percentages of the two types of patients public facilities are to serve) of several candidate values for the parameters. Note that the weight (w) can also be determined by considering tradeoffs between the need of low-income patients for healthcare services and the profit of the facilities that can be obtained from high-income patients.

Finally, we give test results on instances of a real case in Korea, the case of North and South Chungcheong Provinces, there are 33 patient groups, each representing a district. Figure 1 shows the map of these two provinces, in which candidate locations for the facilities are marked with bold dots. The dots also represent demand points of the districts. The locations of the existing private facilities and existing public facilities are marked with triangles and rectangles, respectively. Other parameters are generated with the same method as that for parameters of randomly generated problem instances.

Fig. 1

Map of North and South Chungcheong Provinces, Korea

Results of the test are given in Table 6, which shows that CPU times required for the suggested heuristic algorithm and CPLEX as well as those required for obtaining optimal solutions and heuristic solutions. As it can be seen from the table, the heuristic algorithm required shorter CPU time than CPLEX in all 12 cases. The heuristic algorithm required less than 13 seconds for an instance. The average percentage gap of the heuristic solutions from the optimal solutions was 0.19 %. The solutions obtained from the heuristic algorithm were optimal in 6 problems out of 12 and the heuristic algorithm gave solutions with gaps of less than 0.5 % in all instances.

Table 6 Results of tests on the 33-patient group problems

5 Conclusions

In this study, we considered a problem of determining locations of new public healthcare facilities and allocating potential patients to the public facilities. An integer programming model is presented for the problem. To obtain a near optimal solution in a reasonable amount of computation time, we developed a heuristic algorithm based on Lagrangian relaxation and subgradient optimization method. For evaluation of the performance, the algorithm was compared with a general-purpose commercial solver for integer programs on a number of problem instances. Results of the computational experiments showed that the heuristic algorithm gave reasonably good solutions in much shorter time than the general-purpose solver, by which even a feasible solution could not be obtained for large-sized problems.

The model and algorithm considered in this paper can be applied to the decision making process of the government or public healthcare service authorities. When new public healthcare facilities are to be located or established, near-optimal solutions in various parameters (scenarios) are needed before all parameters are finally fixed. In these cases, the suggested algorithm may be effectively used by the healthcare authorities, who want to know in short time that how many low-income and high-income patients can be served by public healthcare facilities within fixed budget and possible outcomes of their decisions on the locations of public facilities in each of possible scenarios.

This research can be extended in several ways. For example, one can consider a case in which different types of patients, such as low-income, middle-income and high-income patients, have different preferences and different reachable distances. Also, one may need to consider a case in which there is a hierarchical relationship between different types of facilities, that is, one type of facility (health centers) provides basic services and another type of facility (general hospitals) provides advanced as well as basic services. In addition, it may be necessary to consider a problem of determining locations of public facilities with the objective of minimizing the establishment cost for public facilities while satisfying the desired service rate or serving a required number of customers.