American Journal of Oper ations Research, 2011, 1, 39-45
doi:10.4236/ajor.2011.12006 Published Online June 2011 (http://www.SciRP.org/journal/ajor/)
A Multi-Objective Obnoxious Facility Location Model
on a Plane
Utpal K. Bhattacharya
Indian Institute of Management Ind ore, Indore, India
Received February 25, 2011; revised March 15, 201 1; accepted April 8, 2011
Abstract
In this paper a Vertex Covering Obnoxious Facility Location model on a Plane has been designed with a
combination of three interacting criteria as follows: 1) Minimize the overall importance of the various exist-
ing facility points; 2) Maximize the minimum distance from the facility to be located to the existing facility
points; 3) Maximize the number of existing facility points covered. Area restriction concept has been incor-
porated so that the facility to be located should be within certain restricted area. The model developed here is
a class of maximal covering problem, that is covering maximum number of points where the facility is withi n
the upper bounds of the corresponding mth feasible region. Two types of compromise solution methods have
been designed to get a satisfactory solution of the multi-objective problem. A transformed non-linear pro-
gramming algorithm has been designed for the proposed non-linear model. Rectilinear distance norm has
been considered as the distance measure as it is more appropriate to various realistic situations. A numerical
example has been presented to illustrate the solution algorithm.
Keywords: Obnoxious Facility Location, Multi-objective Decision Making, Maximal Covering Problem
1. Introduction
For service facility location problems when the costs are
the increasing function of distance, it is reasonable to
consider either minimum of the sum of distances or the
weighted distances. On the other hand, for some vital fa-
cilities it may be desired to minimize the maximum dis-
tances. However, there are types of location situations
where cost decreases as distance increases and is consid-
ered the name in the literature as the obnoxious or unde-
sirable facility location problems.
Erkut and Neuman [1] have given an excellent survey
on undesirable facility location problems. Models con-
taining maximization of some function of distances as
one of the objectives were considered for analysis. Ex-
amples appropriate for the above cases are garbage dump,
chemical plant or a nuclear reactor. Another type of
problems called semi desirable, have been found in the
literature. Examples appropriate for these models are
baseball stadium, incineratio n plants etc.
In the location literature many people have worked on
MAXIMIN criterion with Euclidean distances. Shamos [2]
defines the unweighted MAXIMIN problem as the largest
empty circle problem in and provides an algorithm
for solving that problem. Dasarathy and White [3] ex-
tended the unweighted maximin problem to a higher di-
mensional space and a convex feasible region. They pro-
vide an algorithm for a three dimensional space. Drezner
and Wesolowsky [4] present a solution to a maximin pro-
blem assuming a feasible region which is the intersection
of the circles of prescribed radii whose centers are existing
facility points. Melachrinoudis and Cullinane [5] solved
maximin problem for the case of non convex feasible re-
gion S in the presence of forbidden circles.
2
R
Drezner and Wesolowsky [6] first introduced the rec-
tilinear maximin problem for locating an obnoxious fa-
cility. They developed a solution procedure by dividing
the feasible region into rectilinear sub regions and solv-
ing a linear programming problem for each of this sub
regions. Melachrinoudis [7] proved several properties of
the optimal solution, dev eloped elimination strategies for
the sub regions and solved the duals of the LPs for the
remaining sub regions. Mehrez et al. [8] suggested an
improvement of Drezner and Wesolowsky’s algorithm,
based on bounds, which reduces the size as well as the
number of sub problems to be solved. Arie Tamir [9] has
presented a subquadratic algorithm for location two ob-
noxious facilities using the weighted maximin criterion.

U. K. BHATTACHARYA 40
n
Banez et. al. [10] have considered a problem of locat-
ing an obnoxious plane and solved in O() time and
O( ) space. Plastria and Carrizosa [11] have considered
of locating an undesirable facility within some feasible
region of any shape in the plane or on a planar network
by considering two criteria: a radius of influence to be
maximized and the total covered population to be mini-
mized. Low complexity polynomial algorithms are de-
rived to determine all non dominated solutions.
3
n
2
n
A bibliography for some fundamental problem catego-
ries such covering models are given by C.S. Revelle,
H.A. Eiselt, M.S. Daskin [12].
In this present investigation a vertex covering obnox-
ious facility location model has been designed with multi-
ple objectives. In this model weights as importance has
been assigned to the various demand points and considers
as a separate objective. Because of undesirable facility, the
facility points which has to be kept more distance away
from the undesirable facility location should be given less
weitages compared to the facility points which may be
kept comparatively closer. The problem has been modeled
as a pure planar location problem. Area restriction concept
has been incorporated so that the facility to be located
should be within certain restricted area. Incorporation of
the area restriction has been implemented by inducting a
convex polygon in the feasible region. Another advantage
of introduction of a convex polygon in the constraint set is
that it might reduce the number of transformed non-linear
programming problems to be solved. Two types of com-
promise solution methods have been designed to get the
satisfactory solution of the original multi-objective non
linear model. The proposed model has another advantage
to give different weightages to the different criteria sepa-
rately to reach out to a desired compromise solution. Rec-
tilinear distance norm has been considered as a distance
measure to design the model. A numerical example has
been presented to illustrate the solution algorithm.
Preliminaries are mentioned in Section 2. Model for-
mulation for the vertex covering obnoxious facility
problem has been given in Section 3. An algorithm has
been designed in Section 4. A numerical example has
been presented in Section 5. Concluding remarks are
made in Section 6.
2. Preliminaries
1-Maxi-min Problem: Single facility location problem
with maximum objective can be broadly classified into
maximin and maxi sum objectives. The problem 1-maxi
min which is u nder st u dy i n t his paper i s descri bed bel o w.
Let for be the location of n de-
mand points.

,
ii
ab 1, 2,,i

,
x
y be the co-ordinates of the facility
to be located.
Then


,min i
i

i
F
xyx ay b
be the mini-
mum rectangular distances from the facility to the de-
mand poi nt i. Then the mathematical model is
Max

,
F
xy
subject to ,0AXb x.


3. Mathematical Formulation
Let


,
ii
ab be the location of the ith existing facility
and


,
x
y is the coordinates of the point to be located.
The objective corresponding to the Minimize the overall
importance of the various demand points is formulated as
P1.
Min
1
n
ii
i
wx


where 1,
0.
ii
ii
x
aybZ
xOtherwise


 


and wi is the weights as importance assigned to the ith
demand points for every i.
The objective corresponding to maximize the mini-
mum distance from the facility to the demand points ob-
jective can be written as follows.
P2.
Maximize



,
i
M
inimizedx y


,
x
yS

i
where


,
ii
dxyxa yb
i


The third objective maximize the demand units cov-
ered can be formulated as
P3.
Maximize 1
n
i
i
x


where i
x
is as defined earlier.
Thus the multi-objective formulation of the vertex
covering obnoxious facility location problem may be
written as follows
P4.
Minimize
1
n
ii
i
wx


M
aximize 1
Z
Maximize
1
n
i
i
x


subject to,
1, ii
x
aybZ 1, 2,,in
12 , 3
j
j
cx cyc
j

 1, 2,,jk


,
x
yS


U. K. BHATTACHARYA 41
where 1
1,
0
ii
i
if xaybZ
xOtherwise



4. Algorithm for Vertex Covering Obnoxious
Facility Location Problem
Let us consider the grid of lines formed by drawing hori-
zontal and vertical lines through every demand point
. This will form at most rectangular re-
gions, some of them bounded by infinity. Consider now
the mathematical formulation which may be written as

,
ii
ab


2
1n
P5.
Maximize 1
Z
Minimize
1
n
ii
i
wx


M
aximize 1
n
i
i
x


subject to,
1, iii
x
aybZX 1, 2,,in
1m
Z
UB
12 , 3
j
j
y c
j
cx c 1, 2,,jk
where 1
1,
0
ii
i
if xaybZ
xOtherwise



and is the upper bound corresponding to the rec-
tangle m.
m
UB
Next to find the upper bound inside rectangle m. The
maximum value of 1
Z
on m is as given below:
 
mii
Z
Max Minxayb 

,
x
ym i
 
ii
M
in Maxxayb
i

,
x
ym

The maximum inside rectangle m must occur on V,
where V is the set of four vertices of the rectangle (some
of this vertices may be at infinity). Hence, an upper
bound on 1
Z
is



mi
UBMin Maxxayb

i

i

,
x
ym
For an open rectangle UB in infi nite.
The single objective formulation of the above mul-
ti-objective problem is as given below.
The non-linear constraints of Problem (5) can be bro-
ken down into four alternative sub problems by using the
P6.
inequality relations. The four sub problems are as follows.
imize Max1
Z
1
n
ii
i
wx

 M
inimize
M aximize 1
n
i
i
x


subject to,
10 ii i
xyabZx


1m
Z
UB

12 , 3
j
jj
cx cyc
or imize
1, 2,,jk.
P7.
Max 1
Z
1
n
ii
i
wx

 M
inimize
M aximize 1
n
i
i
x


subject to,
10 ii i
xyabZx


1m
Z
UB

12 , 3
j
jj
cx cyc
or P8. ize
1, 2,,jk.
Maxim 1
Z
1
n
ii
i
wx

 M
inimize
M aximize 1
n
i
i
x


subject to,
10 ii i
xyabZx


1m
Z
UB

12 , 3
j
jj
cx cyc
or P9. ize
1, 2,,jk.
M axim 1
Z
Minimize wx
1
n
ii
i

1
n
i
i
x


M
aximize
subject to,
10 ii i
xyabZx


1m
Z
UB


U. K. BHATTACHARYA 42
312
j
jj
cx cyc
four problems P6 For all the
1, 2,,jk.
P9 -
1
1, i if xay
x 0.
i
i
b Z
Otherwise



And is the upper bound corresponding to the
rectangle . g the above multi-objective problem two
m
UB
m
For solvin
approaches are suggested.
Type Ⅰ Compromise solution:
Define the variable
K
U in such a way that

*
k
Kk
ZX
UXS


Z



For getting the compromise solution following objec-
tive function is defined.
P10.
112 233
M
aximize VUUU

  
such that
X
S
Where *
K
Z
is t maximum value ofhe
K
Z
over the
constraint * set.
K
Z
can be obtained by solv the indi-
vidual single octive problem. ing bje
K

is the weight at-
tached to the ith objective function.
The problem thus transformed to fur sets as the con-o
st
solution is obtained
by
ize
raints given in P6, P7, P8, P9 with objective function
for all the problems as given in P10.
Type Ⅱ compromise solution e The second type of compromis
defining the objective function
P11.
Minim 32
1
K
K
k
WU 


Where
K
U is defined as follows:
 
12 3
12 3
12 3
1,1 ,1
fX fX
UU U
ZZ Z
 



 

  

  

Where
fX   
*
K
Z
is the maximum value of
K
Z
over the
constraint *
set.
K
Z
can be obtained by solv the indi-
vidual single octive problem. ing bje
K

is the weight at-
tached to the ith objective function. Adjustment in 3 U to
avoid zero in the denominator.
The Algorithm for solving multi objective formulation
of the Obnoxious Facility Location Problem is as given
below.
Step-1. Formulate the multi-objective problem as
given in P10 for Type Ⅰ compromise solution and P11
for Type Ⅱcompromise solution. Choose the weightages
to be assigned to the different objectives.
Step-2.nd the enclosing feasible rectangle by the
procedure-1.
Fi
e within the enclosing feasible rectangle.
Step-3. Restrict the grid and rectangles to be considered
to those that li
Step-4. Eliminate all i nfeasi ble rect angl es by Result 1.
Step-5. Find the upper bound on 1
Z
for all the re-
m -
pe
aining rectangles by using Procedure 1. Sort these up
r bounds of 1
Z
from the largest to the smallest.
Step-6. Solve the multi-objective non-linear program-
ming problem breaking the problem into four albyterna-
tiv
hest upper bound on
e sub problems.
Step-7. Solve the sub problems starting with the rec-
tangle with the hig1
Z
. Stop when
the upper bound fo r the next rectangle is no t greater than
the best 1
Z
va lue solution found so far.
Step-8. Take the solution of the sub problem which
gives mimum objective function vaxalue for type
Ⅰcompromise solution and the solution of the sub prob-
lem which gives minimum objective function value.
Procedure 1. Find the enclosing feasible rectangle
(Drezner & Wesolowsky (1983)).
To find
L
x
X

, the left vertical line defining the rec-
tangle, solve a linear programming problem with x as the
ob be minjective toimized and the constraints ( ).
Maximizing x will give U
X
, which defines the right
vertical line. The lower and upper horizontal lines
L
yY

and U yY

are fousimilarly.
Let us consider the rectangle m defined by the lines
1
i
nd
x
a

2
i
x
a

3
i
y
b

4
i
y
b, where 12
ii
aa

and
34
ii
bb

. Also we define the segments
 
ii
LU
x
x


 and 
 
i
L
yy
i
U




 where
 
,
iiii
L
UL U
x
xy y the ; these are
parts of the line respectively and
i
yb i
x
a.
. If all thitions hold, then Result 1e folloond
de recm (Der &
W
wing c
there is no feasible point insitangle rezn
esolowsky (1983)).
 
11
ii
43
L
iUi
3
Yboryb (1)
 
22
4
ii
L
iU
yborybi 
1
(2)

3
3
4
i i
L
iU i
x
aorx a 
1
(3)

4
4
2
i
i
L
iU i
x
aorx a
5. Numerical Example
4,1), E(9,7) be the five de-
and points on a plane, and
(4)
Let A(2,1), B(3,5), C(6,9), D(
m35 45xy, 5442xy

,
0, 0xy are the boundary of the convex feasible re-
gion. Let the weights attached
15, 0.20, 0.10, 0.25 respectively.
The upper bound corresponding to the twenty feasible
to the five demand points
are 0.30, 0.
rectangles (see Figure 1) are obtained by procedure 1

U. K. BHATTACHARYA 43
, starting
fr
responding to the
hi
and theorem 1 and are given in the sorted form Solution obtained for is as given below:
om largest to the smallest in Table 1.
For Type Ⅰ compromise solution
In the first iteration the mathematical programming
formulation of the first sub problem cor
SP-1
0.426,V

123
1 2345
9,4, 0.7,
1.53,8.07,
0, 1
ZZZ
xy
xxxxx





ghest upper bound of 1
Z
as 9 is given in the following
Where 9,5,1 are the ideal solutions obtained for the
first, second and the third objectives respectively. The
weights attached to the three objectives are 0.4,0.3,0.3
re
Maximize 123
0.4(0.11) 0.060.3VZ ZZ
Subject to, Similarly the solutions for the other sub problems are
as given below.

11
12
13
14
15
123452
123453
12345
1 0;
0;
15 0;
50;
16 0;
0;
0.30.150.20.10.25 50;
35 45;
54 40;
0; 0;
,,,, 0,1;
Zx
Zx
xy Zx
xy Zx
xy Zx
xxxxxz
xxxxxz
xy
xy
xy
xxxxx
 

 
 
 






2xy SP-2
8xy V = 0.411,
123
1345 2
9, 1,0.15,
8, 0,
0, 1
ZZZ
xy
xxxx x




 
SP-3
V = 0.426,
123
1235 4
9, 1,0.10,
0, 9,
0, 1
ZZZ
xy
xxxx x




 
SP-4
V = 0.396
19;Z
123
12345
9,0, 0,
0, 0,
0
ZZZ
xy
xxxxx





spectively.
Table 1. Upper bound
Rectangle Nu
for various rectangles.
mber1069578111415161718192014121323
UBm 9 666555 5 5 5 5 5 4 5 333 3 22
Figure 1. Rectangles.

U. K. BHATTACHARYA 44
If we go to the next iteration with the next 1
Z
value,
the solution obtained can not dominate the1
Z
value sat-
isfactory solution for the multi-objective are the
solutions of SP-1 and SP-3. So in this case we are get-
ting the alternative optimal compromise solutions.
For Type Ⅱ compromise solution
In the first iteration the mathematical programming
formulation of the first sub problem corresponding to the
highest upper bound of
problem
1
Z
as 9 is given in the following.
Minimize






22
12
0.41(0.11) 0.31(0.2) 0.31WZZ Z 
2
3
Subject to,
The solution obtained by using software LINGO for the
four sub problems are as given below. The weights at-
tached to the three objectives are 0.4,0.3,0.3 respectively.
SP-1
W = 0.4E-04
Similarly the solution obtained for the other three sub
problems are as given below.
SP-2
W = 0.5887
SP-3
W = 0.555
SP-4
W = 0.594

11
12
13
14
15
123452
123453
12345
1
21 0;
80;
15 0;
50;
16 0;
0;
0.3 0.150.20.10.250;
35 45;
54 40;
0; 0;
,,,, 0,1;
9;
xy Zx
xy Zx
xy Zx
xy Zx
xy Zx
xxxxxz
xxxxxz
xy
xy
xy
xxxxx
Z
 
 
 
 
 







123
12345
9,5, 1,
7, 0,
1
ZZZ
xy
xxxxx



123
1345 2
9, 1,0.15,
8, 0,
0, 1
ZZZ
xy
xxxxx


 
123
1235 4
9, 1,0.10,
0, 9,
0, 1
ZZZ
xy
xxxx x


 
123
1345 2
8, 1,0.10,
0, 0,
0, 1
ZZZ
xy
xxxxx




 
1
Z
The solution obtained with the next value can not
dominate the solution obtained so far. us we stop the
process here and the satisfactory solution for the multi-
objective problem by using Type Ⅱ compromise solu-
tion methods are the solution of SP-1.
In the Type Ⅰ compromise solution method we have
got the alternative optimal solutions where as for the
Type Ⅱ compromise solution method we have got first
sub problem as the optimal compromise solution.
6. Concluding Remarks
 In this paper a vertex covering obnoxious facility
on problem has been modeled as a mul-
ti-objective planar location model.
 A modified non linear programming algorithm has
been designed to solve the proposed model.
 Two types of compromise solution methods have been
designed. In the first method each individual objec-
tives are divided by the ideal solutions and the sum of
them are maximized. Where as in the second method
each objective deviations have been divided by the
ideal solution and square of them has been minimized.
 Other distance norm such as Euclidean, Geodesic etc.
may be considered to model various other situations.
 Models with general feasible regions (Union of dis-
joint and non-convex sets) may be considered to mo-
del various geographic regions.
 The model developed here is a class of maximal cov-
ering problem, that is covering maximum number of
points where the facility is within the upper bounds of
the corresponding mth feasible region.
7. References
[1] E. Erkut and S. Neuman, “Analytical Models for Locat-
ing Undesirable Facilities,” European Journal of Opera-
tional Research, Vol. 40, No. 3, 1989, pp. 275-291.
doi:10.1016/0377-2217(89)90420-7
Th
locati
[2] M. I. Shamos, “Computational Geometry,” Ph.D. Disser-
tation, Department of Computer Science, Yale University,
New Haven, 1977.
[3] B. Dasarathy and L. White, “A Maximin Location Prob-
lem,” Operations Research, Vol. 28, No. 6, 1980, pp.
1385-1401. doi:10.1016/0377-2217(89)90420-7
[4] Z. Drezner and G. O. Wesolowsky, “A Maximin Loca-
tion Problem with Maximum Distance Constraints,” AIIE
Transaction, Vol. 12, No. 3, 1980, pp. 249-252.

U. K. BHATTACHARYA 45
doi:10.1080/05695558008974513
[5] E. Melachrinoudis and T. P. Cullinane,Locating an
Undesirable facility within a Geographical Region Using
the Maximin Criterion,” Journal of Regional Science, Vol.
25, No. 1, 1985, pp. 115-127. 7.x
“
doi:10.1111/j.1467-9787.1985.tb0029
[6] Z. Drezner and G. O. Wesolowsky, “The Location of an
Obnoxious Facility with Rectangular Distance,” Journal
of Regional Science, Vol. 23, No. 2, 1983, pp. 241-248.
11/j.1467-9787.1983.tb00800.xdoi:10.11
[7] hrindis, “An Efficient Computational Procedure
for the Rectilinear Maximin Location Problem,” Trans-
cience, Vol. 22, No. 3, 1988, pp. 217-223.
7/trsc.22.3.217
E. Melac
portation S
doi:10.128
[8] A. Mehrez, Z. Sinuany-Stern and A. Stulman, “An En-
hancement of the Drezner-Wesolowsky Algorithm for
Single Facility Location with Maximin of Rectangular
Distance,” Journal of Operations Research Society, Vol.
No. 10, 1986, pp. 971-977.
[9] “Locating Two Obnoxious Facilities using the
Weighted Maximin Criterion,” Operations Research Let-
ter, Vol. 34, No. 1, 2006, pp. 97-105.
doi:10.1016/j.orl.2005.02.004
37,
A. Tamir,
[10] J. M. Diaz-Banez, M. A. Lopez and J. A. Sellaves, “Lo-
cating an Obnoxious Plane,” European Journal of Opera-
pptions Research, Vol. 173, No. 2, 2006,. 556-564.
doi:10.1016/j.ejor.2005.02.048
[11] F. Plastria, and E. Carrizosa, “Undesirable Facility Loca-
tion with Minimal Covering Objectives,” European
Journal of Operational Research, Vol. 119, No. 1, 1999,
pp. 158-180. doi:10.1016/S0377-2217(98)00335-X
[12] C. S. ReVelle, H. A. Eiselt, M. S. Daskin, “A Bibliogra-
phy for Some Fundamental Problem Categories in Dis-
crete Location Science,” European Journal of Opera-
tional Rsearch, Vol. 184, No. 3, 2008, pp. 817-848.
doi:10.1016/j.ejor.2006.12.044