# A Triobjective Model for Locating a Public Semiobnoxious Facility in the Plane

Authors: José Fernández; Juana L. Redondo; Aránzazu G. Arrondo; Pilar M. Ortigosa
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

A new mathematical model for locating a single semiobnoxious facility in the plane is proposed. Three objectives are taken into consideration. The first one maximizes the efficiency of the service provided by the facility to some users, by minimizing the sum of weighted distances between the facility and those users. The second one minimizes the social cost caused by the undesirable effects produced by the facility, by minimizing the sum of the repulsions of the affected people (as they feel it). The third one aims to distribute the repulsions fairly (as equal as possible) among the affected people. To prove that the new model can be tackled in practice, two recent general-purpose multiobjective evolutionary algorithms, MOEA/D and FEMOEA, are suggested to obtain a discrete approximation of its Pareto-front. A computational study shows that both algorithms are suitable to cope with the problem.


---

## Body

## 1. Introduction

Location Models. Location science deals with the location of one or more facilities in a way that optimizes a certain objective, for example, minimization of transportation costs [1], minimization of social costs [2], minimization of the response time [3], and maximization of the profit obtained [4]. See [5–7] for an introduction to the topic. In fact, many location problems require taking more than one objective into account. The literature on multiobjective location problems is wide and varied (see, for instance, the review papers [8, 9] and the references therein). In this work we restrict ourselves to continuous problems, in which the facility can be located in any place within a given subset of the plane. Although most multiobjective location papers deal with discrete or network problems, we can find many papers on continuous problems as well (see, for instance [10–12], to name a few).In particular, in this paper, we deal with the location of a semiobnoxious or, in general, a semidesirable facility, that is, a facility that is perceived as desirable by some users (it offers a service to them) but undesirable by others (they receive a negative effect). Garbage dump sites, airports, train stations, chemical plants, and power plants are typical semidesirable facilities. As the welfare of negatively affected users decreases as the facility gets closer to them, they would like the facility to be sited as far as possible. However, this is against the wish of the positively affected users, who want the facility as close to them as possible. Although this naturally leads to bi- (or multi-) objective problems, some authors have afforded the problem using single-objective models, either by combining the negative and the positive objectives into a single one (as a kind of weighting method; see, for instance [13]) or by transforming one of the objectives into a constraint (as a kind of constrained method; see, for instance [14]).Concerning the multiobjective problems, more precisely the biobjective ones, the pull objective considered in all papers that we are aware of is the classical minisum objective, that is, minimization of the sum of weighted distances between the facility and the positively affected users. As for the push objective, the minimization of the sum of negative powers of distances, representing an aggregate undesirable effect, is considered in [15], the minimization of the sum of nonincreasing piecewise linear functions of the distance is employed in [16], and the maximization of the minimum distance, to take care of the worst case, is used in [17].The model introduced in this work also uses the minisum objective as pull objective but differs from existing studies in several aspects. Firstly, the push objective is given by the minimization of the sum of the repulsions as felt by the negatively affected people. To this aim, a nonlinear multimodal objective function introduced in [2] is used. Secondly, in addition to the pull and push objectives, anequity objective is also considered, which aims at distributing the undesirable effects fairly among all the negatively affected people. This is of special interest when locating public facilities, as the authorities in charge of deciding the location of the semidesirable facility may consider this third objective as important as the pull and push ones. Thirdly, the equity objective is new in literature, as it aims toequalize the undesirable effects, and not the distances (as is usually done in the literature dealing with the location of facilities with an equity objective). As far as we know, this is the first three-objective model for locating a semidesirable facility in the plane proposed in literature.Definitions. When dealing with multiobjective problems we need to clarify what “solving” a problem means. Some widely known definitions to explain the concept of optimality are given next. The interested reader is referred to [18] for a good introduction to (nonlinear) multiobjective optimization, where these and other definitions, as well as properties and some solution methods are detailed. The following general nonlinear multiobjective optimization problem will be considered:(1)
min
⁡
f
1
y
,
…
,
f
m
y
s.t.
y
∈
S
⊆
R
n
,where f
1
,
…
,
f
m
:
R
n
→
R are m real-valued functions and S is the feasible set. Let us denote by f
(
y
)
=
(
f
1
(
y
)
,
…
,
f
m
(
y
)
) the vector of objective functions and by Z
=
f
(
S
) the image of the feasible region.Definition 1.
A feasible vectory
∗
∈
S is said to beefficient if and only if there does not exist another feasible vector y
∈
S such that f
l
(
y
)
≤
f
l
(
y
∗
) for all l
=
1
,
…
,
m, and f
j
(
y
)
<
f
j
(
y
∗
) for at least one index j  (
j
∈
{
1
,
…
,
m
}). The set S
E of all the efficient points is called theefficient set orPareto-set. If y
1 and y
2 are two feasible points and f
l
(
y
1
)
≤
f
l
(
y
2
) for all l
=
1
,
…
,
m, with at least one of the inequalities being strict, then we say that y
1
dominates
y
2.Efficiency is defined in the decision space. The corresponding definition in the criterion space is as follows.Definition 2.
An objective vectorz
∗
=
f
(
y
∗
)
∈
Z is said to benondominated if and only if y
∗ is efficient. The set Z
N of all nondominated vectors is called thenondominated set orPareto-front. If y
1 and y
2 are two feasible points and y
1 dominates y
2, then we say that f
(
y
1
) dominates f
(
y
2
).Ideally, solving (1) means obtaining the whole efficient set, that is, all the points which are efficient, and its corresponding Pareto-front.Multiobjective Algorithms. For a majority of multiobjective problems, including location problems, it is not easy to obtain an exact description of the efficient set or Pareto-front, since those sets typically include an infinite number of points (usually a continuum set). The methods proposed in the literature with that purpose are specialized either in particular problems or for a particular type of multiobjective problems. To the extent of our knowledge, only two exactgeneral methods, namely, two interval branch-and-bound methods (see [11, 19]) have been proposed in literature which obtain an enclosure of those sets up to a prespecified precision. Specifically, they offer a list of boxes (multidimensional intervals) whose union contains the complete efficient set (and their images the corresponding Pareto-front) as a solution. However, they are time consuming. Furthermore, they have large memory requirements, so that only small instances can be solved with them. The reason for this lack of methods is that even obtaining a single efficient point of a nonlinear multiobjective problem can be a difficult task. That is why some authors have proposed to present to the decision-maker a good “representative set” of nondominated points which suitably represents the whole Pareto-front. By a good representative set we mean a discrete set of points covering the complete Pareto-front and evenly distributed over it.There is a plethora of metaheuristic methods with that purpose in literature. These include extensions of simulated annealing [20], tabu search [21], scatter search [22], ant systems [23], or particle swarm optimization [24], among others, to multiobjective programming. However, most of them are designed to deal with combinatorial MOPs (some exceptions are [21, 22]).Nonetheless, the most common approaches utilized in literature to cope with (1) is the use of multiobjective evolutionary algorithms (MOEAs). This is due to their ability to find multiple efficient solutions in one single simulation run. The numerous proposed variants have been surveyed, for instance, in [25]. Among them, the algorithms NSGA-II [26] and SPEA2 [27] have been the reference algorithms in the multiobjective evolutionary computation community for years. However, during the last five years, the multiobjective evolutionary algorithm based on decomposition MOEA/D [28] has proved to be superior to other state-of-the-art algorithms (including both NSGA-II and SPEA2) when applied to a wide variety of multiobjective benchmark problems [29]. MOEA/D will be used in this paper to solve the triobjective location model, and also the recently proposed FEMOEA algorithm [30], which has been successfully applied to other biobjective location problems (see, for instance [31]).The rest of the paper is organized as follows. Our new triobjective location model is introduced in the following section, where special subsections are devoted to each of its objectives. In order to show that the problem can be tackled with the aforementioned algorithms, a computational study is performed in Section3. The quality of the approximation sets offered by MOEA/D and FEMOEA is investigated with the help of severalquality indicators. In Section 4, our main conclusions are summarized and the research issues that we believe to be worth exploring in the future are highlighted.


## 2. The Model

A semiobnoxious or semidesirable facility is going to be located in a region of the planeF
⊆
R
2, where there is a set of points (cities, customers, demand points, etc.) that will interact with it. Due to the characteristics of the facility, some of those points perceive the facility as attractive, whereas other points perceive it as undesirable. Let A
+ be the set of points for which the new facility is attractive and A
- the set of points for which the new facility is undesirable. Notice that A
+
∩
A
- may be a nonempty set. Let w
a
+ be a weight related to the importance of point a
∈
A
+, and, similarly, let w
a
- be a weight measuring the importance of point a
∈
A
-. For a point a
∈
A
+
∩
A
-, the weights w
a
+ and w
a
- may be equal or different, depending on the problem.Let us denote byx
=
(
x
1
,
x
2
) the location of the new facility and by d
+
(
a
,
x
) (resp., d
-
(
a
,
x
)) the distance between the facility and the point a
∈
A
+ (resp., a
∈
A
-). Function d
+ measures the distances in accordance with the factors that make the facility attractive, whereas d
- does it in accordance with the factors that make it undesirable. Again, for a point a
∈
A
+
∩
A
-, functions d
+ and d
- may be equal or different. For instance, if the attraction that a
∈
A
+ feels for x decreases with the travel distance between them, then d
+ may be adistance predicting function (see [32]). On the other hand, if the undesirability of the facility is due to the air pollution it causes, then d
- may be given by an elliptic distance metric to reflect the impact of wind in the distribution of pollution (see [33]).In this paper we consider, in particular, the case of a facility which has to provide a service to all the points ina
∈
A
+, such that the cost of providing this service is mainly due to the distance between the facility and the points. We also assume that the disutility produced by the facility at the points a
∈
A
- is related to the distance and that its undesirable effects do not endanger peoples’ lives. Some examples of these kinds of facilities may be a garbage dump or a sewage treatment plant.


### 2.1. Maximizing Efficiency

The first objective of the model is aimed at maximizing the efficiency of the service provided by the facility. If we assume that the cost of providing the service to the points is given by the distance between the facility and the points (or alternatively that the quality of the service decreases as the distance increases), then we can consider that the first objective of the problem is the classical minisum one, where one seeks to minimize the sum of weighted distances from the facility to the demand points that perceive it as attractive. Mathematically, it is given by(2)
min
⁡
f
1
x
=
∑
a
∈
A
+
w
a
+
d
+
a
,
x
,and it is the most widely used criterion in facility location. d
+ should be given by a distance predicting function [32].


### 2.2. Minimizing Social Cost

We can find several papers dealing with the location of undesirable facilities in literature. See, for instance, the review papers [8, 34] and the references therein. Maximin models, whose objective is to maximize the minimum distance between the points a
∈
A
- and the facility, are the most studied. However, such an objective is usually more suited for noxious facilities, which, in case of an accident, may endanger people’s health or the environment (such as a nuclear or a chemical plant).In this paper we follow [2], where the case of the location of a nonnoxious undesirable facility is considered. To model the total repulsion of the inhabitants at a point a
∈
A
- against the location of the facility at x as they perceive it, the use of the function, (3)
trp
a
,
x
=
w
a
-
1
1
+
exp
⁡
α
a
+
β
a
d
-
a
,
x
,is proposed, where α
a
∈
R and β
a
∈
R
+ are two parameters to be estimated for every demand point a. The lower the value of α
a, the higher the repulsion of the inhabitants to the location of the facility near their city or its outlying areas, and the higher the value of β
a, the faster the change in opinion from considering a distance nonacceptable to acceptable. So, many types of repulsions can be modelled with the function t
r
p, just by choosing the right α
a and β
a values (see Figure 1). Observe that when the facility is located far enough from the point a the repulsion decreases to zero. In order to choose a distance function d
- we must bear in mind that what is wanted is to measure the repulsion of the inhabitants to the facility as they feel it. In this way the model should use a distance function which measures distances as people perceive them. What people usually know are the distances between some pairs of cities which they have learnt either by their own experience going from one city to another or by reading the kilometres written on a road-sign or roadmap. Hence, the best choice is to fit a distance predicting function again.Figure 1
Shape oft
r
p
(
a
,
x
) depending on the value of the parameters. w
a
-
=
1 in all the cases.The second objective of our model is to minimize the global repulsion of the inhabitants of the geographical regionF against the location of the facility as they feel it, as given by (4)
min
⁡
f
2
x
=
∑
a
∈
A
-
trp
x
,
a
.Since it is assumed that the undesirable effects the facility provokes do not endanger people’s lives, the minimization of thesum of the total repulsions is better than the minimization of theirmaximum.Notice that if the feasible set was unbounded, the optimal solution of a single-objective problem with a push objective would be at infinity. That is why these types of problems always assume a bounded feasible set or include constraints that make it a bounded set.


### 2.3. Maximizing Equity

Since the facility is undesirable for the pointsa
∈
A
-, its location may provoke a smaller rejection if those points perceive that they are all equally affected, that is, the fact that the relative distribution of the undesirable effects is fair. In fact, this is on its own one of the objectives that authorities wish to achieve when locating public facilities. This suggests including an equity objective in the model. Equity is, essentially, an abstract concept that implies fairness and justice. Although equity is a broader concept than (in)equality (the latter refers to the state of several measurements having the same value), equity is usually quantified with the so-calledinequality measures, to be minimized. Many and diverse measures have been proposed in literature to gauge the level of inequality (as a proxy for equity) in facility location alternatives. In their review, Marsh and Schilling [35] analysed up to 20 different measures.But which measure is to be used? In order to try to answer this question, some authors have mentioned criteria that should be considered when selecting an inequality measure. Among them, the Pigou-Daltonprinciple of transfers is the most widely accepted one, and it is regarded by economists as a mandatory requirement for adequate measures of equity [36], a point of view we follow here. It establishes that the value of the inequality measure decreases as the difference in effects between any two points decreases. Another common assumption is thescale invariance [37]. Interestingly, most of the inequality measures used or proposed in locational analysis literature do not satisfy those two criteria. Among the ones that satisfy them we have the coefficient of variation and the Gini index [38]. The latter is the most commonly accepted one by economists to describe income distributions, and it has also been analysed in the location context [37], though only in [39] in a continuous setting, as we do in this paper.We also use the Gini index in this paper, but in a different way. In locational analysis literature, when an inequality measure is used, it is always with the aim of equalizing the (maybe weighted) distances{
d
+
(
a
,
x
)
:
a
∈
A
+
}, as it is assumed that the distances determine the desirability of the facility. However, our aim is to equalize the total repulsions {
t
r
p
(
a
,
x
)
:
a
∈
A
-
} against the new facility, as we want a fair distribution of the undesirable effects, and the degree of the rejection varies with the distance as measured by the total repulsion t
r
p
(
a
,
x
). Hence, the third objective of the model is (5)
min
⁡
f
3
x
=
∑
a
∈
A
-
∑
a
′
∈
A
-
trp
a
,
x
-
trp
a
′
,
x
2
A
-
2
trp
¯
,where t
r
p
¯
=
(
∑
a
∈
A
-
‍
t
r
p
(
x
,
a
)
)
/
|
A
-
| is the mean of total repulsions.As with push objectives, the optimal solution of an unconstrained single-objective problem with an equity objective would be at infinity. Hence, these types of problems also include constraints to make the feasible set bounded.Then, the triobjective problem is given by(6)
min
⁡
f
x
=
f
1
x
,
f
2
x
,
f
3
x
s.t.
x
∈
F
,where F
⊂
R
2 is a bounded set. As far as we know, this is the first triobjective optimization model for locating a semidesirable facility in the plane proposed in literature. This lack of models (even biobjective models are rather scarce) is in part due to the difficulty of designing specialized algorithms for obtaining (an approximation of) its efficient set and its corresponding Pareto-front. However, as it will be shown in the next section, existing meta-heuristics, in particular multiobjective evolutionary algorithms, can do the job quite efficiently.


### 2.4. A Numerical Example

In order to show how our model works, next we apply it to a quasi-real example dealing with the location of a big landfill around the city of Murcia, in South-Eastern Spain. The city of Murcia is the capital of the Autonomous Region of Murcia (A.R.M.), a province with 11314 km2 and over one million inhabitants. More than half of the inhabitants of A.R.M. live in the city of Murcia or in the villages close to it. A square centred in Murcia with an edge 45 km long was considered as the feasible set in this example. This choice was motivated by two concerns. On the one hand, as all the cities will have to carry their garbage to the landfill (maybe through transfer stations), a bigger region would increase the transportation costs too much. On the other hand, in the region at hand, increasing the length of the edge to 55 km increases the number of covered inhabitants only slightly, whereas reducing the length to 35 km decreases it considerably. But other feasible sets could have been considered as well. 557746 inhabitants of A.R.M. and 74812 inhabitants from the neighbouring province of Alicante live within the considered square. These 632558 inhabitants form our set of people concerned with the location of the landfill. They are distributed over 71 population centres, with population varying between 1138 and 178013 inhabitants. In this study we have considered each population centre a to belong both to A
- (as nobody wants the landfill close to it) and to A
+ (as nobody wants the landfill too far away, in order not to have to pay too much due to the transportation costs), with w
a
-
=
w
a
+ proportional to the population of a (one unit per 17800 inhabitants). Their position and population can be seen in Figure 2: each demand point is shown as a yellow circle whose radius is proportional to the population. In fact, those circles are forbidden zones where the location of the new facility is not allowed, as the location of the new facility too close to a population centre will provoke the reaction of its inhabitants against the facility.Figure 2
Efficient sets and Pareto-fronts of biobjective problems and efficient set and projections of the Pareto-front of the triobjective problem.Approximate values for the parametersα
a and β
a (the same pair of values has been used for all the cities) were obtained through a small survey carried out via e-mail among teachers and students of the University of Murcia. People were asked about the minimum distance from home at which they would like the landfill to be sited, and also the minimum distance from home at which they would allow the location of the landfill (as it is a facility needed for the community). Using 192 answers received, some mathematical transformations, and statistical regression, the following values were obtained: α
a
=
-
2.91972 and β
a
=
0.30146 (for more details the interested reader is referred to [40]). As for the function used to measure distances, the same distance predicting function l
b
1
,
b
2
(
x
,
a
)
=
b
1
(
x
1
-
a
1
)
2
+
b
2
(
x
2
-
a
2
)
2 was used for both d
-
(
x
,
a
) and d
+
(
x
,
a
), with parameters b
1
=
1.760 and b
2
=
1.373 and axes rotated 7
5
° with regard to the true North-South-East-West (see [32]).In Figure2 the results for the problem, as obtained using the FEMOEA algorithm (see Section 3.1), are depicted. In first row we can see, from left to right, the efficient set when only two objectives, f
1 and f
2, are considered, P
S
12; then the corresponding Pareto-front, P
F
12; and, finally, the projection onto the f
1
f
2-image space of the three-dimensional Pareto-front obtained when considering the three objectives, P
r
o
j
12
(
P
F
). The second row gives similar pictures, but when the objectives f
1 and f
3 are considered. The third row corresponds to the objectives f
2 and f
3. The gray scale used to draw both P
S
a
b and P
F
a
b (the same scale for both pictures) allow us to see the part of the efficient set where a better f
a value is obtained (in light grey) as well as the part where a better f
b value is obtained (in dark gray), when the objectives f
a and f
b are considered, as well as the trade-off between both objectives. In the fourth row of Figure 2 the efficient set P
S
123 of problem (6), that is, considering the three objectives simultaneously, is shown.As we can see,P
S
123 strictly contains the union of the other Pareto-sets; thus, considering the three objectives provides other efficient regions not covered by the biobjective problems. Accordingly, we can see that the projection P
r
o
j
a
b
(
P
F
) always contains the Pareto-front P
F
a
b of the corresponding biobjective problem. This clearly confirms that the triobjective problem (6) differs from the three biobjective problems that can be generated by choosing two of the three objective functions. Notice that although some of the points in P
r
o
j
a
b
(
P
F
) are dominated when considering the problem with two objectives, those points are efficient when considering the three objectives simultaneously.Notice also that the efficient set and the Pareto-front of both the biobjective and triobjective problems may have an arbitrary shape, they can be even disconnected (see, for instance,P
S
12 and P
F
12). This clearly shows the difficulty of the problem we are dealing with.In order to show that our model captures the semiobnoxiousness of the facility differently from other existing models, as an example, we have solved the same problem using two models suggested in the literature: in [15] the social cost to be minimized is given by the sum of negative powers of distances (in our computations we have assumed the negative power to be equal to 2), whereas in [17] the maximization of the minimum distance is employed. In both models the pull objective is the classical minisum one, as in our model. In Figure 3 we can see the corresponding efficient sets, which have also been obtained using FEMOEA. As can be seen, the efficient sets obtained by those models differ clearly from the one provided by our model. In fact, none of those efficient sets is contained in the efficient set provided by the triobjective model (see the bottom picture of Figure 2).Figure 3
Efficient sets of the biobjective problems in [15] (a) and [17] (b).
(a)
(b)


## 2.1. Maximizing Efficiency

The first objective of the model is aimed at maximizing the efficiency of the service provided by the facility. If we assume that the cost of providing the service to the points is given by the distance between the facility and the points (or alternatively that the quality of the service decreases as the distance increases), then we can consider that the first objective of the problem is the classical minisum one, where one seeks to minimize the sum of weighted distances from the facility to the demand points that perceive it as attractive. Mathematically, it is given by(2)
min
⁡
f
1
x
=
∑
a
∈
A
+
w
a
+
d
+
a
,
x
,and it is the most widely used criterion in facility location. d
+ should be given by a distance predicting function [32].


## 2.2. Minimizing Social Cost

We can find several papers dealing with the location of undesirable facilities in literature. See, for instance, the review papers [8, 34] and the references therein. Maximin models, whose objective is to maximize the minimum distance between the points a
∈
A
- and the facility, are the most studied. However, such an objective is usually more suited for noxious facilities, which, in case of an accident, may endanger people’s health or the environment (such as a nuclear or a chemical plant).In this paper we follow [2], where the case of the location of a nonnoxious undesirable facility is considered. To model the total repulsion of the inhabitants at a point a
∈
A
- against the location of the facility at x as they perceive it, the use of the function, (3)
trp
a
,
x
=
w
a
-
1
1
+
exp
⁡
α
a
+
β
a
d
-
a
,
x
,is proposed, where α
a
∈
R and β
a
∈
R
+ are two parameters to be estimated for every demand point a. The lower the value of α
a, the higher the repulsion of the inhabitants to the location of the facility near their city or its outlying areas, and the higher the value of β
a, the faster the change in opinion from considering a distance nonacceptable to acceptable. So, many types of repulsions can be modelled with the function t
r
p, just by choosing the right α
a and β
a values (see Figure 1). Observe that when the facility is located far enough from the point a the repulsion decreases to zero. In order to choose a distance function d
- we must bear in mind that what is wanted is to measure the repulsion of the inhabitants to the facility as they feel it. In this way the model should use a distance function which measures distances as people perceive them. What people usually know are the distances between some pairs of cities which they have learnt either by their own experience going from one city to another or by reading the kilometres written on a road-sign or roadmap. Hence, the best choice is to fit a distance predicting function again.Figure 1
Shape oft
r
p
(
a
,
x
) depending on the value of the parameters. w
a
-
=
1 in all the cases.The second objective of our model is to minimize the global repulsion of the inhabitants of the geographical regionF against the location of the facility as they feel it, as given by (4)
min
⁡
f
2
x
=
∑
a
∈
A
-
trp
x
,
a
.Since it is assumed that the undesirable effects the facility provokes do not endanger people’s lives, the minimization of thesum of the total repulsions is better than the minimization of theirmaximum.Notice that if the feasible set was unbounded, the optimal solution of a single-objective problem with a push objective would be at infinity. That is why these types of problems always assume a bounded feasible set or include constraints that make it a bounded set.


## 2.3. Maximizing Equity

Since the facility is undesirable for the pointsa
∈
A
-, its location may provoke a smaller rejection if those points perceive that they are all equally affected, that is, the fact that the relative distribution of the undesirable effects is fair. In fact, this is on its own one of the objectives that authorities wish to achieve when locating public facilities. This suggests including an equity objective in the model. Equity is, essentially, an abstract concept that implies fairness and justice. Although equity is a broader concept than (in)equality (the latter refers to the state of several measurements having the same value), equity is usually quantified with the so-calledinequality measures, to be minimized. Many and diverse measures have been proposed in literature to gauge the level of inequality (as a proxy for equity) in facility location alternatives. In their review, Marsh and Schilling [35] analysed up to 20 different measures.But which measure is to be used? In order to try to answer this question, some authors have mentioned criteria that should be considered when selecting an inequality measure. Among them, the Pigou-Daltonprinciple of transfers is the most widely accepted one, and it is regarded by economists as a mandatory requirement for adequate measures of equity [36], a point of view we follow here. It establishes that the value of the inequality measure decreases as the difference in effects between any two points decreases. Another common assumption is thescale invariance [37]. Interestingly, most of the inequality measures used or proposed in locational analysis literature do not satisfy those two criteria. Among the ones that satisfy them we have the coefficient of variation and the Gini index [38]. The latter is the most commonly accepted one by economists to describe income distributions, and it has also been analysed in the location context [37], though only in [39] in a continuous setting, as we do in this paper.We also use the Gini index in this paper, but in a different way. In locational analysis literature, when an inequality measure is used, it is always with the aim of equalizing the (maybe weighted) distances{
d
+
(
a
,
x
)
:
a
∈
A
+
}, as it is assumed that the distances determine the desirability of the facility. However, our aim is to equalize the total repulsions {
t
r
p
(
a
,
x
)
:
a
∈
A
-
} against the new facility, as we want a fair distribution of the undesirable effects, and the degree of the rejection varies with the distance as measured by the total repulsion t
r
p
(
a
,
x
). Hence, the third objective of the model is (5)
min
⁡
f
3
x
=
∑
a
∈
A
-
∑
a
′
∈
A
-
trp
a
,
x
-
trp
a
′
,
x
2
A
-
2
trp
¯
,where t
r
p
¯
=
(
∑
a
∈
A
-
‍
t
r
p
(
x
,
a
)
)
/
|
A
-
| is the mean of total repulsions.As with push objectives, the optimal solution of an unconstrained single-objective problem with an equity objective would be at infinity. Hence, these types of problems also include constraints to make the feasible set bounded.Then, the triobjective problem is given by(6)
min
⁡
f
x
=
f
1
x
,
f
2
x
,
f
3
x
s.t.
x
∈
F
,where F
⊂
R
2 is a bounded set. As far as we know, this is the first triobjective optimization model for locating a semidesirable facility in the plane proposed in literature. This lack of models (even biobjective models are rather scarce) is in part due to the difficulty of designing specialized algorithms for obtaining (an approximation of) its efficient set and its corresponding Pareto-front. However, as it will be shown in the next section, existing meta-heuristics, in particular multiobjective evolutionary algorithms, can do the job quite efficiently.


## 2.4. A Numerical Example

In order to show how our model works, next we apply it to a quasi-real example dealing with the location of a big landfill around the city of Murcia, in South-Eastern Spain. The city of Murcia is the capital of the Autonomous Region of Murcia (A.R.M.), a province with 11314 km2 and over one million inhabitants. More than half of the inhabitants of A.R.M. live in the city of Murcia or in the villages close to it. A square centred in Murcia with an edge 45 km long was considered as the feasible set in this example. This choice was motivated by two concerns. On the one hand, as all the cities will have to carry their garbage to the landfill (maybe through transfer stations), a bigger region would increase the transportation costs too much. On the other hand, in the region at hand, increasing the length of the edge to 55 km increases the number of covered inhabitants only slightly, whereas reducing the length to 35 km decreases it considerably. But other feasible sets could have been considered as well. 557746 inhabitants of A.R.M. and 74812 inhabitants from the neighbouring province of Alicante live within the considered square. These 632558 inhabitants form our set of people concerned with the location of the landfill. They are distributed over 71 population centres, with population varying between 1138 and 178013 inhabitants. In this study we have considered each population centre a to belong both to A
- (as nobody wants the landfill close to it) and to A
+ (as nobody wants the landfill too far away, in order not to have to pay too much due to the transportation costs), with w
a
-
=
w
a
+ proportional to the population of a (one unit per 17800 inhabitants). Their position and population can be seen in Figure 2: each demand point is shown as a yellow circle whose radius is proportional to the population. In fact, those circles are forbidden zones where the location of the new facility is not allowed, as the location of the new facility too close to a population centre will provoke the reaction of its inhabitants against the facility.Figure 2
Efficient sets and Pareto-fronts of biobjective problems and efficient set and projections of the Pareto-front of the triobjective problem.Approximate values for the parametersα
a and β
a (the same pair of values has been used for all the cities) were obtained through a small survey carried out via e-mail among teachers and students of the University of Murcia. People were asked about the minimum distance from home at which they would like the landfill to be sited, and also the minimum distance from home at which they would allow the location of the landfill (as it is a facility needed for the community). Using 192 answers received, some mathematical transformations, and statistical regression, the following values were obtained: α
a
=
-
2.91972 and β
a
=
0.30146 (for more details the interested reader is referred to [40]). As for the function used to measure distances, the same distance predicting function l
b
1
,
b
2
(
x
,
a
)
=
b
1
(
x
1
-
a
1
)
2
+
b
2
(
x
2
-
a
2
)
2 was used for both d
-
(
x
,
a
) and d
+
(
x
,
a
), with parameters b
1
=
1.760 and b
2
=
1.373 and axes rotated 7
5
° with regard to the true North-South-East-West (see [32]).In Figure2 the results for the problem, as obtained using the FEMOEA algorithm (see Section 3.1), are depicted. In first row we can see, from left to right, the efficient set when only two objectives, f
1 and f
2, are considered, P
S
12; then the corresponding Pareto-front, P
F
12; and, finally, the projection onto the f
1
f
2-image space of the three-dimensional Pareto-front obtained when considering the three objectives, P
r
o
j
12
(
P
F
). The second row gives similar pictures, but when the objectives f
1 and f
3 are considered. The third row corresponds to the objectives f
2 and f
3. The gray scale used to draw both P
S
a
b and P
F
a
b (the same scale for both pictures) allow us to see the part of the efficient set where a better f
a value is obtained (in light grey) as well as the part where a better f
b value is obtained (in dark gray), when the objectives f
a and f
b are considered, as well as the trade-off between both objectives. In the fourth row of Figure 2 the efficient set P
S
123 of problem (6), that is, considering the three objectives simultaneously, is shown.As we can see,P
S
123 strictly contains the union of the other Pareto-sets; thus, considering the three objectives provides other efficient regions not covered by the biobjective problems. Accordingly, we can see that the projection P
r
o
j
a
b
(
P
F
) always contains the Pareto-front P
F
a
b of the corresponding biobjective problem. This clearly confirms that the triobjective problem (6) differs from the three biobjective problems that can be generated by choosing two of the three objective functions. Notice that although some of the points in P
r
o
j
a
b
(
P
F
) are dominated when considering the problem with two objectives, those points are efficient when considering the three objectives simultaneously.Notice also that the efficient set and the Pareto-front of both the biobjective and triobjective problems may have an arbitrary shape, they can be even disconnected (see, for instance,P
S
12 and P
F
12). This clearly shows the difficulty of the problem we are dealing with.In order to show that our model captures the semiobnoxiousness of the facility differently from other existing models, as an example, we have solved the same problem using two models suggested in the literature: in [15] the social cost to be minimized is given by the sum of negative powers of distances (in our computations we have assumed the negative power to be equal to 2), whereas in [17] the maximization of the minimum distance is employed. In both models the pull objective is the classical minisum one, as in our model. In Figure 3 we can see the corresponding efficient sets, which have also been obtained using FEMOEA. As can be seen, the efficient sets obtained by those models differ clearly from the one provided by our model. In fact, none of those efficient sets is contained in the efficient set provided by the triobjective model (see the bottom picture of Figure 2).Figure 3
Efficient sets of the biobjective problems in [15] (a) and [17] (b).
(a)
(b)


## 3. Computational Studies

Anygood mathematical model that cannot be solved in practice is auseless model. In this section we show that the model introduced in the previous section can indeed be solved via multiobjective evolutionary algorithms.


### 3.1. Algorithms

MOEA/D is a generic, evolutionary multiobjective optimization algorithm based on decomposition. It first uses a decomposition method to decompose a multiobjective optimization problem into a number of scalar optimization problems. Then, an evolutionary algorithm is employed to optimize these subproblemssimultaneously. Each individual solution in the population of MOEA/D is associated to a subproblem. A neighbourhood relationship among all the subproblems is defined based on the distances of their weight vectors. In MOEA/D, optimization of a subproblem uses the current information of its neighbouring subproblems since two neighbouring subproblems should have close optimal solutions. See [28, 29] for more details on the algorithm. It will be one of the algorithms used in our study.The other one is FEMOEA. It is also a generic, multiobjective evolutionary algorithm, but based onspecies. A species is mainly defined by a centre and a radius. The centre is a solution and the radius is a positive number which determines the subregion of the search space covered by that species. The main aim of the radius is to focus the searching operators on the corresponding subregions. At each stage of the algorithm, several species with different radii can coexist simultaneously. The use of different radii throughout the optimization process allows, on the one hand, identifying regions in the search space with high quality solutions and, on the other hand, to not waste too much time on regions of the search space which are either already explored or do not provide high quality solutions. Additionally, FEMOEA includes a local method which accelerates the convergence of the population towards the optimal Pareto-front. Basically, this method is an extension of the local optimizer SASS [41] and improves a given solution along a search direction (no gradient information is used). Finally, unlike the termination criteria of most MOEAs in literature, which is usually based on a number of function evaluations, FEMOEA incorporates a stopping rule which establishes that the algorithm will finish if during three consecutive iterations, the changes experimented in the candidate Pareto-front are negligible (in terms of the objective function values), for a given tolerance. To know how far two sets are from each other, a modified Hausdorff distance is proposed.The version of MOEA/D used in the studies, obtained from jMetal [42], is coded in Java, while the algorithm FEMOEA has been implemented in C++. The parameters used for MOEA/D are those proposed in [29], while the ones considered by FEMOEA are those recommended in [31]. For both algorithms and all the instances, the number M of points in the set approximating the Pareto-front has been set to 300. Notice that this is also the number of points in the population set for both algorithms.Since the analyzed algorithms are stochastic heuristics, every particular instance has been run five times by each algorithm. The value of the quality indicator considered for a given problem is the average over the five runs. Additionally, notice that due to the termination criteria of FEMOEA, each particular instance may require a different number of function evaluations. Then, in order to carry out the comparison as fair as possible, the number of function evaluations used by MOEA/D has been modified for each particular problem by fixing it to the average number of evaluations performed by FEMOEA in the five runs.


### 3.2. Problems

In order to have an overall view of the performance of the algorithms, different types of problems have been generated, varying the total number of demand points,|
A
+
∪
A
-
|, the number of demand points which feel repulsion, |
A
-
|, and the number of demand points which feel attraction, |
A
+
|. More precisely, three different values of |
A
+
∪
A
-
| were considered; that is, |
A
+
∪
A
-
|
=
25,100,500. For each value, 10 instances were generated by randomly choosing the parameters of the problems uniformly within predefined intervals: a
∈
(
[
0,10
]
,
[
0,10
]
),w
a
+
,
w
a
-
∈
[
1,10
],α
a
∈
[
-
5,1
]
,
β
a
∈
[
1,6
], and d
+
(
a
,
x
)
=
d
-
(
a
,
x
)
=
(
b
1
a
(
x
1
-
a
1
)
2
+
b
2
a
(
x
2
-
a
2
)
2
)
1
/
2 with b
1
a
,
b
2
a
∈
[
1,2.5
] (see [43]). The searching space proposed was (
[
0,10
]
,
[
0,10
]
) for all the problems. Besides, for each instance, both |
A
-
| and |
A
+
| values were also randomly computed, so that A
+
∩
A
- includes at least 65% of the points of A
+
∪
A
- and at most 85% of them. Each particular instance will be represented by (
|
A
+
∪
A
-
|
,
|
A
-
|
,
|
A
+
|
) throughout this work.


### 3.3. Quality Indicators

To measure the quality of the sets offered by the algorithms at approximating the Pareto-front, severalquality indicators from literature have been utilized. They map each Pareto-front approximation to a number, which can then be easily compared. Three quality indicators have been considered in this study, namely, the hypervolume, the additive epsilon indicator, and the spread, that will be explained later.Lets assume that we want to compare the quality of the outcomes generated byQ stochastic algorithms (Q
=
2 in our study). For each algorithm q, q
∈
{
1
,
…
,
Q
}, e
q runs are performed (e
q
=
5 in our study), generating the approximation sets P
S
1
q
,
…
,
P
S
e
q
q (in the decision space). Let us denote by S
P
S the set of all the approximation sets of the Pareto-set, S
P
S
=
{
P
S
1
1
,
…
,
P
S
e
1
1
,
…
,
P
S
1
Q
,
…
,
P
S
e
Q
Q
}.In some of the indicators listed below the approximation sets of the Pareto-front need to be compared to thetrue Pareto-front. However, the true Pareto-front is not usually known or cannot be completely obtained. Then, areference set
R
S which approximates the true Pareto-front is used instead. In our studies, the reference set R
S has been obtained as follows. All the approximation sets in S
P
S are combined, and then the dominated points are removed from this union. The image of the remaining points forms the reference set.Furthermore, normalized objective values are used to allow different objectives to contribute equally to comparative indicator values. The standard normalization is(7)
f
l
y
′
=
f
l
y
-
f
l
min
⁡
f
l
max
⁡
-
f
l
min
⁡
,where f
l
(
m
i
n
) (resp., f
l
(
m
a
x
)) denotes the minimum (resp., maximum) value of f
l when considering all the solutions in S
P
S.The most commonly used quality indicator in literature ishypervolume [44], which measures the hypervolume of the portion of the criterion space that is weakly dominated by the approximation set. The higher the hypervolume, the better the approximation. In order to measure this quantity, a reference point that is dominated by all points is needed. For a given problem, the same reference point has to be used for all the algorithms and all the runs. In our computational studies, the point whose lth component is the maximum of all the lth components of points in f
(
S
P
S
) is considered. It is an approximation of the Nadir point obtained when considering all the approximations of the Pareto-front together. The computation of thehypervolume metric has been depicted in Figure 4, although, for the sake of simplicity, the biobjective case has been represented.Figure 4
Computation of the hypervolume value for an approximation set with two objectives.Hypervolume can be thought of as aglobal quality indicator, in the sense that it assesses the approximation set as a whole. On the other hand,proximity indicators somehow measure the distance between the approximation set and the reference set. In this paper, we have used theunary additive epsilon indicator [45]. For an approximation of a Pareto-set, P
S, it is computed as (8)
I
ϵ
+
f
PS
=
min
ϵ
∈
R
⁡
∀
z
∈
RS
∃
a
∈
PS
:
f
l
a
-
f
l
m
i
n
f
l
m
a
x
-
f
l
m
i
n
-
ϵ
≤
z
l
-
f
l
m
i
n
f
l
m
a
x
-
f
l
m
i
n
∀
l
∈
1
,
…
,
mand gives the minimum distance by which f
(
P
S
) needs to be translated in each dimension in objective space such that R
S is weakly dominated by it. See Figure 5 for a graphic representation about the computation of the I
ϵ
+ indicator (again for the biobjective case).Figure 5
Computation of the epsilon indicator for an approximation set with two objectives.Besides, anevenness/diversity indicator, the well-knownspread [22, 26], is used in the studies. It is computed as (9)
Δ
f
PS
=
∑
l
=
1
m
d
f
l
m
i
n
,
f
PS
+
∑
sp
∈
PS
d
f
sp
,
f
PS
-
d
¯
∑
l
=
1
m
d
f
l
m
i
n
,
f
PS
+
PS
·
d
¯
,where (10)
d
f
sp
,
f
PS
=
min
s
p
∗
∈
PS
,
s
p
∗
≠
sp
⁡
f
sp
′
-
f
s
p
∗
′
2
,
d
¯
=
1
PS
∑
sp
∈
PS
d
f
sp
,
f
PS
.
·
2 denotes the Euclidean distance and f
y
′
=
(
f
1
y
′
,
…
,
f
m
y
′
). If the solutions in the approximation set P
S are well distributed and include the extreme solutions, Δ
(
f
(
P
S
)
)
=
0. Figure 6 depicts two approximation sets for a biobjective problem. The figure on the left hand depicts a better distributed Pareto-front as compared to the one on the right side. Therefore, the spread measure will be smaller for the Pareto-front on the left.Figure 6
Representation of two approximation sets for a biobjective problem. The Pareto-front on the left is better distributed and, hence, it will have a smaller spread value than the one on the right.
(a)
(b)


### 3.4. Comparative Study

All the computational studies in this paper have been run in the supercomputer Bullxual at the University of Almería, Spain, which is a cluster with 18 nodes. Each node has 16 cores (Intel Xeon E5 2650) and 64 GB of memory and 128 GB of solid-state drive. The whole supercomputer has 288 cores, 1151 GB of memory and 2304 GB of SSD. In our computational studies, each problem was run in one of the cores of the nodes (one problem at a time).Table1 summarizes thehypervolume average results obtained by both FEMOEA and MOEA/D for each particular instance. The final row refers to the average value, considering all the problems. As can be seen, FEMOEA obtains the highest hypervolume (highlighted with a bold font) for all the problems. Notice, however, that the results obtained by MOEA/D are also competitive (in average, the hypervolume values are 16.98% smaller). In the same table the CPU times employed by both algorithms, in seconds, are reported. As we can see, in average, MOEA/D is 11.21% quicker than FEMOEA.Table 1
Average hypervolume values and average computing time (in seconds). MOEA/D was run with the same number of functions evaluations as FEMOEA.
Problem
FEMOEA
MOEA/D
FEMOEA
MOEA/D
Av. (hyper)
Av. (hyper)
Av. (time)
Av. (time)
(25, 24, 18)
0.91196
0.78084
76
52
(25, 21, 24)
1.15776
1.06012
115
97
(25, 21, 23)
1.22557
1.04957
98
64
(25, 22, 20)
0.99244
0.67305
103
71
(25, 22, 21)
1.16561
1.07470
98
63
(25, 21, 20)
1.26344
1.26117
105
79
(25, 23, 20)
1.27525
1.26033
79
56
(25, 24, 18)
1.05399
0.98118
116
76
(25, 17, 24)
0.98886
0.85612
65
38
(25, 24, 20)
1.08105
1.03254
73
58
(100, 75, 93)
0.90985
0.74924
845
629
(100, 90, 92)
0.97463
0.81445
1020
786
(100, 94, 84)
0.98315
0.82334
1321
813
(100, 96, 75)
1.04997
0.81953
1562
1330
(100, 82, 92)
0.82064
0.63769
789
699
(100, 75, 92)
1.12490
0.83296
658
544
(100, 85, 90)
1.13659
1.08949
958
749
(100, 75, 93)
1.11774
1.04373
712
541
(100, 67, 98)
1.00772
0.51032
456
374
(100, 90, 87)
0.83631
0.70375
954
769
(500, 347, 493)
0.99370
0.70744
24617
20514
(500, 436, 474)
0.85810
0.69633
35326
31285
(500, 406, 484)
0.46998
0.43240
33409
32257
(500, 438, 417)
0.80063
0.68276
34606
31438
(500, 482, 388)
0.84188
0.63235
41099
36998
(500, 343, 492)
0.93035
0.75761
23613
19660
(500, 435, 440)
0.98743
0.79883
34189
30465
(500, 347, 493)
0.77210
0.44679
23131
19350
(500, 327, 498)
0.80318
0.63370
22272
19773
(500, 467, 418)
0.73983
0.46125
38725
35532
Average
0.97582
0.81012
10706
9505Table2 shows the average results for theadditive epsilon indicator. FEMOEA obtains the best result in just 2 out of the 30 problems, while MOEA/D achieves it in 28 instances. For this indicator, MOEA/D is clearly the best algorithm.Table 2
AverageI
ϵ
+
1 values. MOEA/D was run with the same number of function evaluations as FEMOEA.
Problem
FEMOEA
MOEA/D
(25, 24, 18)
0.00068
0.00035
(25, 21, 24)
0.21509
0.00143
(25, 21, 23)
0.00266
0.00090
(25, 22, 20)
0.00912
0.00019
(25, 22, 21)
0.00403
0.00080
(25, 21, 20)
0.04324
0.03989
(25, 23, 20)
0.43792
0.21885
(25, 24, 18)
0.00034
0.00008
(25, 17, 24)
0.00246
0.00253
(25, 24, 20)
0.07457
0.00176
(100, 75, 93)
0.00037
0.00012
(100, 90, 92)
0.00209
0.00002
(100, 94, 84)
0.00130
0.00053
(100, 96, 75)
0.00196
0.00569
(100, 82, 92)
0.00132
0.00033
(100, 75, 92)
0.00349
0.00007
(100, 85, 90)
0.00069
0.00007
(100, 75, 93)
0.04547
0.02274
(100, 67, 98)
0.00229
0.00067
(100, 90, 87)
0.00185
0.00009
(500, 347, 493)
0.00044
0.00024
(500, 436, 474)
0.01485
0.00004
(500, 406, 484)
0.00038
0.00002
(500, 438, 417)
0.00058
0.00006
(500, 482, 388)
0.00065
0.00003
(500, 343, 492)
0.00045
0.00002
(500, 435, 440)
0.00111
0.00018
(500, 347, 493)
0.00083
0.00001
(500, 327, 498)
0.00092
0.00004
(500, 467, 418)
0.00091
0.00005
Average
0.02907
0.00993Table3 shows the results for thespread indicator. FEMOEA obtains the best result in 23 out of the 30 problems, while MOEA/D achieves it in 7 instances. Besides, note that FEMOEA performs better as the total number of demand points increases, that is, the number of problems for which FEMOEA achieves the best value rises as |
A
+
∪
A
-
| increases, as compared to MOEA/D. In average, when considering all the problems, FEMOEA is superior to MOEA/D for this quality indicator.Table 3
Average spread values. MOEA/D was run with the same number of function evaluations as FEMOEA.
Problem
FEMOEA
MOEA/D
(25, 24, 18)
1.12956
1.28165
(25, 21, 24)
1.04294
1.12417
(25, 21, 23)
0.99491
1.08773
(25, 22, 20)
1.05180
0.87930
(25, 22, 21)
0.98264
1.09932
(25, 21, 20)
1.02766
0.15614
(25, 23, 20)
1.02432
0.89417
(25, 24, 18)
0.99967
1.17793
(25, 17, 24)
1.00648
0.83419
(25, 24, 20)
1.05036
1.62452
(100, 75, 93)
0.95021
1.29786
(100, 90, 92)
1.10039
0.92509
(100, 94, 84)
0.87594
1.17988
(100, 96, 75)
1.04167
1.35587
(100, 82, 92)
1.07414
1.24912
(100, 75, 92)
1.03605
1.28197
(100, 85, 90)
1.00849
0.93924
(100, 75, 93)
0.97911
1.28423
(100, 67, 98)
1.05109
1.20700
(100, 90, 87)
0.92771
1.06084
(500, 347, 493)
1.10840
1.38154
(500, 436, 474)
1.19189
1.17312
(500, 406, 484)
0.89934
1.62259
(500, 438, 417)
1.08120
1.30452
(500, 482, 388)
1.14914
1.36793
(500, 343, 492)
1.14351
1.16944
(500, 435, 440)
1.11731
1.36507
(500, 347, 493)
1.18428
1.35763
(500, 327, 498)
1.10058
1.13559
(500, 467, 418)
1.14600
1.24795
Average
1.04923
1.16885The computational study suggests that both FEMOEA and MOEA/D are competitive multiobjective evolutionary algorithms, able to deal with the hard-to-solve triobjective location model presented in this paper. Furthermore, taking all the quality indicators into account, it could be inferred that FEMOEA performs slightly better than MOEA/D, for the considered settings.


## 3.1. Algorithms

MOEA/D is a generic, evolutionary multiobjective optimization algorithm based on decomposition. It first uses a decomposition method to decompose a multiobjective optimization problem into a number of scalar optimization problems. Then, an evolutionary algorithm is employed to optimize these subproblemssimultaneously. Each individual solution in the population of MOEA/D is associated to a subproblem. A neighbourhood relationship among all the subproblems is defined based on the distances of their weight vectors. In MOEA/D, optimization of a subproblem uses the current information of its neighbouring subproblems since two neighbouring subproblems should have close optimal solutions. See [28, 29] for more details on the algorithm. It will be one of the algorithms used in our study.The other one is FEMOEA. It is also a generic, multiobjective evolutionary algorithm, but based onspecies. A species is mainly defined by a centre and a radius. The centre is a solution and the radius is a positive number which determines the subregion of the search space covered by that species. The main aim of the radius is to focus the searching operators on the corresponding subregions. At each stage of the algorithm, several species with different radii can coexist simultaneously. The use of different radii throughout the optimization process allows, on the one hand, identifying regions in the search space with high quality solutions and, on the other hand, to not waste too much time on regions of the search space which are either already explored or do not provide high quality solutions. Additionally, FEMOEA includes a local method which accelerates the convergence of the population towards the optimal Pareto-front. Basically, this method is an extension of the local optimizer SASS [41] and improves a given solution along a search direction (no gradient information is used). Finally, unlike the termination criteria of most MOEAs in literature, which is usually based on a number of function evaluations, FEMOEA incorporates a stopping rule which establishes that the algorithm will finish if during three consecutive iterations, the changes experimented in the candidate Pareto-front are negligible (in terms of the objective function values), for a given tolerance. To know how far two sets are from each other, a modified Hausdorff distance is proposed.The version of MOEA/D used in the studies, obtained from jMetal [42], is coded in Java, while the algorithm FEMOEA has been implemented in C++. The parameters used for MOEA/D are those proposed in [29], while the ones considered by FEMOEA are those recommended in [31]. For both algorithms and all the instances, the number M of points in the set approximating the Pareto-front has been set to 300. Notice that this is also the number of points in the population set for both algorithms.Since the analyzed algorithms are stochastic heuristics, every particular instance has been run five times by each algorithm. The value of the quality indicator considered for a given problem is the average over the five runs. Additionally, notice that due to the termination criteria of FEMOEA, each particular instance may require a different number of function evaluations. Then, in order to carry out the comparison as fair as possible, the number of function evaluations used by MOEA/D has been modified for each particular problem by fixing it to the average number of evaluations performed by FEMOEA in the five runs.


## 3.2. Problems

In order to have an overall view of the performance of the algorithms, different types of problems have been generated, varying the total number of demand points,|
A
+
∪
A
-
|, the number of demand points which feel repulsion, |
A
-
|, and the number of demand points which feel attraction, |
A
+
|. More precisely, three different values of |
A
+
∪
A
-
| were considered; that is, |
A
+
∪
A
-
|
=
25,100,500. For each value, 10 instances were generated by randomly choosing the parameters of the problems uniformly within predefined intervals: a
∈
(
[
0,10
]
,
[
0,10
]
),w
a
+
,
w
a
-
∈
[
1,10
],α
a
∈
[
-
5,1
]
,
β
a
∈
[
1,6
], and d
+
(
a
,
x
)
=
d
-
(
a
,
x
)
=
(
b
1
a
(
x
1
-
a
1
)
2
+
b
2
a
(
x
2
-
a
2
)
2
)
1
/
2 with b
1
a
,
b
2
a
∈
[
1,2.5
] (see [43]). The searching space proposed was (
[
0,10
]
,
[
0,10
]
) for all the problems. Besides, for each instance, both |
A
-
| and |
A
+
| values were also randomly computed, so that A
+
∩
A
- includes at least 65% of the points of A
+
∪
A
- and at most 85% of them. Each particular instance will be represented by (
|
A
+
∪
A
-
|
,
|
A
-
|
,
|
A
+
|
) throughout this work.


## 3.3. Quality Indicators

To measure the quality of the sets offered by the algorithms at approximating the Pareto-front, severalquality indicators from literature have been utilized. They map each Pareto-front approximation to a number, which can then be easily compared. Three quality indicators have been considered in this study, namely, the hypervolume, the additive epsilon indicator, and the spread, that will be explained later.Lets assume that we want to compare the quality of the outcomes generated byQ stochastic algorithms (Q
=
2 in our study). For each algorithm q, q
∈
{
1
,
…
,
Q
}, e
q runs are performed (e
q
=
5 in our study), generating the approximation sets P
S
1
q
,
…
,
P
S
e
q
q (in the decision space). Let us denote by S
P
S the set of all the approximation sets of the Pareto-set, S
P
S
=
{
P
S
1
1
,
…
,
P
S
e
1
1
,
…
,
P
S
1
Q
,
…
,
P
S
e
Q
Q
}.In some of the indicators listed below the approximation sets of the Pareto-front need to be compared to thetrue Pareto-front. However, the true Pareto-front is not usually known or cannot be completely obtained. Then, areference set
R
S which approximates the true Pareto-front is used instead. In our studies, the reference set R
S has been obtained as follows. All the approximation sets in S
P
S are combined, and then the dominated points are removed from this union. The image of the remaining points forms the reference set.Furthermore, normalized objective values are used to allow different objectives to contribute equally to comparative indicator values. The standard normalization is(7)
f
l
y
′
=
f
l
y
-
f
l
min
⁡
f
l
max
⁡
-
f
l
min
⁡
,where f
l
(
m
i
n
) (resp., f
l
(
m
a
x
)) denotes the minimum (resp., maximum) value of f
l when considering all the solutions in S
P
S.The most commonly used quality indicator in literature ishypervolume [44], which measures the hypervolume of the portion of the criterion space that is weakly dominated by the approximation set. The higher the hypervolume, the better the approximation. In order to measure this quantity, a reference point that is dominated by all points is needed. For a given problem, the same reference point has to be used for all the algorithms and all the runs. In our computational studies, the point whose lth component is the maximum of all the lth components of points in f
(
S
P
S
) is considered. It is an approximation of the Nadir point obtained when considering all the approximations of the Pareto-front together. The computation of thehypervolume metric has been depicted in Figure 4, although, for the sake of simplicity, the biobjective case has been represented.Figure 4
Computation of the hypervolume value for an approximation set with two objectives.Hypervolume can be thought of as aglobal quality indicator, in the sense that it assesses the approximation set as a whole. On the other hand,proximity indicators somehow measure the distance between the approximation set and the reference set. In this paper, we have used theunary additive epsilon indicator [45]. For an approximation of a Pareto-set, P
S, it is computed as (8)
I
ϵ
+
f
PS
=
min
ϵ
∈
R
⁡
∀
z
∈
RS
∃
a
∈
PS
:
f
l
a
-
f
l
m
i
n
f
l
m
a
x
-
f
l
m
i
n
-
ϵ
≤
z
l
-
f
l
m
i
n
f
l
m
a
x
-
f
l
m
i
n
∀
l
∈
1
,
…
,
mand gives the minimum distance by which f
(
P
S
) needs to be translated in each dimension in objective space such that R
S is weakly dominated by it. See Figure 5 for a graphic representation about the computation of the I
ϵ
+ indicator (again for the biobjective case).Figure 5
Computation of the epsilon indicator for an approximation set with two objectives.Besides, anevenness/diversity indicator, the well-knownspread [22, 26], is used in the studies. It is computed as (9)
Δ
f
PS
=
∑
l
=
1
m
d
f
l
m
i
n
,
f
PS
+
∑
sp
∈
PS
d
f
sp
,
f
PS
-
d
¯
∑
l
=
1
m
d
f
l
m
i
n
,
f
PS
+
PS
·
d
¯
,where (10)
d
f
sp
,
f
PS
=
min
s
p
∗
∈
PS
,
s
p
∗
≠
sp
⁡
f
sp
′
-
f
s
p
∗
′
2
,
d
¯
=
1
PS
∑
sp
∈
PS
d
f
sp
,
f
PS
.
·
2 denotes the Euclidean distance and f
y
′
=
(
f
1
y
′
,
…
,
f
m
y
′
). If the solutions in the approximation set P
S are well distributed and include the extreme solutions, Δ
(
f
(
P
S
)
)
=
0. Figure 6 depicts two approximation sets for a biobjective problem. The figure on the left hand depicts a better distributed Pareto-front as compared to the one on the right side. Therefore, the spread measure will be smaller for the Pareto-front on the left.Figure 6
Representation of two approximation sets for a biobjective problem. The Pareto-front on the left is better distributed and, hence, it will have a smaller spread value than the one on the right.
(a)
(b)


## 3.4. Comparative Study

All the computational studies in this paper have been run in the supercomputer Bullxual at the University of Almería, Spain, which is a cluster with 18 nodes. Each node has 16 cores (Intel Xeon E5 2650) and 64 GB of memory and 128 GB of solid-state drive. The whole supercomputer has 288 cores, 1151 GB of memory and 2304 GB of SSD. In our computational studies, each problem was run in one of the cores of the nodes (one problem at a time).Table1 summarizes thehypervolume average results obtained by both FEMOEA and MOEA/D for each particular instance. The final row refers to the average value, considering all the problems. As can be seen, FEMOEA obtains the highest hypervolume (highlighted with a bold font) for all the problems. Notice, however, that the results obtained by MOEA/D are also competitive (in average, the hypervolume values are 16.98% smaller). In the same table the CPU times employed by both algorithms, in seconds, are reported. As we can see, in average, MOEA/D is 11.21% quicker than FEMOEA.Table 1
Average hypervolume values and average computing time (in seconds). MOEA/D was run with the same number of functions evaluations as FEMOEA.
Problem
FEMOEA
MOEA/D
FEMOEA
MOEA/D
Av. (hyper)
Av. (hyper)
Av. (time)
Av. (time)
(25, 24, 18)
0.91196
0.78084
76
52
(25, 21, 24)
1.15776
1.06012
115
97
(25, 21, 23)
1.22557
1.04957
98
64
(25, 22, 20)
0.99244
0.67305
103
71
(25, 22, 21)
1.16561
1.07470
98
63
(25, 21, 20)
1.26344
1.26117
105
79
(25, 23, 20)
1.27525
1.26033
79
56
(25, 24, 18)
1.05399
0.98118
116
76
(25, 17, 24)
0.98886
0.85612
65
38
(25, 24, 20)
1.08105
1.03254
73
58
(100, 75, 93)
0.90985
0.74924
845
629
(100, 90, 92)
0.97463
0.81445
1020
786
(100, 94, 84)
0.98315
0.82334
1321
813
(100, 96, 75)
1.04997
0.81953
1562
1330
(100, 82, 92)
0.82064
0.63769
789
699
(100, 75, 92)
1.12490
0.83296
658
544
(100, 85, 90)
1.13659
1.08949
958
749
(100, 75, 93)
1.11774
1.04373
712
541
(100, 67, 98)
1.00772
0.51032
456
374
(100, 90, 87)
0.83631
0.70375
954
769
(500, 347, 493)
0.99370
0.70744
24617
20514
(500, 436, 474)
0.85810
0.69633
35326
31285
(500, 406, 484)
0.46998
0.43240
33409
32257
(500, 438, 417)
0.80063
0.68276
34606
31438
(500, 482, 388)
0.84188
0.63235
41099
36998
(500, 343, 492)
0.93035
0.75761
23613
19660
(500, 435, 440)
0.98743
0.79883
34189
30465
(500, 347, 493)
0.77210
0.44679
23131
19350
(500, 327, 498)
0.80318
0.63370
22272
19773
(500, 467, 418)
0.73983
0.46125
38725
35532
Average
0.97582
0.81012
10706
9505Table2 shows the average results for theadditive epsilon indicator. FEMOEA obtains the best result in just 2 out of the 30 problems, while MOEA/D achieves it in 28 instances. For this indicator, MOEA/D is clearly the best algorithm.Table 2
AverageI
ϵ
+
1 values. MOEA/D was run with the same number of function evaluations as FEMOEA.
Problem
FEMOEA
MOEA/D
(25, 24, 18)
0.00068
0.00035
(25, 21, 24)
0.21509
0.00143
(25, 21, 23)
0.00266
0.00090
(25, 22, 20)
0.00912
0.00019
(25, 22, 21)
0.00403
0.00080
(25, 21, 20)
0.04324
0.03989
(25, 23, 20)
0.43792
0.21885
(25, 24, 18)
0.00034
0.00008
(25, 17, 24)
0.00246
0.00253
(25, 24, 20)
0.07457
0.00176
(100, 75, 93)
0.00037
0.00012
(100, 90, 92)
0.00209
0.00002
(100, 94, 84)
0.00130
0.00053
(100, 96, 75)
0.00196
0.00569
(100, 82, 92)
0.00132
0.00033
(100, 75, 92)
0.00349
0.00007
(100, 85, 90)
0.00069
0.00007
(100, 75, 93)
0.04547
0.02274
(100, 67, 98)
0.00229
0.00067
(100, 90, 87)
0.00185
0.00009
(500, 347, 493)
0.00044
0.00024
(500, 436, 474)
0.01485
0.00004
(500, 406, 484)
0.00038
0.00002
(500, 438, 417)
0.00058
0.00006
(500, 482, 388)
0.00065
0.00003
(500, 343, 492)
0.00045
0.00002
(500, 435, 440)
0.00111
0.00018
(500, 347, 493)
0.00083
0.00001
(500, 327, 498)
0.00092
0.00004
(500, 467, 418)
0.00091
0.00005
Average
0.02907
0.00993Table3 shows the results for thespread indicator. FEMOEA obtains the best result in 23 out of the 30 problems, while MOEA/D achieves it in 7 instances. Besides, note that FEMOEA performs better as the total number of demand points increases, that is, the number of problems for which FEMOEA achieves the best value rises as |
A
+
∪
A
-
| increases, as compared to MOEA/D. In average, when considering all the problems, FEMOEA is superior to MOEA/D for this quality indicator.Table 3
Average spread values. MOEA/D was run with the same number of function evaluations as FEMOEA.
Problem
FEMOEA
MOEA/D
(25, 24, 18)
1.12956
1.28165
(25, 21, 24)
1.04294
1.12417
(25, 21, 23)
0.99491
1.08773
(25, 22, 20)
1.05180
0.87930
(25, 22, 21)
0.98264
1.09932
(25, 21, 20)
1.02766
0.15614
(25, 23, 20)
1.02432
0.89417
(25, 24, 18)
0.99967
1.17793
(25, 17, 24)
1.00648
0.83419
(25, 24, 20)
1.05036
1.62452
(100, 75, 93)
0.95021
1.29786
(100, 90, 92)
1.10039
0.92509
(100, 94, 84)
0.87594
1.17988
(100, 96, 75)
1.04167
1.35587
(100, 82, 92)
1.07414
1.24912
(100, 75, 92)
1.03605
1.28197
(100, 85, 90)
1.00849
0.93924
(100, 75, 93)
0.97911
1.28423
(100, 67, 98)
1.05109
1.20700
(100, 90, 87)
0.92771
1.06084
(500, 347, 493)
1.10840
1.38154
(500, 436, 474)
1.19189
1.17312
(500, 406, 484)
0.89934
1.62259
(500, 438, 417)
1.08120
1.30452
(500, 482, 388)
1.14914
1.36793
(500, 343, 492)
1.14351
1.16944
(500, 435, 440)
1.11731
1.36507
(500, 347, 493)
1.18428
1.35763
(500, 327, 498)
1.10058
1.13559
(500, 467, 418)
1.14600
1.24795
Average
1.04923
1.16885The computational study suggests that both FEMOEA and MOEA/D are competitive multiobjective evolutionary algorithms, able to deal with the hard-to-solve triobjective location model presented in this paper. Furthermore, taking all the quality indicators into account, it could be inferred that FEMOEA performs slightly better than MOEA/D, for the considered settings.


## 4. Conclusions and Future Research

In this work, a new model for locating a single semidesirable facility in the plane is presented. Three objectives are considered for the first time in literature: (i) the minimization of the sum of weighted distances between the facility and the users to which it provides a service (to maximize its efficiency); (ii) the minimization of the sum of the repulsions of the people affected by the undesirable effects produced by the facility (to minimize the social cost); and (iii) the minimization of the Gini index applied to the repulsions felt by the affected people (to distribute the repulsions fairly among the affected people). Whereas in previous studies dealing with the location of facilities with an equity objective, the aim has always been to equalize the distances, notice that, for the problem at hand, the equity objective is aimed at equalizing the undesirable effects.This hard-to-solve triobjective location model has been tackled by means of two multiobjective evolutionary optimization methods, namely, MOEA/D and FEMOEA. Results convey that both FEMOEA and MOEA/D are suitable and competitive algorithms. As they are general purpose algorithms, they both could also handle other similar realistic bi- and triobjective location models.In the future, we plan to develop new multiobjective methods for solving some of the most successful existing multiobjective location models, as well as proposing new, more realistic models for the location of both undesirable and semidesirable facilities.



---

*Source: 631872-2015-07-13.xml*