Keywords

1 Introduction

Creating systems of emergency services and establishing the related facilities have a pivotal role in the success of planning. The model of maximal covering location has a lot of applications in this field. In MCLP, the objective is to determine the location of a limited number of facilities in order to maximize the extent of coverage based on coverage radius. In this study, another multiple-objective model of maximal covering location has been presented. Populations and the extent of demands are continuously changing throughout the time in different places. Based on these changes, the number of transportation vehicles in the centers of emergency services must change. Determining the initial coverage and backup coverage in a fractional manner are among the other features of the model. In many models, coverage radius is determined in a fixed manner, which is not consistent with reality. In the presented model, coverage radius is gradual. In addition, capacity constraint of facilities is taken into account. The potential locations have fixed and variable expenses in the installation of facilities. Up to now, different methods have been suggested for the solution of multiple-objective models, including: goal programming and weighted methods. The goal programming enables decision-makers to determine the level of expectations for each goal. Since in reality, it is difficult to find the expected figure exactly, the intended figures might not be found with assurance. In situations which the decision-makers cannot determine the objective figures, the fuzzy goal programming can help them.

2 Literature Review

Up to now, many models have been suggested in this field. All these models have developed the basic models. In the field of multiple-objective models, Araz et al. (2007) proposed a multi-objective model. The objectives considered in the model are maximization of the population covered by one vehicle, maximization of the population with backup coverage, and increasing the service level. Beraldi and Bruni (2009) suggested a probability model of the positioning of emergency transportation vehicles. This model seeks to minimize fixed and variable expenses related to the stationing of transportation vehicles. Coskun and Erol (2010) proposed a single-objective model whose focus was to minimize the expenses related to the stationing and the allocation of transportation vehicles. In the suggested models, the coverage radii are fixed. The gradual coverage is a concept which helps to bring the models closer to the realities. The suggested model of the current study is a model with gradual coverage. Berman et al. (2003) in their article proposed two coverage radii. In their model, the demands within the smaller radius were covered completely; the demands outside the bigger radius were not covered; and the demands between the two radii were covered according to a linear function. Another effective factor which increased the efficiency of the model was the consideration of demand dispersion in each zone. The majority of studies on maximal covering location are static, and the variable of time has not been taken into account in the process of positioning (Fazel Zarandi et al. 2013). Since demand dispersion changes throughout years, the dynamic positioning of emergency facilities can improve the quality of these services. Başar et al. (2011) suggested a dynamic model with double-coverage approach for medical service stations. This single-objective model optimizes the level of demands which have been covered at least twice.

3 Proposed Model

In the proposed model, the problem is considered in a discrete condition. The expenses are considered to be fixed throughout time. Each demand point can be covered by one or more centers. Then, some of the parameters and variables are introduced. r1,r2: Smaller and bigger radius; dij: The shortest distance from i to j; Kj: The workload capacity for a facility in j; fj: Fixed costs; vj: Variable costs (per-unit capacity cost); hit: The population at node i in period t; Mi: The set of zones that are within a distance less than r2 from i; Uit; The fraction of population in i covered by more than one vehicle in t; Yit: The fraction of population in node i covered by one vehicle in t; Xjt: The integer number of vehicles located at potential site j in period t; Wijt: The fraction of population.

The suggested model has several advantages over previous models. Firstly, it is multiple-objective model whose aims are maximizing the initial coverage, maximizing backup coverage, and minimizing expenses. Secondly, since population dispersion is not fixed throughout time, the variable of time has been taken as an important factor in order to prepare the ground for meeting the future demands. Thirdly, Uit and Yit have been defined as continuous variables in order to make it possible that part of the demands of a zone are covered. Finally, in contrast to the previous models whose coverage radii are fixed, the coverage radius in this model is gradual. In the following parts, the suggested mathematical model is explained.

$$ {\text{Max}}\;{\text{Z}}_{ 1} = \sum\limits_{t = 1}^{T} {\sum\limits_{i = 1}^{I} {h_{it} } } \cdot Y_{it} $$
(1)
$$ {\text{Max}}\;{\text{Z}}_{ 2} = \sum\limits_{t = 1}^{T} {\sum\limits_{i = 1}^{I} {h_{it} } } \cdot U_{it} $$
(2)
$$ {\text{Max}}\;{\text{Z}}_{ 3} = \sum\limits_{t = 1}^{T} {\sum\limits_{j = 1}^{J} {(f_{j} } } \cdot Z_{jt} + v_{j} \cdot X_{jt} ) $$
(3)

Subject to:

$$ \sum\limits_{j = 1}^{J} {X_{jt} } \le P_{t} \quad \forall {\text{t}} \in {\text{T,}}({\text{P}}_{\text{t}} \le {\text{P}}_{{{\text{t}} + 1}} ) $$
(4)
$$ {\text{X}}_{\text{jt}} \le {\text{S}}_{\text{j}} .{\text{ Z}}_{\text{jt}} \quad \forall {\text{t}} \in {\text{T}},\,\,\forall {\text{j}} \in {\text{J}} $$
(5)
$$ {\text{Z}}_{\text{jt}} \le {\text{X}}_{\text{jt}} \quad \forall {\text{t}} \in {\text{T}},\;\;\forall {\text{j}} \in {\text{J}} $$
(6)
$$ {\text{Z}}_{{{\text{j}}({\text{t}} - 1)}} \le {\text{Z}}_{\text{jt}} \quad \forall ({\text{t}} \ge 2)\,\,\forall {\text{j}} \in {\text{J}} $$
(7)
$$ {\text{U}}_{\text{it}} {-}{\text{q}}_{\text{it}} \le 0\quad \forall {\text{t}} \in {\text{T}},\,\,\forall {\text{i}} \in {\text{I}} $$
(8)
$$ {\text{Q}}_{\text{it}} {-}{\text{Y}}_{\text{it}} \le 0\quad \forall {\text{t}} \in {\text{T}},\,\,\forall {\text{i}} \in {\text{I}} $$
(9)
$$ \sum\limits_{{j \in M_{i} }} {W_{ijt} } - Y_{it} - U_{it} \ge 0\quad \forall {\text{t}} \in {\text{T}},\,\,\forall {\text{i}} \in {\text{I}} $$
(10)
$$ {\text{W}}_{\text{ijt}} \le {\text{C}}_{\text{ij}} \quad \forall {\text{t}} \in {\text{T}},\,\,\forall {\text{i}} \in {\text{I}},\,\,\forall {\text{j}} \in {\text{M}}_{\text{i}} $$
(11)
$$ \sum\limits_{i = 1}^{I} {W_{ijt} \cdot h_{it} } \le K_{j} \cdot X_{jt} \quad \forall {\text{t}} \in {\text{T}},\,\,\forall {\text{j}} \in {\text{J}} $$
(12)
$$ {\text{U}}_{\text{it}} \le 1\quad \forall {\text{t}} \in {\text{T}},\,\,\forall {\text{i}} \in {\text{I}} $$
(13)
$$ {\text{Y}}_{\text{it}} \le 1\quad \forall {\text{t}} \in {\text{T}},\,\,\forall {\text{i}} \in {\text{I}} $$
(14)
$$ {\text{C}}_{\text{ij}} = \left\{ {\begin{array}{*{20}l} 1 \hfill & {d_{ij} \le r_{1} } \hfill \\ {\frac{{(r_{2} - d_{ij} )}}{{(r_{2} - r_{1} )}}} \hfill & {r_{1} < d_{ij} \le r_{2} } \hfill \\ 0 \hfill & {d_{ij} > r_{2} } \hfill \\ \end{array} } \right.\quad \forall {\text{i}} \in {\text{I}},\,\,\forall {\text{j}} \in {\text{J}} $$
(15)
$$ {\text{X}}_{\text{jt}} \ge 0\;{\text{integer}}\quad \forall {\text{t}} \in {\text{T}},\,\,\forall {\text{j}} \in {\text{J}} $$
(16)
$$ {\text{Z}}_{\text{jt}} \in \left\{ {0,1} \right\}\quad \forall {\text{t}} \in {\text{T}},\,\,\forall {\text{j}} \in {\text{J}} $$
(17)
$$ {\text{q}}_{\text{it}} \in \left\{ {0,1} \right\}\quad \forall {\text{t}} \in {\text{T}},\,\,\forall {\text{i}} \in {\text{I}} $$
(18)

In this model, the objective functions (1) and (2) seek to maximize the initial and backup coverage, respectively. The objective function (3) intends to minimize the fixed and variable expenses related to the stationing of transportation vehicles. The constraint (4) shows that in the period t, at most Pt facilities can be stationed in the potential locations (j). Also, the maximum number of facilities in each period should be more than or equal to the number of facilities in the previous period (\( {\text{P}}_{\text{t}} \le {\text{P}}_{{{\text{t}} + 1}} \)). The constraints (5) and (6) show that if the potential location j in the period t is selected for the facility, at least one facility and at most Sj facilities can be allocated to this station. Constraint (7) shows that if the potential location j is selected as a location for stationing facilities, it is also selected in the following periods. In other words, if a station is built for a given period, it is also used in the following periods. The constraint (8) and (9) guarantee that Uit can be assigned value if Yit = 1. The constraint (10) shows the number of zones which are able to cover the demand point i. The constraint (11) guarantees that the demand points can be covered to a level equal to the coverage function Cij, if the constraint (12) is met. In constraints (13) and (14), Uit and Yit have defined as continuous variables within [0,1]. Constraint (15) shows the gradual coverage function. In Constraint (16) Xjt is the integer number of vehicles. In constraint (17), the variable Zjt is equal to 1 if the location j in the period t is selected as a station; otherwise zero. Based on constraint (18), the variable qit is equal to 1, the backup coverage is made possible for that demand point.

4 Solution Approach

In order to solve the suggested model, four approaches have been used. In lexicographic multi-objective linear programming (LMOLP) approach which is crisp, the first objective is met completely at the beginning; then, the second and last objectives are met, respectively. In this approach, an ordinal ranking of the objectives are specified as follows:

Priority level 1: Max Z1, Priority level 2: Max Z2, Priority level 3: Min Z3.

In the first FGP approach (FGP1), the objectives have no priority over each other and all objectives are wanted to be satisfied simultaneously and also no relative importance assigned to objectives. So the first FGP based on lower bounds (LB), upper bounds (UB) of objectives and \( \upalpha_{\text{t}} \) (the satisfaction-level of tth period) can be defined as follows:

$$ {\text{Max}}\;\;\sum\limits_{t = 1}^{3} {\alpha_{t} } $$
(19)

Subject to:

$$ \alpha_{t} \le \frac{{\sum_{i = 1}^{I} {h_{it} \cdot Y_{it} } - LB(Z_{1} )_{t} }}{{UB(Z_{1} )_{t} - LB(Z_{1} )_{t} }},\alpha_{t} \le \frac{{\sum_{i = 1}^{I} {h_{it} \cdot U_{it} } - LB(Z_{2} )_{t} }}{{UB(Z_{2} )_{t} - LB\,(Z_{2} )_{t} }}\quad \forall {\text{t}} \in {\text{T}} $$
(20)
$$ \alpha_{t} \le \frac{{UB(Z_{3} )_{t} - \sum_{j = 1}^{J} {(f_{j} \cdot Z_{jt} + v_{j} \cdot X_{jt} )} }}{{UB(Z_{3} )_{t} - LB(Z_{3} )_{t} }}\quad \forall {\text{t}} \in {\text{T}} $$
(21)

and constraints (3)–(18). Also, \( \upalpha_{\text{t}} \in \left[ {0,1} \right]. \)

In additive fuzzy goal programming (Chen and Tsai 2001)—(A-FGP-C) the first objective has priority over the second objective, and the second objective has priority over the third objective. So A-FGP-C model can be formulated as follows:

$$ {\text{Max}}\;\;\sum\limits_{z = 1}^{3} {\sum\limits_{t = 1}^{3} {\alpha_{tz} } } $$
(22)

Subject to:

$$ \alpha_{t1} \le \frac{{\sum_{i = 1}^{I} {h_{it} \cdot Y_{it} } - LB(Z_{1} )_{t} }}{{UB(Z_{1} )_{t} - LB(Z_{1} )_{t} }},\alpha_{t2} \le \frac{{\sum_{i = 1}^{I} {h_{it} \cdot U_{it} } - LB(Z_{2} )_{t} }}{{UB(Z_{2} )_{t} - LB(Z_{2} )_{t} }}\quad \forall {\text{t}} \in {\text{T}} $$
(23)
$$ \alpha_{t3} \le \frac{{UB(Z_{3} )_{t} - \sum_{j = 1}^{J} {(f_{j} \cdot Z_{jt} + v_{j} \cdot X_{jt} )} }}{{UB(Z_{3} )_{t} - LB(Z_{3} )_{t} }}\quad \forall {\text{t}} \in {\text{T}} $$
(24)
$$ \upalpha_{\text{t1}} \ge\upalpha_{\text{t2}} \ge\upalpha_{\text{t3}} \quad \forall {\text{t}} \in {\text{T}} $$
(25)

and constraints (3)–(18), \( \upalpha_{\text{tz}} \in \left[ {0,1} \right] \) where denotes the satisfaction-level of tth period and zth fuzzy goal (Z1, Z2, Z3).

In weighted additive fuzzy goal programming (Tiwari et al. 1987) the objectives have different weights and importance which is denoted by \( \lambda_{z} \). WA-FGP-T model can be written as follows:

$$ {\text{Max}}\;\;\sum\limits_{t = 1}^{3} {\sum\limits_{z = 1}^{3} {\lambda_{z} } \alpha_{tz} } $$
(26)

and constraints (3)–(18), (23), (24). Also, \( \upalpha_{\text{tz}} \in \left[ {0,1} \right]. \)

5 Computational Experience

In this section, an example with random numbers is presented. Then, the proposed model is solved and evaluated. The example is presented with 30 points within [0, 45] by choosing random numbers and uniform distribution. In this example, in the first period, 5 transportation vehicles are allocated, and then 3 other vehicles are added in each following period. The model of the problem has been made by three FGP approaches as well as LMOLP approach. Based on the programming, in each one of the periods, the interval must be determined for each objective. In Table 1, the value of each objective in different periods have been shown, which are determined by decision-makers. Since the periods are dependent on each other, wrong decision on the intervals leads to a situation in which the problem cannot be solved. Also, by changing the intervals, the coverage priority of the population in different periods can be changed. In order to obtain the results, the problem is solved by lingo 11.0 optimization software. The results obtained by the solution of suggested model and approaches have been shown in Table 2.

Table 1 Aspiration levels of fuzzy goals
Full size table
Table 2 Results of the proposed model
Full size table

In LMOLP model, the initial coverage has been taken as the first objective with the highest priority, and the obtained value in the three periods is equal to 1,244,236 totally. The minimization of expenses in this method is the last priority. According to this solution, at the end of three periods, at least 7,688 units are expended in order to establish service centers. In order to show how initial coverage variable (which is fractional) affects coverage increase, the suggested model has been solved by LMOLP approach and the binary variable of y. In this condition, the maximum of initial coverage throughout the total of three periods is equal to 1,230,544, which shows a substantial reduction compared to the main model. So, when the initial coverage is taken fractionally, the model becomes more flexible and the maximum demand is covered. Although LMOLP is superior in initial coverage, the backup coverage throughout the total of periods is equal to 86,425, and only 6.25 % of the population has backup coverage, which is not satisfactory. Therefore, lexicographic multiple-objective linear programming which is based on absolute priority is not efficient in backup coverage.

In fuzzy approaches, the backup coverage is improved substantially, although there is a little decrease in initial coverage. According to the obtained results from FGP, the percentage of backup coverage in the total of periods is equal to 16.68 %, while the initial coverage is equal to 89.12 % totally. In other words, a 4.77 % decrease in initial coverage (from 93.89 to 89.12 %) leads to an improvement equal to 10.16 % (from 6.25 to 16.68 %). Compared to LMOLP method, the total of expenses of the three periods has decreased from 7,688 to 6,907. In WA-FGP-T approach, different weights show the relative importance of the goals. According to the obtained results, the WA-FGP-T approach leads to the best results among the different approaches. Programming for future demands can lead to the maximum coverage as well as a reduction in the expenses of stationing. It can be observed that in the first period, 25, 24, 19, 16, and 8 nodes were selected for five transportation vehicles. In the following period, two new stations have been created and other vehicle has been stationed in station 19. In the third period, only one new station has been created, and two other vehicles have been created in the previous established stations. In this way, this model can cover the maximum level of future demands based on the changes in the congestion and with the minimum amount of expenses. The A-FGP-C approach has a structure similar to LMOLP method, but the priorities are not absolute. Although this approach does not determine the priorities of the goals, it guarantees that a fuzzy goal with highest priority has been achieved with the highest level. The obtained results from this approach are similar to the obtained results from FGP1.

6 Conclusion and Future Researches

In this article, a dynamic multiple-objective fuzzy model of maximal covering location problem with gradual coverage radius has been presented. In addition to initial coverage, the backup coverage objective, fixed expenses of establishing stations and variable expenses of facility stationing have been taken into account. Taking the coverage radius as a gradual factor and taking the initial coverage as a fractional factor brings the model closer to reality. The efficiency of the model is evaluated by presenting an example with random numbers and its solution by different approaches. The obtained results show that the suggested model is closer to the reality when it is compared with other models. Also, the FGP approaches are more efficient for the solution of location problem. As the proposed model is highly complex, it is suggested that heuristic and meta-heuristic methods are developed for the solution of the problem in large scales. In addition to variable demands, other factors such as expenses can be taken as variables for future researches.