A Benders decomposition for the location-allocation and scheduling model in a healthcare system regarding robust optimization

Abstract

The hospital location and service allocation is one of the most important aspects of healthcare systems. Due to lack of studies on covering location-allocation and scheduling problems with respect to the uncertain budget, this paper develops a bi-objective hybrid model to locate hospitals and allocate machines and services scheduled. The costs of establishing facilities are assumed to be uncertain, while a robust counterpart model is employed to overcome the uncertainty. Covering the demand of each service is limited as well. Moreover, hospitals have a limited space to the specialized equipment like CT scan and MRI machines, while there is a cost constraint on hospitals and the specialized equipment. The aim of this paper is to find a near-optimal solution including the number of hospitals and the specialized equipment, the location of hospitals, the assignment of demand of each service and the specialized equipment to hospitals, the determination of allowable number of each service of hospitals, the determination of demand that should be transferred from one hospital to another (patient transfer), and schedule services. As the proposed model, minimizing the total costs and the completion time of demand simultaneously, is an NP-hard problem, it is impossible to solve its large-scale version with exact methods in a reasonable time. Thus, a hybrid algorithm including simulated annealing optimization and the Benders decomposition is employed to solve it. The CPLEX optimizer verifies the presented algorithm to solve the proposed model. The sensitivity analysis is performed to validate the proposed robust model against of uncertain situations while the Monte Carlo simulation is used to analyze the quality and the robustness of solutions under uncertain situations. The results show that the uncertainty used in the proposed model properly formulates real-world situations compared to the deterministic case. Finally, the contributions and the future research are presented.

1 Introduction

Healthcare systems have a vital role in total costs of every country’s economy. Moreover, locating hospitals with regard to allocating services is one of the main healthcare problems. Over the past few decades, the operation research approaches like the facility location problem have been used to model many healthcare problems [1]. Rahman and Smith [2] considered a location-allocation problem of the healthcare system in developing nations, while some studies [3–11] carried out several major reviews of the location problems. These problems locate facilities and allocate services to facilities. In the past few years, the location-allocation models have been employed for a wide range of problems such as healthcare, manufacturing, forestry, and logistics providing many extensions. The covering problem is one of the most important developments of the location-allocation models. Farahani et al. [10] presented a review of covering problems in logistics.

In a case study at the division of angiography and interventional radiology at the Brigham and women’s hospital in Boston, Baum et al. [12] presented a model consisting of scheduling, revenue management, and fairness to find an optimal daily scheduling of physicians regarding mixed integer optimization. In an unfavorable economic scenario, clinical pathways for patients should be clearly defined by healthcare organizations to increase the quality of care services [13]. Considering patterns in clinical pathways, Huang et al. [14] developed a probabilistic problem with occurrences in clinical pathways and treatment activities for a Chinese hospital. The emergency care plays an important role in the transportation of casualties to hospitals to save people’s life. To overcome the demand surge regarding a case study consisting of an expected earthquake in Istanbul, Salman and Gül [15] formulated a bi-objective location problem to find a near-optimal solution including the location and size of emergency service facilities in which the total cost of establishing new facilities and the total travel and waiting time of casualties over the search-and-rescue period were minimized. Regarding the strategic planning of hospital networks, Mestre et al. [16] proposed a location-allocation problem with uncertain demand for a case study based on the Portuguese National Health Service.

Many patients find it hard to receive hospital treatments due to the imbalance between demand and supply in an outpatient specialty care. Since the need for a health service should be accessible to all, one of the policies is to open outreach clinics which are closer to patients’ residences. Regarding care delivery scheme, Li et al. [17] presented an integrated multi-site care networks to find a near-optimal solution including appointment locations for patients and travel assignments for physicians in case studies of Veteran Affairs Care Networks.

Uncertainty is the most important reason not to take advantage of some formulated problems. Stochastic and fuzzy approaches are two well-known methods to overcome uncertain situations under real-world conditions, while the robust optimization (RO) has been recently used like the bloodmobile routing problems [18], hub location problems [19], and layout problem [20]. RO presents a solution including the deterministic variability to enable formulated problems to be effective against uncertainty. Gülpınar et al. [21] employed the robust optimization to solve a facility location problem in which the demand was assumed to have a normal distribution. Regarding RO in disaster relief problems, Paul and MacDonald [22] developed a stochastic facility location-allocation model in which the timing and severity of potential event were uncertain. However, Table 1 presents a comparison the proposed model with the literature.

Table 1 Comparison the proposed model with the literature

The location-allocation models, unable to be solved by exact methods, are an NP-hard problem [23]. One of the popular methods to optimize NP-hard problems is to employ meta-heuristic optimization algorithms like genetic algorithm (GA) [24], multi-objective genetic algorithm [25], imperialist competitive algorithm (ICA) [26], Tabu search [27] and path-relinking algorithm [28], hybrid Tabu search [29], particle swarm optimization (PSO) [30], harmony search algorithm (HSA) [31], non-dominated sorting genetic algorithm-II (NSGA-II) [32], simulated annealing (SA) [33], cuckoo-inspired algorithms [34], and hybrid firefly algorithm [35].

Regarding mentioned issues, this paper develops a bi-objective covering location-allocation problem with the uncertain budget, in which patient services were scheduled. There is a constraint on hospitals space to the specialized equipment like CT scan and MRI machines while covering demand of each service is limited. The aim of the proposed model is to find a near-optimal solution including (1) the number of hospitals and the specialized equipment, (2) the location of hospitals, (3) the assignment of demand of each service, and the specialized equipment to hospitals, (4) the determination of allowable number of each service of hospitals, (5) the determination of demand that should be transferred from one hospital to another (patient transfer), and (6) scheduling patient services.

The proposed model is an NP-hard problem; thus, exact methods are unable to solve its large-scale version in a reasonable time [49]. To optimize the proposed model, minimizing the total costs and the completion time of the demand (total patient services) simultaneously, this paper employs a hybrid algorithm including the SA optimization and the Benders decomposition while a robust counterpart model is employed to overcome the uncertainty about costs of establishing hospitals and buying specialized equipment. In compared with the standard SA, the provided solutions by the hybrid algorithm are compared with the lower and upper bounds presented by the CPLEX solver.

To mention the main contributions, this paper combines and develops approaches presented by these studies [50–53] so that the models presented by Feizollahi and Modarres-Yazdi [53] and Syam and Côté [51] are developed to consider the second objective minimizing the completion time of the total patient services (group scheduling). Moreover, we extend the models provided by Kim and Kim [52] and Shariff et al. [50] to uncertain budgets. In brief, the main innovations are to consider the second objective in the mathematical model, to investigate the uncertainty about budgets, to formulate an integrated model including the covering location-allocation and scheduling problems, and to employ a robust optimization and a hybrid algorithm including SA optimization and the Benders decomposition.

The remainder of this paper is organized as follows. The next section provides the mathematical model. The proposed hybrid algorithm and comparison results are presented in Sects. 3 and 4. Finally, conclusion and future research are provided in Sect. 5.

2 A bi-objective covering location-allocation and scheduling model

This section presents a bi-objective hybrid model, a mixed integer nonlinear programming, for hospital location with machines and service allocation under uncertain budget regarding scheduling patient services.

2.1 Notations and assumptions

In this paper, to locate new hospitals and allocate machines and demand to hospitals, respectively, regarding limited budget, it is assumed to be s potential locations for hospitals providing a variety of services and m locations with certain demand. Moreover, each demand consists of n different services provided by one or more hospitals in order to determine allowable number of each service of hospitals.

It is assumed to be c types of specialized equipment (machines). As there is the limited budget in real-world applications, a hospital is unable to have all types of specialized equipment such as CT scan and MRI machines. Thus, the question is which kind of and how many machines are installed in each hospital regarding the limited budget and space? Meaning that if buying four MRI machines is allowable, only four hospitals are able to have them. While a hospital does not have all types of machines, what scheduling patient services (SPS) is since it is possible to transfer a patient from a hospital to another hospital?

According to budget constraints, the costs of purchasing and installing of machines, and the fixed and variable costs of establishing hospitals are assumed to be uncertain with an ambiguous distribution. Moreover, demand is able to be assigned to one or more machines while visiting machines is not allowed more than once while hospitals have to cover demand at least L ⁱ _j percent.

In this paper, there are the following notations to formulate the proposed model.

Sets and indexes

$I,i$ :

Set and index of patient services, $i \in I;\quad i = 1, \ldots ,n$

$J,j$ :

Set and index of patient locations, $j \in J;\quad j = 1, \ldots ,m$

$L,l$ :

Set and index of hospital locations, $l \in L;\quad l = 1, \ldots ,s$

$K,k$ :

Set and index of machine types, $k \in K;\quad k = 1, \ldots ,c$

Parameters

$c_{jl}$ :

Transportation cost per unit between jth patient location and lth hospital

$m_{jl}$ :

Distance between jth patient and lth hospital

$\rho_{{ll^{\prime}\,k}}$ :

Cost per unit of transferring patient from lth hospital to $l^{\prime th}$ hospital for kth machine

$d_{j}^{i}$ :

Demand of ith patient service of jth patient location

$L_{j}^{i}$ :

Lower bound to cover demand of ith patient service of jth patient location

$A_{l}^{i}$ :

Lower bound of ith patient service for lth hospital to establish

e _l :

Fixed cost to establish lth hospital

$g_{l}^{i}$ :

Variable cost to establish lth hospital per unit of ith patient service

$r_{lk}$ :

Purchasing and installing costs of kth machine in lth hospital

B ₁ :

Maximum budget to establish lth hospital

B ₂ :

Maximum budget to purchase and install machines

$f_{{kk^{\prime}}}^{i}$ :

$\left\{ \begin{array}{ll} 1&\quad {\text{if }}k^{\prime th} {\text{machine is required after }}k{\text{th}}\;{\text{machine to provide }}i{\text{th patient service}} \\ 0&\quad{\text{otherwise}} \end{array} \right.$

$f_{k}^{i}$ :

$\left\{ \begin{array}{ll} 1&{\text{ if }}k{\text{th}}\;{\text{machine is the first machine to provide }}i{\text{th patient service}} \\ 0&{\text{ otherwise}} \end{array} \right.$

$n_{{ll^{\prime}}}$ :

Transferring time between lth hospital and $l^{\prime th}$ hospital

$t_{k}^{i}$ :

Unit processing time of ith patient service by kth machine

Decision variables

$Z_{jl}^{i}$ :

Number of ith patient service of $j^{th}$ patient location assigned to lth hospital

$W_{{ll^{\prime}\,k}}^{i}$ :

Number of ith patient service transferred from lth hospital to $l^{\prime th}$ hospital for kth machine

$Y_{lk}$ :

$\left\{ \begin{array}{ll} 1&{\text{ if }}k{\text{th machine instralled in }}l{\text{th hospital}} \\ 0&{\text{ otherwise}} \end{array} \right.$

$X_{l}$ :

$\left\{ \begin{array}{ll} 1&{\text{ if }}l{\text{th hospital is opened}} \\ 0&{\text{ otherwise}} \end{array} \right.$

$H_{i'\,lk}^{i}$ :

$\left\{ \begin{array}{ll} 1&{\text{ if }}i{\text{th patient service provided before }}i^{\prime th} {\text{ patient service by }}k{\text{th}}\;{\text{machine in }}l{\text{th}}\;{\text{hospital}} \\ 0&{\text{ otherwise}} \end{array} \right.$

$T_{lk}^{i}$ :

Completion time of $i{\text{th}}$ patient service by $k{\text{th}}$ machine in $l{\text{th}}$ hospital

Depended variables

$S_{lk}^{i}$ :

$\left\{ \begin{array}{ll} 1&{\text{ if }}i{\text{th patient service transferred to }}l{\text{th hospital for }}k{\text{th}}\;{\text{machine}} \\ 0&{\text{ otherwise}} \end{array} \right.$

$C{ \hbox{max} }_{i}$ :

Completion time of the last patient service i

2.2 The proposed mathematical model

Regarding mentioned assumptions, the proposed mixed integer nonlinear programming model is as follows.

Objectives

$$ {\text{Min}}\,{\text{Cost = }}\left( {\sum\limits_{i = 1}^{n} {\sum\limits_{l = 1}^{s} {\sum\limits_{j = 1}^{m} {\left( {c_{jl} m_{jl} Z_{jl}^{i} } \right)} } } + \sum\limits_{i = 1}^{n} {\sum\limits_{l = 1}^{s} {\sum\limits_{{l^{\prime} = 1}}^{m} {\sum\limits_{k = 1}^{c} {\left( {\rho_{{ll^{\prime } k}} \,W_{{ll^{\prime}\,k}}^{i} } \right)} } } } } \right) \quad\left( {{\text{Total}}\;{\text{Costs}}} \right) $$

(1)

$$ {\text{Min}}\,{\text{Time}} = \left( {\sum\limits_{i = 1}^{n} {\left( {C{ \hbox{max} }_{i} } \right)} } \right) \left( {{\text{Completion}}\,{\text{time}}\,{\text{of}}\,{\text{patient}}\,{\text{treatment}}} \right) $$

(2)

Subject to

$$ \sum\limits_{l = 1}^{s} {Z_{jl}^{i} } \ge d_{j}^{i} L_{j}^{i} ;\quad \forall j \in J,i \in I\quad({\text{Covering}}\,{\text{constraint}}) $$

(3)

$$ \sum\limits_{j = 1}^{m} {Z_{jl}^{i} } \ge A_{l}^{i} X_{l} ;\quad \forall l \in L,i \in I\quad({\text{Patient}}\,{\text{service}}\,{\text{constraint}}) $$

(4)

$$ \sum\limits_{k = 1}^{c} {Y_{lk} } \le cX_{l} ;\quad \forall l \in L\quad({\text{Machines}}\,{\text{constraint}}) $$

(5)

$$ \sum\limits_{i = 1}^{n} {\sum\limits_{j = 1}^{m} {Z_{jl}^{i} } } \le MX_{l} ;\quad \forall l \in L\quad({\text{Establishment}}\,{\text{constraint}}) $$

(6)

$$ \sum\limits_{i = 1}^{n} {\sum\limits_{{l^{\prime} = 1}}^{m} {W_{{ll^{\prime}k}}^{i} } } \le MY_{lk} ;\quad \forall l \in L,k \in K\quad({\text{Transference}}\,{\text{constraint}}) $$

(7)

$$ \sum\limits_{{l^{\prime} = 1}}^{s} {W_{{ll^{\prime } k}}^{i} } = \sum\limits_{i = 1}^{n} {\sum\limits_{j = 1}^{m} {f_{k}^{i} Z_{jl}^{i} } } + \sum\limits_{{l^{\prime} = 1}}^{s} {\sum\limits_{{k^{\prime} = 1}}^{c} {f_{{k^{\prime } k}}^{i} W_{{l^{\prime } lk^{\prime } }}^{i} } } ;\quad \forall i \in I,l \ne l^{\prime } ,l \in L,k \ne k^{\prime } ,k \in K $$

(8)

$$ S_{lk}^{i} \le \sum\limits_{{l^{\prime } = 1}}^{s} {W_{{l^{\prime } lk}}^{i} } \le MS_{lk}^{i} ;\quad \forall i \in I,k \in K,l \ne l^{\prime } ,l \in L $$

(9)

$$ \sum\limits_{l = 1}^{s} {e_{l} X_{l} } + \sum\limits_{i = 1}^{n} {\sum\limits_{l = 1}^{s} {\sum\limits_{j = 1}^{m} {g_{l}^{i} Z_{jl}^{i} \le B_{1} } } } \quad({\text{Budget}}\,{\text{constraint}}) $$

(10)

$$ \sum\limits_{k = 1}^{c} {\sum\limits_{l = 1}^{s} {r_{lk} Y_{lk} \le B_{2} } } \quad({\text{Budget constraint}}) $$

(11)

$$ H_{{i^{{\prime }} lk}}^{i} + H_{ilk}^{{i^{{\prime }} }} = S_{lk}^{i} S_{lk}^{{i^{\prime } }} ;\quad \forall i \ne i^{{\prime }} ,i\,\&\, i^{{\prime }} \in I,k \in K,l \in L $$

(12)

$$ \left( {T_{lk}^{{i^{\prime}}} - T_{lk}^{i} + M\left( {1 - H_{{i^{{\prime }} lk}}^{i} } \right)} \right) \ge t_{{i^{\prime } k}} \sum\limits_{{l^{\prime } = 1}}^{s} {W_{{l^{{\prime }} lk}}^{i} } ;\quad \forall i \ne i^{\prime } ,i\,\&\, i^{\prime } \in I,j \in J,l \ne l^{\prime } ,k \in K,l \in L $$

(13)

$$ T_{{l^{\prime } k^{\prime } }}^{i} - T_{lk}^{i} \ge \left( {n_{{ll^{\prime } }} + t_{{k^{\prime } }}^{i} } \right)W_{{ll^{\prime } k^{\prime } }}^{i} - M\left( {1 - f_{{kk^{\prime } }}^{i} \,S_{lk}^{i} S_{{l^{\prime } k^{\prime } }}^{i} } \right);\quad \forall i \in I,k \ne k^{\prime } ,k\,\&\, k^{\prime } \in K,l \ne l^{\prime } ,l\,\&\, l^{\prime } \in L $$

(14)

$$ C{ \hbox{max} }_{i} \ge T_{lk}^{i} - M\left( {1 - S_{lk}^{i} } \right);\quad \forall i \in I,k \in K,l \in L $$

(15)

$$ Z_{jl}^{i} ,W_{{ll^{\prime } k}}^{i} ,C{ \hbox{max} }_{i} ,T_{lk}^{i} \ge 0;Y_{lk} ,S_{lk}^{i} ,X_{l} ,H_{{i^{\prime } lk}}^{i} = 0\;{\text{or}}\;1; $$

(16)

where Eqs. (1, 2), the objective functions of the model, minimize the total costs and the completion time of the demand, simultaneously. There is the conflict between the first objective and the second objective, which means that Eq. (1) tries to minimize the patient cost for treatment while Eq. (2) seeks to reduce the completion time of the patient treatment. The second objective provides a solution including the transfer of patients from a hospital to another one leading to increase the patient’s costs. Equation (3) is the lower bound to cover demand of ith patient service of jth patient location. Regarding Eq. (4), a hospital to be established has a lower bound for ith patient service meaning that constructing lth hospital is not allowable in jth location that does not have at least $A_{l}^{i}$ patient services. The number of machines is controlled by Eq. (5). M is a big number in Eqs. (6, 7) to encourage transferring and assigning more patient services to opened hospitals. Equations (8, 9) check the number of patients transferred among hospitals. Equations (10, 11) present an upper bound to establish hospitals and purchase machines. According to the scheduling patient services problem, Eqs. (12–14) check sequencing of patients in hospitals. Equation (15) determines the completion time of the last patient service which is equal to the total time of patient treatment. Equation (16) defines the type of variables.

2.3 The proposed robust mathematical model

Over the past few years, the robust optimization (RO) has been used to overcome uncertain situations under real-world conditions in problems like the layout problem [20], the bloodmobile routing problems [18], and the hub location problems [19]. The RO provides a solution including the deterministic variability to enable the formulated problems to be effective against uncertainty [54]. Among approaches presented in the RO, this paper uses the robust methodology provided by Bertsimas and Sim [55] to provide solutions ensuring deterministic and probabilistic guarantees.

Regarding the budget constraints, the costs of purchasing and installing of machines $\left( {r_{lk} } \right)$, and the fixed and variable costs of establishing hospitals (e _l and $g_{l}^{i}$, respectively) are assumed to be uncertain with an ambiguous distribution. In the RO provided by Bertsimas and Sim [55], J _i is the set of coefficients a _ij , j ∊ J that are subject to parameter uncertainty, i.e. $\tilde{a}_{ij}$, $j \in J$ taking values according to a symmetric distribution with the mean equals to the nominal value a _ij in the interval $\left[ {a_{ij} - \hat{a}_{ij} , a_{ij} - \hat{a}_{ij} } \right]$. $\varGamma_{i}$ is a parameter taking values in the interval $\left[ {0,\left| {\,J_{i} } \right|} \right]$, adjusting the robustness against the level of conservatism of the solution. However, three uncertain parameters of the proposed model in Eqs. (10, 11) ($r_{lk}$, $e_{l}$, and $g_{l}^{i}$) are

$$ e_{l} :\left[ {\begin{array}{*{20}c} {e_{l} - \hat{e}_{l} \xi_{l}^{1} } & {e_{l} + \hat{e}_{l} \xi_{l}^{1} } \\ \end{array} } \right] $$

(17)

$$ g_{l}^{i} :\left[ {\begin{array}{*{20}c} {g_{l}^{i} - \hat{g}_{l}^{i} \xi_{l}^{i2} } & {g_{l}^{i} + \hat{g}_{l}^{i} \xi_{l}^{i2} } \\ \end{array} } \right] $$

(18)

$$ r_{lk} : \left[ {\begin{array}{*{20}c} {r_{lk} - \hat{r}_{lk} \xi_{lk}^{3} } & {r_{lk} + \hat{r}_{lk} \xi_{lk}^{3} } \\ \end{array} } \right] $$

(19)

then, the protection function $\beta_{1} \left( {x^{*} } \right)$ to the first budget constraint shown in Eq. (10) is

$$ \beta_{1} \left( {x^{*} } \right) = \hbox{max} \left( {\sum\limits_{l = 1}^{s} {X_{l} \hat{e}_{l} \xi_{l}^{1} } + \sum\limits_{j = 1}^{m} {\sum\limits_{i = 1}^{n} {\sum\limits_{l = 1}^{s} {Z_{jl}^{i} \hat{g}_{l}^{i} \xi_{l}^{i2} } } } } \right) $$

(20)

s.t,

$$ \sum\limits_{l = 1}^{s} {\xi_{l}^{1} } \le \varGamma_{1} $$

(21)

$$ \sum\limits_{l = 1}^{s} {\sum\limits_{i = 1}^{n} {\xi_{l}^{i2} \le \varGamma_{2} } } $$

(22)

$$ 0 \le \xi_{l}^{1} \le 1;\quad \forall l \in L $$

(23)

$$ 0 \le \xi_{l}^{i2} \le 1;\quad \forall l \in L,i \in I $$

(24)

As Eq. (20), a Knapsack problem, is bounded and feasible, its dual version is bounded and feasible as well. Thus,

$$ {\text{Min}} = \varGamma_{1\,} Q_{1} + \varGamma_{2} Q_{2} + \sum\limits_{l = 1}^{s} {P_{l} } + \sum\limits_{l = 1}^{s} {\sum\limits_{i = 1}^{n} {P_{l}^{i2} } } $$

(25)

s.t,

$$ Q_{1} + P_{l}^{1} \ge X_{l} \hat{e}_{l} ;\quad \forall l \in L $$

(26)

$$ Q_{2} + P_{l}^{i2} \ge \sum\limits_{j = 1}^{m} {Z_{jl}^{i} \hat{g}_{l}^{i} } ;\quad \forall l \in L,i \in I $$

(27)

$$ Q_{1} ,Q_{2} ,P_{l}^{i2} ,\;{\text{and}}\quad P_{l}^{i2} \ge 0;\quad \forall l \in L,i \in I $$

(28)

Similarly, to provide a robust optimization for the second budget constraint shown in Eq. (11), we have,

$$ {\text{Min}} = \varGamma_{3} Q_{3} + \sum\limits_{l = 1}^{s} {\sum\limits_{k = 1}^{c} {P_{lk}^{3} } } $$

(29)

s.t,

$$ Q_{3} + P_{lk}^{3} \ge Y_{lk} \hat{r}_{lk} ;\quad \forall l \in L,k \in K $$

(30)

$$ Q_{3} \quad{\text{and}}\quad P_{lk}^{3} \ge 0;\quad \forall l \in L,k \in K $$

(31)

Therefore, Eqs. (25–31) are replaced with Eqs. (10, 11) to provide a robust proposed model.

To recapitulate briefly, this section proposed a bi-objective covering location-allocation problem with the uncertain costs, in which patient services were scheduled. Covering the demand of each service and the hospitals space to the specialized equipment like CT scan and MRI machines was limited. The robust optimization is employed to overcome the uncertainty of costs. The aim of the proposed model, minimizing the total costs and the completion time of demand (total patient services) simultaneously, is to provide a near-optimal solution including (1) the number of hospitals and specialized equipment, (2) the location of hospitals, (3) the assignment of demand of each service and specialized equipment to hospitals, (4) the determination of allowable number of each service of hospitals, (5) the determination of demand that should be transferred from one hospital to another (patient transfer), and (6) scheduling patient services. The main contributions of this paper were presented in the end of Sect. 1.

As the proposed robust model is an NP-hard problem, exact methods are unable to solve its large-scale version in a reasonable time. As a result, this paper uses a hybrid algorithm including the SA optimization and the Benders decomposition while solutions are compared with the lower and upper bounds presented by the CPLEX solver. Thus, the next sections present the solution algorithm and results.

3 Solution algorithm: a hybrid SA and the Benders decomposition algorithm

Over the past few decades, meta-heuristic approaches have been presented as powerful tools to optimize the complex problems like NP-hard and NP-complete with regard to the computational complexity theory. In optimization methods, meta-heuristic algorithms have presented solutions with minimal errors compared with the exact methods. However, the exact methods in discrete programming are unable to solve large-scale problems, but some methods have been developed to overcome this fundamental weakness like the decomposition approaches. Moreover, with the advent and advancement of modern technology like quantum computers, decomposition approaches are able to solve problems not being solved in a reasonable time before. Note that the acceptability of meta-heuristic approaches is not weakened as they use the same computers as well.

The proposed problem, a bi-objective model, combines two important problems in the operation research called the covering location-allocation problem and the scheduling problem while there are several constraints on it. The proposed model is an NP-hard problem and being unable to be solved with exact methods or complete enumeration algorithms like branch and bound. This paper proposes a hybrid algorithm including the SA and the Benders decomposition. The Benders decomposition reduces the complexity of the proposed model. Solutions obtained by the proposed hybrid algorithm are compared with CPLEX solver. The proposed hybrid algorithm decomposes the presented model into two main models solved by SA and the Benders decomposition, respectively.

As the presented model has two conflictive objectives [Eqs. (1, 2)] unable to be optimized separately, the linear scalarization [56], sometimes called the weighted sum method, is employed to solve in which one scalar objective (F) [Eq. (32)] is obtained by merging the two weighted objective functions,

$$ {\text{Min}}\,F = \omega_{1} \,{\text{Cost}} + \omega_{2} \,{\text{Time}} $$

(32)

where ω ₁ and ω ₂ are weighting coefficients for decision makers. Note that this paper uses an equal weight of ω ₁ = ω ₂ = 0.5 for each objective function.

However, the proposed methodology for solving the presented model in this paper is illustrated graphically after a brief description about SA and Benders decomposition.

3.1 Benders decomposition

The Benders method [57] decomposes a hard mathematical model into the master problem and the subproblem rewritten the dual version, and then it tries to optimize them to find the optimal solution as follows.

• 1. Calculate the lower bound by solving the master problem including one or more variables (here $H_{{i^{\prime } lk}}^{i}$);

• 2. Obtain the optimality cut for adding to the master problem by inserting obtained variables in step (1) (here $H_{{i^{\prime } lk}}^{i}$) into dual subproblem;

• 3. Calculate the upper bound by summing the function objective 1 and 2;

• 4. Checking the stopping criterion with the sum of the lower and the upper bounds, which means that going to step (1) if the stopping criterion is not satisfied.

3.2 Simulated annealing (SA) optimization

Meta-heuristic algorithms are classified into two groups according to their search policy which are single-based search like the Tabu search [27] and the SA [58], and population-based search like the genetic algorithm [26], the particle swarm optimization [59], and the harmony search [31]. Employing meta-heuristic algorithm depends on the type of problems. As the proposed solution methodology presents one point to start optimizing the proposed model, this paper employs the SA to find the near-optimal solution in the proposed hybrid algorithm.

Regarding statistical mechanics called the Metropolis algorithm, the SA is developed [60]. Kirkpatrick et al. [61] and Černý [62] proposed the first version of SA independently. A method including heating and controlled cooling of a material to make a strong crystalline structure called the annealing process in metallurgy inspired researchers to develop SA algorithms. Cooling slowly a high-temperature material leads to a strong crystal. The SA imitates these energy changes to solve the models.

To begin the SA, an initial solution is presented randomly after defining the temperature parameter (T = 1000, reduced slowly in every iteration), and then the following cycle is repeated (here It = 10,000) until the termination criterion is obtained.

Regarding an initial solution (sol), the operators, called insertion, reversion, and swap [58] first create a random neighbor (sol^′) while their cost functions, f(sol), and f(sol^′), are calculated. In minimization problems, a random neighbor, sol^′, is accepted as a new solution if f(sol^′) ≤ f(sol); otherwise, sol^′ can be accepted with the probability of P based on the Boltzmann distribution shown in Eq. (33) [61].

$$ p = \exp \left( { - {{\left( {f({\text{sol}}^{\prime } ) - f({\text{sol}})} \right)} \mathord{\left/ {\vphantom {{\left( {f({\text{sol}}^{\prime } ) - f({\text{sol}})} \right)} T}} \right. \kern-0pt} T}} \right) $$

(33)

Note that this paper uses a trial and error method to calibrate and tune the parameters of the SA.

3.3 CPLEX

To employ IBM ILOG CPLEX optimizer, constraints shown in Eqs. (12) and (14) should be rewritten in linear formation as,

$$ H_{{i^{\prime } lk}}^{i} + H_{ilk}^{{i^{\prime } }} = S_{{i^{\prime } lk}}^{\prime i} ;\quad \forall i \ne i^{\prime } ,i\,\&\, i^{\prime } \in I,k \in K,l \in L $$

(34)

$$ S_{lk}^{i} + S_{lk}^{{i^{\prime } }} - 1 \le S_{{i^{\prime } lk}}^{\prime i} ;\quad \forall i \ne i^{\prime } ,i\,\&\, i^{\prime } \in I,k \in K,l \in L $$

(35)

$$ 2S_{{i^{\prime } lk}}^{\prime i} \le S_{lk}^{i} + S_{lk}^{{i^{\prime } }} ;\quad \forall i \ne i^{\prime } ,i\,\&\, i^{\prime } \in I,k \in K,l \in L $$

(36)

$$ T_{{l^{\prime } k^{\prime } }}^{i} - T_{lk}^{i} \ge \left( {n_{{ll^{\prime } }} + t_{{k^{\prime } }}^{i} } \right)W_{{ll^{\prime } k^{\prime } }}^{i} - M\left( {1 - f_{{kk^{\prime } }}^{i} S_{{lkl^{\prime } k^{\prime } }}^{i} } \right);\quad \forall i \in I,k \ne k^{\prime } ,k\,\&\, k^{\prime } \in K,l \ne l^{\prime } ,l\,\&\, l^{\prime } \in L $$

(37)

$$ S_{lk}^{i} + S_{{l^{\prime } k^{\prime } }}^{i} - 1 \le S_{{lkl^{\prime } k^{\prime } }}^{i} ;\quad \forall i \in I,k \ne k^{\prime } ,k\,\&\, k^{\prime } \in K,l \ne l^{\prime } ,l\,\&\, l^{\prime } \in L $$

(38)

$$ 2S_{{lkl^{\prime } k^{\prime } }}^{i} \le S_{lk}^{i} + S_{{l^{\prime } k^{\prime } }}^{i} ;\quad \forall i \in I,k \ne k^{\prime } ,k\,\&\, k^{\prime } \in K,l \ne l^{\prime } ,l\,\&\, l^{\prime } \in L $$

(39)

3.4 The proposed hybrid algorithm including SA and Benders decomposition

In the proposed hybrid algorithm, the formulated model is divided into two parts solved by the SA and the Benders decomposition, respectively. In brief, considering the near-optimal value of decision variables, the Benders decomposition finds $H_{{i^{\prime } lk}}^{i}$ and $T_{lk}^{i}$ when the SA determines $Z_{jl}^{i} ,W_{{ll^{\prime } k}}^{i} ,Y_{lk} ,$ and $X_{l}$ shown in Fig. 1. The proposed algorithm includes several steps illustrated as follows.

Fig. 1

Solution representation for SA

Step 1 After tuning parameters of SA (iteration = 1000 and T = 30,000), the SA solves the following model shown in Eqs. (40–50) derived from the proposed model to determine $Z_{jl}^{i} ,W_{{ll^{\prime } k}}^{i} ,Y_{lk} ,$ and $X_{l}$ variables.

$$ {\text{Min}}\,{\text{Cost = }}\left( {\sum\limits_{i = 1}^{n} {\sum\limits_{l = 1}^{s} {\sum\limits_{j = 1}^{m} {\left( {c_{jl} m_{jl} Z_{jl}^{i} } \right)} } } + \sum\limits_{i = 1}^{n} {\sum\limits_{l = 1}^{s} {\sum\limits_{{l^{\prime } = 1}}^{m} {\sum\limits_{k = 1}^{c} {\left( {\rho_{{ll^{\prime } k}} W_{{ll^{\prime } k}}^{i} } \right)} } } } } \right)\;\left( {{\text{Total}}\,{\text{Costs}}} \right) $$

(40)

Subject to

$$ \sum\limits_{l = 1}^{s} {Z_{jl}^{i} } \ge d_{j}^{i} L_{j}^{i} ;\quad \forall j \in J,i \in I\quad({\text{Covering}}\,{\text{constraint}}) $$

(41)

$$ \sum\limits_{j = 1}^{m} {Z_{jl}^{i} } \ge A_{l}^{i} X_{l} ;\quad \forall l \in L,i \in I\quad({\text{Patient}}\,{\text{service}}\,{\text{constraint}}) $$

(42)

$$ \sum\limits_{k = 1}^{c} {Y_{lk} } \le cX_{l} ;\quad \forall l \in L\quad({\text{Machines}}\,{\text{constraint}}) $$

(43)

$$ \sum\limits_{i = 1}^{n} {\sum\limits_{j = 1}^{m} {Z_{jl}^{i} } } \le MX_{l} ;\quad \forall l \in L\quad({\text{Establishment}}\,{\text{constraint}}) $$

(44)

$$ \sum\limits_{i = 1}^{n} {\sum\limits_{{l^{\prime } = 1}}^{m} {W_{{ll^{\prime } k}}^{i} } } \le MY_{lk} ;\quad \forall l \in L,k \in K\quad({\text{Transference}}\,{\text{constraint}}) $$

(45)

$$ \sum\limits_{{l^{\prime } = 1}}^{s} {W_{{ll^{\prime } k}}^{i} } = \sum\limits_{i = 1}^{n} {\sum\limits_{j = 1}^{m} {f_{k}^{i} Z_{jl}^{i} } } + \sum\limits_{{l^{\prime } = 1}}^{s} {\sum\limits_{{k^{\prime } = 1}}^{c} {f_{{k^{\prime } k}}^{i} W_{{l^{\prime } lk^{\prime } }}^{i} } } ;\quad \forall i \in I,l \ne l^{\prime } ,l \in L,k \ne k^{\prime } ,k \in K $$

(46)

$$ S_{lk}^{i} \le \sum\limits_{{l^{\prime } = 1}}^{s} {W_{{l^{\prime } lk}}^{i} } \le MS_{lk}^{i} ;\quad \forall i \in I,k \in K,l \ne l^{\prime } ,l \in L $$

(47)

$$ \sum\limits_{l = 1}^{s} {e_{l} X_{l} } + \sum\limits_{i = 1}^{n} {\sum\limits_{l = 1}^{s} {\sum\limits_{j = 1}^{m} {g_{l}^{i} Z_{jl}^{i} \le B_{1} } } } \quad({\text{Budget}}\,{\text{constraint}}) $$

(48)

$$ \sum\limits_{k = 1}^{c} {\sum\limits_{l = 1}^{s} {r_{lk} Y_{lk} \le B_{2} } } \quad({\text{Budget}}\,{\text{constraint}}) $$

(49)

$$ Z_{jl}^{i} ,W_{{ll^{\prime } k}}^{i} \ge 0;Y_{lk} ,S_{lk}^{i} ,X_{l} = 0\;{\text{or}}\;1; $$

(50)

Step 2 By getting the near-optimal values of $Z_{jl}^{i} ,W_{{ll^{\prime } k}}^{i} ,Y_{lk} ,$ and $X_{l}$ variables by the SA in Step 1, the Benders decomposition method tries to determine $H_{{i^{\prime } lk}}^{i}$ and $T_{lk}^{i}$ to optimize the following model shown in Eqs. (51–56).

$$ {\text{Min}}\,{\text{Time}} = \left( {\sum\limits_{i = 1}^{n} {\left( {C{ \hbox{max} }_{i} } \right)} } \right)\,\left( {{\text{Completion}}\,{\text{time}}\,{\text{of}}\,{\text{patient}}\,{\text{treatment}}} \right) $$

(51)

Subject to

$$ H_{{i^{\prime } lk}}^{i} + H_{ilk}^{{i^{\prime } }} = S_{lk}^{i} S_{lk}^{{i^{\prime } }} ;\quad \forall i \ne i^{\prime } ,i\,\&\, i^{\prime } \in I,k \in K,l \in L $$

(52)

$$ \left( {T_{lk}^{{i^{\prime } }} - T_{lk}^{i} + M\left( {1 - H_{{i^{\prime } lk}}^{i} } \right)} \right) \ge t_{{i^{\prime } k}} \sum\limits_{{l^{\prime} = 1}}^{s} {W_{{l^{\prime } lk}}^{i} } ;\quad \forall i \ne i^{\prime } ,i\,\&\, i^{\prime } \in I,j \in J,l \ne l^{\prime } ,k \in K,l \in L $$

(53)

$$ T_{{l^{\prime } k^{\prime } }}^{i} - T_{lk}^{i} \ge \left( {n_{{ll^{\prime } }} + t_{{k^{\prime } }}^{i} } \right)W_{{ll^{\prime } k^{\prime } }}^{i} - M\left( {1 - f_{{kk^{\prime } }}^{i} S_{lk}^{i} S_{{l^{\prime } k^{\prime } }}^{i} } \right);\quad \forall i \in I,k \ne k^{\prime } ,k\,\&\, k^{\prime } \in K,l \ne l^{\prime } ,l\,\&\, l^{\prime } \in L $$

(54)

$$ C{ \hbox{max} }_{i} \ge T_{lk}^{i} - M\left( {1 - S_{lk}^{i} } \right);\quad \forall i \in I,k \in K,l \in L $$

(55)

$$ C{ \hbox{max} }_{i} ,T_{lk}^{i} \ge 0;H_{{i^{\prime } lk}}^{i} = 0\;{\text{or}}\;1; $$

(56)

The master problem in the Benders terminology is,

$$ {\text{Min}}\,{\text{Z}} $$

Subject to:

$$ \begin{aligned} Z & \ge \sum\limits_{j = 1}^{s} {\sum\limits_{k = 1}^{c} {\sum\limits_{l = 1}^{s} {\sum\limits_{{i^{\prime } = 1}}^{n} {\sum\limits_{i = 1}^{n} {U_{{i^{\prime } lk}}^{i} } } } } t_{k}^{i} H_{{i^{\prime } lk}}^{i} W_{jlk}^{i} } + \sum\limits_{k = 1}^{c} {\sum\limits_{l = 1}^{s} {\sum\limits_{j = 1}^{s} {\sum\limits_{i = 1}^{n} {U_{lk}^{\prime i} } } } } S_{lk}^{i} W_{jlk}^{i} (n_{jl} + t_{k}^{i} ) \\ & \quad + \sum\limits_{{k^{\prime } = 1}}^{c} {\sum\limits_{k = 1}^{c} {\sum\limits_{{l^{\prime } = 1}}^{s} {\sum\limits_{l = 1}^{s} {\sum\limits_{i = 1}^{n} {V_{{lkl^{\prime } k^{\prime } }}^{i} f_{{kk^{\prime } }}^{i} S_{lk}^{i} S_{{l^{\prime } k^{\prime } }}^{i} W_{{ll^{\prime } k^{\prime } }}^{i} (} } } } } n_{{ll^{\prime } }} + t_{{k^{\prime } }}^{i} ) + \sum\limits_{k = 1}^{c} {\sum\limits_{l = 1}^{s} {\sum\limits_{i = 1}^{n} {V_{lk}^{\prime i} (S_{lk}^{i} - 1)} } } \\ \end{aligned} $$

(57)

$$ H_{{i^{\prime } lk}}^{i} = 0\;{\text{or}}\;1\quad \forall i,i^{\prime } \in I,l \in L,k \in K $$

(58)

And the dual subproblem (DSP) can be written as,

$$ \begin{aligned} {\text{Max}}\,{\text{DSP}} & = \sum\limits_{k = 1}^{c} {\sum\limits_{l = 1}^{s} {\sum\limits_{j = 1}^{s} {\sum\limits_{{i^{\prime } = 1}}^{n} {\sum\limits_{i = 1}^{n} {U_{{i^{\prime } lk}}^{i} t_{k}^{i} H_{{i^{\prime } lk}}^{i} W_{jlk}^{i} } } } } } + \sum\limits_{k = 1}^{c} {\sum\limits_{l = 1}^{s} {\sum\limits_{j = 1}^{s} {\sum\limits_{i = 1}^{n} {U_{lk}^{\prime i} } } } } S_{lk}^{i} W_{jlk}^{i} (n_{jl} + t_{k}^{i} ) \\ & \quad + \sum\limits_{{k^{\prime } = 1}}^{c} {\sum\limits_{k = 1}^{c} {\sum\limits_{{l^{\prime } = 1}}^{s} {\sum\limits_{l = 1}^{s} {\sum\limits_{i = 1}^{n} {V_{{lkl^{\prime } k^{\prime } }}^{i} f_{{kk^{\prime } }}^{i} S_{lk}^{i} S_{{l^{\prime } k^{\prime } }}^{i} W_{{ll^{\prime } k^{\prime } }}^{i} (n_{{ll^{\prime } }} + t_{{k^{\prime } }}^{i} )} } } } } + \sum\limits_{k = 1}^{c} {\sum\limits_{l = 1}^{s} {\sum\limits_{i = 1}^{n} {V_{lk}^{\prime i} (S_{lk}^{i} - 1)} } } \\ \end{aligned} $$

(59)

Subject to:

$$ \sum\limits_{{i^{\prime } = 1}}^{n} {(U_{{i^{\prime } lk}}^{i} - } H_{ilk}^{{i^{\prime } }} U_{ilk}^{{i^{\prime } }} ) + \sum\limits_{{k^{\prime } = 1}}^{c} {\sum\limits_{{l^{\prime } = 1}}^{s} {(V_{{lkl^{\prime } k^{\prime } }}^{i} } } - f_{{k^{\prime } k}}^{i} S_{lk}^{i} S_{{l^{\prime } k^{\prime } }}^{i} V_{{l^{\prime } k^{\prime } lk}}^{i} ) + U_{lk}^{\prime i} - S_{lk}^{i} V_{lk}^{\prime i} \le 0;\quad \forall i \in I,l \in L,k \in K $$

(60)

$$ \sum\limits_{k = 1}^{c} {\sum\limits_{l = 1}^{s} {\sum\limits_{i = 1}^{n} {V_{lk}^{\prime i} \le 1} } } $$

(61)

$$ U_{{i^{\prime } lk}}^{i} ,U_{lk}^{\prime i} ,V_{{lkl^{\prime } k^{\prime } }}^{i} ,V_{lk}^{\prime i} \ge 0\quad \forall i,i^{\prime } \in I,l,l^{\prime } \in L,k.k^{\prime } \in K $$

(62)

Note that the Benders decomposition method described in Sect. 3.1 solves the master problem and the dual subproblem with the IBM ILOG CPLEX Optimizer due to reduction of the model complexity.

Step 3 Repeat Steps 1 and 2 for 1000 iteration while T is reduced slowly in every iteration.

4 Results

Regarding nine examples in Table 2, in this section, the optimal results provided by the proposed hybrid algorithm, including the SA and the Benders decomposition, are compared with the exact method and a standard version of SA. Table 2 shows the summarized results. From Table 2, it can be concluded that the proposed hybrid algorithm has the better performance than the standard SA. In this paper, the approach used in the proposed algorithm, called the Benders decomposition, helps to algorithm to reduce the complexity of the proposed model which is an NP-hard problem. In comparison with the standard SA, the proposed hybrid algorithm presents the near-optimal solutions with 51 % reduction in CPU time computation (Fig. 2); moreover, the results are improved 20 % at the same way (Fig. 3). The main reason to describe these improvements of the proposed hybrid algorithm than the standard SA is to employ the Benders decomposition method facilitating optimization of NP-hard problems.

Table 2 Comparisons of algorithm solutions

Fig. 2

Comparisons of CPU time

Fig. 3

Comparisons of CPU time

To verify and validate the solutions provided by the proposed hybrid algorithm, this paper employs IBM ILOG CPLEX optimizer. The lower and upper bounds obtained by CPLEX verifies the performance of proposed hybrid algorithm for optimizing the presented model, the mixed integer programming problem. As NP-hard problems are unable to be solved by exact methods, CPLEX optimizer can solve only the first four examples so that solving 5th example is stopped in 7200th second to take the upper bound. Moreover, CPLEX optimizer is unable to solve the examples bigger that 8th example and provide a feasible solution. Regarding the results shown in Table 2 and the boxplot in Fig. 4, the proposed hybrid algorithm provides the better results than CPLEX optimizer for large-scale problems so that optimizing the presented model faster (28 %), accurate (10 %), and less GAP than it. The statistical test verifies the performance of the proposed hybrid algorithm to present the accurate solutions (P value = 0.006 < 0.05 in Table 3).

Fig. 4

Boxplot of the proposed hybrid algorithm and CPLEX

Table 3 T test for the proposed hybrid algorithm and CPLEX

Note that all algorithms are coded by C# and IBM ILOG in Win8 environment with a PC with core i7 1.7 GHz, 8 GB RAM DDR3.

In the next subsection, the behavior of proposed robust model is investigated to uncertain conditions.

4.1 Considering the robust proposed model

To overcome uncertain situations under real-world conditions, robust optimization (RO) has been employed to provide the solution including the deterministic variability. Regarding the budget constraints, the costs of purchasing and installing of machines (r _lk ), and the fixed and variable costs of establishing hospitals (e _l and $g_{l}^{i}$, respectively) are assumed to be uncertain with an ambiguous distribution. To test and verify the proposed robust model against of uncertain situations, this subsection performs the sensitivity analysis on protection levels of $\varGamma_{i}$ with respect to solving 200 instances.

Regarding the first example (k–m–n = 4–3–4), the uncertain data are chosen from interval set so that e _l , $g_{l}^{i}$, and $r_{lk}$ are assumed to have 30 % variability of their original value. To begin, the protection level of $r_{lk}$ $(\varGamma_{1} )$ can be set between 0 and 12 indicating the certain circumstance and Soyster method [57], respectively. This paper generates 200 instances for the different values of $\varGamma_{1}$, and then solves the proposed model. Then, the Monte Carlo simulation is used to analyze the quality and the robustness of solutions under uncertain situations.

In Table 4 showing the results, P _q is the probability of obtaining a better solution by Monte Carlo simulation than the robust solution. The more P _q is obtained, the less the robust solution has the quality. P _i is the percent of increase in results provided by the proposed robust model than the certain model shown in Eqs. (1–16). P _v is the probability of constraint violation which is robustness of the solution.

Table 4 Sensitivity analysis on protection level of Γ ₁, r _lk

Figure 5 shows the robustness of the proposed model, and Fig. 6 presents the quality of the solution with regard to different values of Γ ₁. From Figs. 5, 6, it can be concluded that the increase in the protection raises the robustness of the solutions while the quality of near-optimal solutions is decreased.

Fig. 5

Robustness of solutions for r _lk

Fig. 6

Quality of solutions for r _lk

Regarding Table 4, there is not the considerable variation in the near-optimal solutions for the protection levels of 6 to 12. Therefore, to have the probability of violation less than 10 %, the amount of Γ ₁ should be set 6 while the quality of solutions is reduced 24 %; moreover, the objective function is raising 8.8 %.

The second part of sensitivity analysis is to consider e _l (Γ ₂) and $g_{l}^{i}$ $(\varGamma_{3} )$ with the variation of [0 3] and [0 6], respectively. Table 5 presents the results of the robust solutions for the fixed and variable costs of establishing hospitals.

Table 5 Sensitivity analysis on the protection level of Γ ₂ and Γ ₃, (e _l and $g_{l}^{i}$)

Figure 7 shows the robustness of the proposed model, and Fig. 8 presents the quality of the solution with regard to different values of Γ ₂ and Γ ₂. Similar to Figs. 5, 6, 7 and 8 show that the protection levels and the robustness of the solutions are increased while the quality of near-optimal solutions is decreased.

Fig. 7

Robustness of solutions for e _l and $g_{l}^{i}$

Fig. 8

Quality of solutions for e _l and $g_{l}^{i}$

For example, to have the high quality of near-optimal solutions like 80 %, the protection levels should be Γ ₂ = 0 and Γ ₃ = 3 while the probability of violation more than 90 % is inevitable. Similarly, to have the increase of less than 10 %, Γ ₂ = 1 and Γ ₃ = 2, the probability of violation will be 60 %.

With regard to Table 5 and Fig. 8, the quality of near-optimal solutions is reduced after Γ ₂ = 2 and Γ ₃ = 3 which are an upper bound to the quality. Regarding Table 5, if Γ ₂ = 2 and Γ ₃ = 3, the probability of violation will be less than 10 % while the quality of solutions is reduced. The objective function is raising 22 % as well.

From the sensitivity analysis on the protection level of Γ _i , it can be concluded that the variation in the fixed and variable costs of establishing hospitals increases more costs (22 % compared to 8.8 %) to the objective function than the variation in the costs of purchasing and installing of machines.

5 Conclusion and the future research

In healthcare systems, the hospital location and the service allocation play an important role in the total costs. This paper developed a bi-objective hybrid model including location-allocation and scheduling problems while covering the demand of each service was limited. To near real-world conditions for overcoming uncertain situations, the budget including the costs of purchasing and installing of machines and establishing hospitals was assumed to be uncertain with an ambiguous distribution. The robust counterpart model, the robust optimization, was employed to solve the proposed uncertain model locating hospitals and allocating machines and services scheduled. In addition, the specialized equipment like CT scan and MRI machines had a limited space to install while there was a cost constraint on hospitals and specialized equipment. It was also assumed that there were certain disease types like heart, brain, eye, and cancer. The purpose of optimizing the proposed model was to find a near-optimal solution including the location of hospitals, the number of hospitals and specialized equipment, the determination of allowable number of each service of hospitals, the assignment of demand of each service and specialized equipment to hospitals, the determination of demand that should be transferred from one hospital to another (patient transfer), and schedule services.

As the proposed mixed integer programming problem, minimizing the total costs and the completion time of the demand simultaneously, was an NP-hard problem, the exact method was unable to solve its large-scale version. Thus, the hybrid meta-heuristic optimization, a hybrid algorithm including the simulated annealing (SA) optimization and the Benders decomposition, was employed to solve the proposed model. Regarding lower bound and upper bound, the proposed hybrid algorithm was verified by CPLEX optimizer to present near-optimal solutions. Moreover, results were compared with a standard version of SA. The results showed that the proposed hybrid algorithm presented the better solutions than CPLEX optimizer and the standard SA in less time. Moreover, the results showed that the uncertainty used in the proposed model properly formulated real-world situations compared to the deterministic case. The main reason to describe these improvements of the proposed hybrid algorithm was to employ the Benders decomposition method facilitating optimization of NP-hard problems. The sensitivity analysis was performed to verify the proposed robust model against of uncertain situations while the Monte Carlo simulation was used to analyze the quality and the robustness of solutions under uncertain situations.

The main contribution of this paper was twofold. First, in the proposed mathematical model, innovations were to consider the uncertain budget and employ the robust optimization to overcome it, formulate the second objective minimizing the completion time of the total patient services (group scheduling), and develop a hybrid model including the covering location-allocation and scheduling problems. Second, in the solution algorithm, this paper proposed a hybrid algorithm including the SA optimization and the Benders decomposition. Finally, this paper can be extended as follows.

• Employing other meta-heuristics, population-based search algorithms, to compare the proposed hybrid algorithm.

• Using Taguchi method to calibrate parameters of algorithms.

• Utilizing the Pareto-optimal solution to the bi-objective model.

• Considering the fuzzy number to parameters to simulate more uncertainties.

• Investigating the queuing theory to minimize average waiting time of demands in the queue.