In most developed and developing countries, governments deploy various types of systems to provide public health-care services. Especially for a society facing the aging population, the role of public health-care services by the government becomes very important. One such example is homecare services. For aged citizens with limited mobility, going to a hospital can be a very difficult task, and having health-care professionals visit their home to provide necessary care is much more desirable. In designing a system for homecare service, the central question is to determine the number and locations of care facilities to establish-e.g., homecare service centers and hospitals-when these facilities provide different service coverage and incur different construction cost.

In this paper, we consider a public health-care system with two types of facilities: health centers for homecare services and public hospitals for regular hospital services as well as homecare services. In particular, we focus on a location problem for both types of public health-care facilities. Since it is a public health-care system, cost to patients for the services received depends on their income levels in the system, that is, the charges for the same service may be different for patients with different income levels. We also take into account the fact that there already exist a number of private hospitals. We develop solution methods for solving such healthcare systems design problems common to the developed and developing countries. The main contribution of this study is to deal with and present a viable solution method for a real-world problem that must be solved by the (local) governments to maximize the utility of the budget invested on public health-care services.

In the problem considered in this study, patients, who need health-care services, are geographically scattered throughout the country. The two types of public health-care facilities, public hospitals and health centers, provide two types of health-care services, hospital services (for inpatients and outpatients) and homecare services. As part of homecare services, nurses visit patients at their home to provide necessary service on site. Public hospitals provide both hospital services and homecare services, while health centers provide only homecare services. For a public hospital, its capacity for hospital services, i.e., the number of bed, is limited. For a health center, there is no specific capacity limit because the number of nurses for homecare services is assumed to be sufficient.

As part of social security services, these public healthcare facilities offer health-care services, including hospital and homecare services, to low-income patients for free or at a significantly reduced cost. High-income and middle-income patients are allowed to use the public facilities for hospital services, but at standard cost. Note that the standard cost for hospital services at a public hospital is lower than the cost at a private hospital. Due to the government policy, high- and middle-income patients are not eligible for health-care services provided by a health center; they are required to seek homecare services from private hospitals offering the service. Lowincome patients are to be assigned to a public facility within a pre-specified distance, which is determined according to the government policy. In the remainder of this paper, we refer to high- and middle-income patients (people) as high-income patients (people) for simplicity. Also, patients needing hospital services are called in/ out-patients and patients needing homecare services are called homecare patients.

This paper discusses the problem of determining locations for public health-care facilities and allocating patients to the public facilities with the objective of minimizing the total construction cost. Types of facilities included in the problem are public hospitals, health centers, and private hospitals. Table 1 summarizes the services provided by each of the facilities and the population they serve. We do not consider homecare services provided by private hospitals in this study.

We assume that there already exist a number of public hospitals, health centers as well as private hospitals. There is some degree of competition among private hospitals and public hospitals, since high-income patients for hospital services can choose to go to their preferred facilities (among private hospitals and public hospitals). Understandably, public hospitals wish to serve as many high-income patients as possible within their capacities as high-income patients pay standard costs, thereby contributing to their revenue. In addition, when the government makes the decision on the locations of new public hospitals and health centers, it has a pre-set target in terms of the percentage of patients served by public hospitals (The target set by the Korean government is 30%. In 2008, about 15% of the both high-income patients and low-income patients were served by public hospitals, and the rest, about 85% of the patients, were served by private hospitals).

There are a large number of research articles on facility location problems describing a variety of applications. Surveys on such research are given in Hale and Moberg (2003), ReVelle and Eiselt (2005), and Daskin (2008). Studies on facility location problems may be classified according to the objectives used in the problems. Problems with the objective of minimizing the total system cost while satisfying demands are modeled as p-median problems in Lorena and Senne (2004), Fathali and Kakhki (2006), Choi and Lee (2007), Dominguez and Munoz (2008), and Schobel et al. (2009). Problems with the objective of maximizing the demand covered by a given number of facilities are modeled as set covering problems in Hong and Lee (2004), Weng et al. (2006), Berman et al. (2007) and ReVelle et al. (2008).

A number of researchers have considered facility location problems in health care systems, as reviewed by Rahman and Smith (2000) and Daskin and Dean (2004). Prior research works in the health-care domain include those for: the emergency medical service facilities by Adenso-Diaz and Rodriguez (1997), and Jia et al. (2007); preventive care facilities by Verter and Lapierre (2002); healthcare facilities for patients suffering a diabetic coma by Pacheco and Casado (2005) and Pacheco et al. (2008); healthcare facilities for seasonally moving populations by Ndiaye and Alfares (2008); long-term care facilities by Kim and Kim (2010); specialized health-care services such as traumatic brain injury treatment by Syam and Cote (2010), and public healthcare facilities under competition with private hospitals by Kim and Kim (2009).

In relation to this research, location problems in which there are multiple types of facilities have also been studied. Zhang (2006), Lu and Bostel (2007), Wang et al. (2008) and Costa et al. (2011) consider two-level facility location problems in which lower-level facilities supply products to higher-level facilities. In another variation, Galvao et al. (2002), Jayaraman et al. (2003), Barreto et al. (2007), Smith et al. (2009), and Obreque et al. (2010) address hierarchical location problems in which higher level facilities provide both higher level services and lower level services, while lower-level facilities provide only lower-level services.

Though various facility location problems have been dealt with in a number of studies, there is no research that dealt with a facility location problem of two types of public health-care facilities under the presence of a competition between the public and private hospitals. We develop a new mathematical formulation, and propose two types of heuristics based on simple optimization techniques. In the first type, locations of new public hospitals and health centers are determined based on the computed priorities of the candidate locations. In the second type, an approximation is used, and locations of the facilities are determined based on the information obtained from the solution of the approximated problem.

The remainder of this paper is organized as follows. In the next section, we describe the problem considered here by stating assumptions used in this study, and present a mathematical formulation for the problem. In section 3, we discuss the two types of heuristics developed for this problem. Performance of the algorithms is tested on a number of randomly generated problem instances, and the results are reported in section 4. Section 5 concludes the paper with a short summary and discussion on possible extensions.

This paper assumes two types of public health-care facilities, public hospitals and health centers, providing hospital services and/or homecare services. In the problem considered here, we determine locations for the public health-care facilities and allocate low-income in/outpatients to the public hospitals with the objective of minimizing the total construction cost. We consider decisions regarding the locations of the health centers, but do not consider decisions regarding the allocation of low-income homecare patients to the health centers, since the capacity of each public health-care facility for those patients are assumed to be unlimited. Thus, it is enough to ensure that there is a public health-care facility within a pre-specified distance, or reachable distance, from the low-income homecare patients.

The following assumptions are made in this research.

1) There are public hospitals, health centers and private hospitals 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 location of the region. Patients in a patient group have the same level of income and have the same preference for health-care facilities.

3) Public hospitals provide both hospital services and homecare services, while health centers provide only homecare services.

4) High-income in/out-patients who need hospital services, use their most favorite (public or private) hospitals.

5) The relative preference for the public hospital or private hospital at each location is known (They depend on the distance to the facilities, cost, and quality of the services).

6) Low-income patients can be assigned to any public facility within a pre-specified distance (reachable distance) without consideration of their preferences.

7) At least a given fraction of in/out-patients should be served by public hospitals, while all (low-income) homecare patients should be served by the public health-care facilities, i.e., public hospitals and health centers.

8) The capacity (number of sickbeds) of each (existing or candidate) public hospital is given, and the construction cost of a public hospital or a health center at each candidate location is known.

9) The capacity for homecare services of a public healthcare facility is not considered, because nurses visit homecare patients, and it is assumed that there are enough nurses available for the services or enough nurses can be assigned to a public health-care facility.

10) At any location, at most one of the three types of facilities, i.e., public hospitals, private hospitals, and health centers, can be established including the currently existing one, if any. Currently, there is no location at which there are two or more facilities.

For a clearer description of the problem considered in this paper, we give a mathematical formulation for the problem. Note that allocation of low-income patients to health-care facilities is closely related with the set cover problem. However, in the problem considered in this study, preference of high-income in/out-patients should be considered when the patients are allocated to the facilities. First, we list the notation used in the formulation (and throughout the paper).

I set of patient groups

J set of facility locations (I and J are identical by assumption 8)

i index for patient groups (i ∈ I)

j, l indices for facility locations ( j, l ∈ J)

F_i number of high-income in/out-patients in patient group i

G_i number of low-income in/out-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) upper limit of the distance between a lowincome in/out-patient and the public hospital that the patient can use

D₂ (given) upper limit of the distance between a homecare patient and the public hospital or health center that is to serve the patient

l_ij = 1 if d_ij ≤ D₁, and 0 otherwise, that is, the low-income in/out-patients at patient group i can be assigned to the public hospital at location j if l_ij = 1

m_ij = 1 if d_ij ≤ D₂, and 0 otherwise, that is, the homecare patients at patient group i can be assigned to the public facility at location j if m_ij = 1 σminimum required (target) ratio of the number of in/out-patients served by public hospitals to the number of all in/out-patients

α_j cost of establishing a public hospital at candidate location j

β_j cost of establishing a health center at candidate location j ( β _j < α _j)

C_j capacity of a (candidate or existing) public hospital at location j

p_j = 1 if there is an existing public hospital at location j, and 0 otherwise

q_j= 1 if there is an existing private hospital at location j, and 0 otherwise

r_j = 1 if there is an existing health center at location j, and 0 otherwise

P ={j | p_j = 1}, i.e., the set of locations where there already are public hospitals

Q ={j | q_j = 1}, i.e., the set of locations where there already are private hospitals

R ={j | r_j = 1}, i.e., the set of locations where there already are health centers

w_j relative preference for the private hospital compared to that for a public hospital at location j

h_ij preference of in/out-patients in patient group i for the hospital at location j, note that if there is an existing private hospital at location j (q_j = 1), h_ij is given as w_j / d_ij; otherwise (q_j = 0), h_ij is given as 1/ d_ij

x_ij binary decision variable that is equal to 1 if highincome in/out-patients at patient group i are to use the public hospital at location j (if the preference for the public hospital at location j is greater than that of any other hospital, existing or to be established), and 0 otherwise

y_ij binary decision variable that is equal to 1 if lowincome in/out-patients at patient group i are to be served by the public hospital at location j, and 0 otherwise

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

z²_j binary decision variable that is equal to 1 if a new health center is to be established at location j, and 0 otherwise

M a large number (to be used in the formulation)

An integer programming formulation for the problem is given below.

The objective is to minimize the total construction cost of public hospitals and health centers. Constraint sets (2) and (3) ensure that in/out-patients of each patient group are allocated to at most one public hospital, and constraint set (4) restricts allocations to be made only to public hospitals established (i.e., those that already exist) or to be established. At each location, at most one health-care facility, either public or private, can be established including the currently existing one by constraint set (5), and constraint set (6) ensures that the number of patients served by a public hospital cannot exceed its capacity. In addition, constraint set (7) ensures that high-income in/out-patients in a patient group are served by a public hospital, if their most favorite hospital is the public hospital (already established or to be established), while constraint set (8) ensures that lowincome in/out-patients are served by public hospitals within the reachable distance. Constraint set (9) lets all homecare patients (patient groups) be covered by public hospitals or health centers established or to be established. Also, constraint (10) ensures that public hospitals established or to be established must serve the minimum required number of in/out-patients.

Since solutions for (the integer programs of) the problems of practical sizes cannot be obtained by a commercial software package for integer programs due to excessive memory requirement, we developed heuristics in this study. Note that a special case of the problem, the set covering problem, is proven to be NP-complete (Garey and Johnson, 1979). We present two types of algorithms. The first type employs a method based on priority rules, while in the second type of algorithms, an approximate model is used in which decision variables for allocation are not considered. In the second approach, locations of new public hospitals and health centers are determined for an initial solution based on the solution of the approximated problem, and then the solution (locations of the public facilities) is modified in a way that constraints related to the allocation are satisfied.

Two priority rule-based heuristics are developed; a health center first heuristic and a public hospital first heuristic. Both algorithms consist of two phases, one to generate an initial solution (facility locations) and the other to improve the solution. In the first phase, we obtain an initial solution by using priority rules. We select locations of the facilities one by one by selecting a location with the highest priority among candidate locations available at the moment during the solution procedure. In the second phase, we improve the solution obtained in the first phase.

In the following, we give detailed descriptions of the heuristics. We use the following notation in the descriptions, in addition to the notation given above.

Tj number of hospital-service patients who can be additionally served by the (new) public hospital at candidate location j

Vj number of homecare-service patient groups that can be additionally covered by the (new) public hospital at candidate location j

Wj number of homecare-service patient groups that can be additionally covered by the (new) health center at candidate location j

3.1.1 Health center first heuristic (HCF)

The heuristic consists of two phases: generating an initial feasible solution and improving the solution. In the first phase, new health centers are selected (to be established) one by one until all patient groups can be provided with homecare services. The selection is done according to priorities of the candidate locations for the health centers. That is, at each time, we select a candidate location with the highest priority among candidates available at the moment. Priorities of the candidates are computed as W_j/β_j (for the meaning of the symbols, refer to the notation given earlier).

When the selection procedure for homecare services is completed, i.e., when selected health centers cover all patient groups, locations of public hospitals are selected for hospital services. Since public hospitals provide homecare services as well as hospital services, health centers can be replaced with public hospitals for homecare services. Selection of locations for the public hospitals is done using another priority rule. That is, among the locations at which health centers are to be established, a location with the largest value of T_j/(α_j ? β_j) is selected for the location of a new hospital instead of a new health center. Note that this priority function denotes the ratio of the number of patients who can be additionally served by a new public hospital to the difference between the construction costs of a public hospital and a health center at location j. This process of substitution of a health center with a public hospital including re-allocation of patients to the facilities is repeated until the minimum required number of in/out-patients can be served by public hospitals.

In the second phase, the solution obtained in the first phase is improved with two methods: cancellation and replacement. First, starting from the location of a public facility that requires the maximum construction cost, we check whether the selection (for establishment) of a facility can be canceled without violating constraints, that is, if demands/requirements for the services can be satisfied by other selected facilities. If possible, the selection is canceled. This cancellation procedure is repeated until there is no more selected location to be checked. Then, starting from the location of a public facility that requires the maximum construction cost, we check whether each of the currently selected locations can be replaced with a candidate location (that has not been selected) where a public facility can be established with a lower cost while still satisfying the demands.

The procedure of this heuristic can be summarized as follows.

Procedure 1: (HCF)

(Phase 1)

Step 1: If homecare services for all patient groups are covered by existing health centers and health centers to be established at selected locations, go to step 3. Otherwise, go to step 2.

Step 2: Compute priorities of candidate locations for health centers. Select a location with the highest priority for a health center, and go to step 1.

Step 3: If the number of in/out-patients who are served by existing public hospitals and public hospitals to be established at selected locations exceeds the minimum required number of patients, go to step 5. Otherwise, go to step 4.

Step 4: Compute priorities of candidate locations for public hospitals. At the candidate location with the highest priority, substitute a health center (selected to be established) with a new public hospital, i.e., select the location for a new public hospital instead of a health center, and go to step 3.

(Phase 2)

Step 5: (cancellation) In a non-increasing order of construction costs among the currently selected locations for public facilities, check if the demands/ requirements can be satisfied without the public facility at each selected location. If so, cancel the selection of the location for establishment of a public facility (This cancellation step is repeated until there is no more selected location to be considered).

Step 6: (replacement) In a non-increasing order of construction costs among the currently selected locations for public facilities, check if each location can be replaced with a candidate location that has not been selected and requires lower construction cost while satisfying the demands/ requirements. If there is one, replace the currently selected location with this candidate location. If there are two or more such candidate locations, the one requiring the lowest construction cost is selected for replacement (This replacement step is repeated until there is no more selected location to be considered).

3.1.2 Public hospital first heuristic (PHF)

This heuristic is composed of two phases as well. In the first phase, we select locations for public hospitals given the demands for hospital services, and then select locations for health centers to satisfy demand for homecare services that cannot be satisfied by existing public hospitals or public hospitals to be established. In the second phase, the solution is improved by cancellation and replacement procedures as in HCF.

In the first phase, we first select locations for public hospitals in a way that the minimum required number of in/out-patients can be served by public hospitals. At each iteration, among available candidate locations, a location with the largest value of T_j V_j /α_j is selected. As can be seen in this priority function, we select the location for a new public hospital based on the number of patients who can be additionally served, the number of patient groups that are to be additionally covered by the new public hospital, and the construction cost. Note that when this selection process is completed, at least the minimum required number of in/out-patients can be served by public hospitals. Then, we select locations for health centers to cover patient groups that are not covered by the public hospitals. For the selection, we set priorities of candidate locations for health centers as W_j/β_j, i.e., the ratio of the number of patient groups that are to be additionally covered by the health center to the construction cost. A location with the largest priority value is selected.

The solution obtained in the first phase is improved in the second phase with two methods: cancellation and replacement. These improvement steps are identical to those of HCF. The procedure of Phase 1 of PHF can be summarized as follows.

Procedure 2: (PHF)

(Phase 1)

Step 1: If the number of in/out-patients who are served by existing public hospitals and public hospitals to be established at selected locations is greater than or equal to the minimum required number of patients, go to step 3. Otherwise, go to step 2.

Step 2: Compute priorities of candidate locations for public hospitals. Select a location with the highest priority for a public hospital, and go to step 1.

Step 3: If homecare services for all patient groups are covered by existing facilities and facilities to be established at selected locations, go to step 5. Otherwise, go to step 4.

Step 4: Compute priorities of candidate locations for health centers. Select a location with the highest priority for a health center, and go to step 3.

(Phase 2) identical to Phase 2 of HCF

This heuristic consists of two phases, one for obtaining an initial solution and the other for modifying the solution. In the algorithm, we use an approximated (simplified) version of the mathematical formulation of the problem in which decision variables for allocation (and associated constraints) are not included. This approximate formulation is used to obtain an initial solution. Since this initial solution may not be feasible for the original problem, we modify the initial solution in the second phase if needed. In the following, we describe the two phases of the algorithm in detail.

3.2.1 Phase 1: Obtaining an initial solution

The heuristic consists of two phases: generating an initial feasible solution and improving the solution. In the first phase, new health centers are selected (to be established) one by one until all patient groups can be provided with homecare services. The selection is done according to priorities of the candidate locations for the health centers. That is, at each time, we select a candidate location with the highest priority among candidates available at the moment. Priorities of the candidates are computed as W_j/β_j (for the meaning of the symbols, refer to the notation given earlier). An approximate formulation is used to obtain an initial solution, i.e., to select locations of the facilities. In the approximate formulation, which is given below, decision variables for allocation, x_ij and y_ij, as well as constraints (2), (3), (4), (8), (11), and (12) are disregarded, and constraint sets (6), (7), and (10) of the original problem [P] are substituted with a new constraint, (15). In the formulation, S_j denotes the maximum possible number of high- and lowincome in/out-patients who can be served by the public hospital at candidate location

where K_j is the set of patient groups of which the high-income in/out-patients may possibly use a public hospital at location j, i.e.,

Note that K_j can be defined from the (given) preferences of in/out-patients of patient groups for the private and public hospitals.

[AP] Minimize

subject to

Constraints (6), (7), and (10), which were used for the allocation of patients to facilities in [P], are substituted with (15), which ensures that the number of patients to be served by the public hospitals is greater than or equal to the minimum required number of in/outpatients. An optimal solution for [AP] can be obtained easily, or within a reasonably short time, with a commercial software package for integer and linear programs, such as CPLEX. Note that an optimal solution of [AP] can also be used as a lower bound on the solution of the original problem [P].

3.2.2 Phase 2: Modification

When locations of public facilities as well as private hospitals are given, patients can be assigned to the facilities easily using the information on the locations of facilities and patient groups and preferences of the patients. In other words, the values of x_ij’s and y_ij’s, i.e., the allocation of high-income and low-income in/outpatients, respectively, at patient group i to the public hospital at location j, can be determined from the values of z¹_j and z²_j i.e., the decisions on the establishment of new public hospitals and new health centers, respectively, are obtained as a solution of [AP]. If all constraints are satisfied by the solution (for the original problem) obtained in this way, the procedure is terminated. Otherwise, the solution obtained in the first phase is modified with two methods: replacement and addition of the locations for the facilities. First, we replace the location of a public facility that is selected in the current solution with a location that is not selected in a way that the total construction cost is increased least. This replacement procedure is repeated until all the constraints are satisfied. If the constraints are not satisfied after the replacement procedure, we additionally select locations for public hospitals and/or health centers with the minimum construction cost one by one until the constraints are satisfied.

The procedure of this algorithm can be summarized as follows.

Procedure 3: (approximation-based heuristic, ABH)

(Phase 1)

Step 1: Obtain an optimal solution of [AP] with an integer programming solver.

Step 2: Based on the values for z1j’s and z2j’ s in the optimal solution of [AP], assign the high-income in/out-patients to their favorite hospitals and assign low-income in/out-patients to public hospitals within a reachable distance. If there are two or more public hospitals within the reachable distance, the low-income in/out-patients are assigned to a public hospital with the maximum remaining capacity.

Step 3: If the number of in/out-patients served by the public hospitals is greater than or equal to the minimum required number, terminate. Otherwise, go to step 4.

(Phase 2) identical to Phase 2 of HCF

Step 4: In a non-increasing order of construction costs for the currently selected locations, check if each location can be replaced with a candidate location that has not been selected while satisfying all the constraints. If there is one, replace the currently selected location with this candidate location. If there are two or more such candidate locations, the one requiring the lowest construction cost is selected for replacement (This replacement step is repeated until there is no more selected location to be considered).

Step 5: If the constraints related to the demands for the services are satisfied with the current solution, stop. Otherwise, select additionally a public hospital or health center with the minimum construction cost one at a time, until all the constraints are satisfied. Stop.

For evaluation of the performance of the suggested heuristics, computational experiments were performed on a number of problem instances that were randomly generated in a way that the resulting instances reflect real situations in Korea relatively closely (Note that there are about 400 basic districts in the capital city and 1,200 districts throughout the country in Korea).

Wegenerated 96 problem instances, one instance for each of all combinations of: three levels (400, 800, and 1,200) for |I|, the number of patient groups; two levels

for D₁, the reachable distance between low-income in/out-patients and a public hospital; two levels

for D₂, the reachable distance between homecare patients and a public facility; two levels (0.3 and 0.5) for σ, the ratio of the minimum required number of in/out-patients served by the public hospitals to all in/out-patients; two levels (5% and 10%) for |P|/|I|, the ratio of the number of existing public hospitals to the number of patient groups; and two levels (10% and 20%) for |Q|/|I|, the ratio of the number of existing private hospitals to the number of patient groups.

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 the Korean government. 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 high-income in/out-patients (Fi) in each patient group was generated from DU (100, 200).

3) The number of low-income in/out-patients (Gi) in each patient group was generated from DU(50, 100).

4) The relative preference for a private hospital compared to that for a public hospital (Wj) at each loca-

tion was generated from DU(1, 3).

5) The capacity of the hospital (Ci) at each candidate location was generated from DU (300, 700).

6) The construction cost of a public hospital at each candidate location (αj) was set to cf + cvCj, where cf and cv were generated from DU (200, 400) and U(1, 3), respectively.

7) The construction cost of a health center at each candidate location (βj) was generated from DU (100, 200).

The heuristics were coded in C++ , and 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. Since there is no algorithm specifically designed for the problem considered in this study, the suggested algorithms were compared with CPLEX 10.0, a commercial software package for integer and linear programs. For problem instances of practical sizes, i.e., those with 400, 800 and

1,200 patient groups, CPLEX could not even find feasible solutions due to excessive memory requirement. Hence, lower bounds were obtained from the approximate formulation, [AP]. Performance of the algorithms is shown with the percentage gaps of the heuristic solutions from the lower bounds. Throughout the paper, the health center first heuristic, the public hospital first heuristic, and the approximation-based heuristic are denoted with HCF, PHF, and ABH, respectively.

Table 2 shows the results of the tests on problem instances with 400 patient groups. As can be seen from the table, ABH worked best. It gave the best solutions in the majority of the instances. The average percentage gaps (from lower bounds) of HCF, PHF, and ABH were 3.22%, 4.76%, and 1.71%, respectively. ABH gave solutions with gaps larger than 3% in only 6 instances out of

32, but it required a longer CPU time than HCF and PHF. HCF and PHF gave solutions within 2 seconds for each problem instance, while ABH gave solutions in 30 seconds. Although an integer programming problem should be solved for an initial solution in ABH, it did not require an excessively long time. This may be because the number of decision variables is reduced significantly by the approximation, and the resulting location problem, without variables related to the allocation of patients to facilities, can be solved in a short time.

Similar results were obtained from the tests on the problem instances with 800 patient groups and 1,200 patient groups, as shown in Tables 3 and 4, respectively. Although the average percentage gap of the heuristic solutions from the lower bounds increased slightly as the problem sizes increase, the relative performance of

the three heuristics was the same. That is, in terms of the average percentage gaps, ABH worked best, followed by HCF. Also, ABH gave solutions with gaps larger than 3% in only 10 instances out of 64 instances of these sizes. ABH worked better, in terms of the percentage gap, in cases where the number of existing private hospitals (|Q|) is larger. This may be because the initial solutions, which are obtained from the approximated formulation, were often feasible in these cases. ABH required 2 and 4 minutes on average to solve each of the problem instances with 800 and 1,200 patient groups, respectively.

To evaluate the performance of the heuristics in terms of the gaps of the heuristic solutions from optimal solutions, we further tested the algorithms on smallsized problem instances, those with 100 patient groups. For this test, we generated 32 instances with the same method as the one used for generating problem instances of practical sizes. Optimal solutions were obtained with CPLEX applied to the complete formulation, [P]. The results of the tests are given in Table 5, which shows optimal solution values, heuristic solution values and percentage gaps of the heuristic solutions from optimal solutions as well as the CPU time needed for CPLEX. Note that the heuristics required less than 5 seconds for each problem instance. All the three algorithms, especially ABH, worked relatively well. The average percenttage gap of HCF, PHF, and ABH were 2.99%, 4.66%, and 1.39%, respectively. ABH found optimal solutions in 4 instances out of 32, and gave solutions with gaps of more than 2% in only 6 instances.

Finally, in Table 6, we show the effect of the reachable distances of/to a low-income in/out-patient and homecare patient, i.e., D1 and D2, respectively, on the solution value, i.e., the total construction cost. Note that when the government plans to establish new public facilities, it usually considers the budget and the total construction cost. As can be seen from the table, the total construction cost was affected by both factors, the reachable distance to in/out patients (D1) and the reachable distance to homecare patients (D2). The total construction cost was affected more by D2 than D1. This may be because a public facility, with enough nurses for homecare services, can cover more patient groups without establishing additional facilities, while a public hospital can serve only a limited number of patients due to the limited capacity even though D1 is increased. Hence, to reduce total construction cost, one may think of an alternative of increasing the reachable distance to homecare patients, which is directly related with traveling distance of nurses. For such an alternative, labor cost or overtime cost for the nurses as well as traveling cost may be increased, and one may have to consider tradeoffs between these additional costs and the construction cost.

In this study, we considered the problem of determining locations of public health-care facilities and allocating patients to the public facilities with the objective of minimizing the total construction cost. An integer programming model is presented for the problem. To obtain a near optimal solution in a reasonable computation time, we developed two types of heuristics. The results of the computational experiments on randomly generated problem instances showed that the heuristics gave reasonably good solutions in much shorter time than a general-purpose integer and linear programming solver, by which even a feasible solution could not be obtained for large-size problems. Designed on the basis of the situations of a real-world health-care systems design problem, the solution method presented in this study may be considered a viable tool for real application.

This research can be extended in several directions. For example, one can consider a problem of determining locations of public health-care facilities with the objective of maximizing the number of (potential) patients covered by the facilities under a constraint on the budget for construction cost. Also, it may be necessary to consider problems of determining locations of the facilities and allocating nurses to patients for homecare services while considering construction costs of the facilities and travel distance of the nurses. In addition, one may need to consider cases in which the capacities of the existing public facilities can be changed, or problems involving the decision on the capacities of the facilities.