Geoscience Reference
In-Depth Information
set of candidates for each individual facility but it is the set of candidate pairs to be
optimal solutions.
10.4.2.2
A Discouraging Result for the p-Facility Case
It is well-known that FDS of polynomial size exist for the classical p-median,
p-center, p-centdian and p-k-centrum problems (see Hooker et al.
1991
; Kalcsics
et al.
2003
). In addition, our previous section has shown a finite set of candidates
to be optimal solutions of the 2-facility ordered median problem in a network.
However, despite the similarity existing between those problems and the general
p-facility ordered median problem, these results can not be extended to our model.
The reason for this is the following. For the 1-facility ordered median problem
we have that the set of candidates to be optimal solutions is
EQ
, that means, the
equilibrium points (see Nickel and Puerto
1999
). For the 2-facility ordered median
problem we have obtained that the set of candidates to be optimal solutions is
EQ
Y
[
T , that means, the points generated by the distances between each node and each
equilibrium point and the set T. It should be noted that in this case we have added
these points because there may exist ties which do not allow to move the service
facility improving the objective function. In the 3-facility ordered median problem,
the previous candidate set is not enough because if x
1
2
EQ
and x
2
2
Y
n
EQ
,the
distances between each node and x
2
don't have to be included in the set of radius,
R. Therefore, it may occur that there exists a tie between two nodes and the service
facilities x
2
and x
3
respectively, so that there is no movement of the facilities at x
2
and x
3
which improves the objective function (see Example
10.6
).
Example 10.6
Let N
D
.G;`/ be a network with underlying graph G
D
.V;E/
where V
Df
v
1
;v
2
;v
3
;v
4
;v
5
;v
6
g
and E
Dff
1;2
g
;
f
2;3
g
;
f
3;4
g
;
f
4;5
g
;
f
5;6
gg
.The
length function is given by `.
f
1;2
g
/
D
3;`.
f
2;3
g
/
D
50;`.
f
3;4
g
/
D
6;`.
f
4;5
g
/
D
50;`.
f
5;6
g
/
D
10. The w-weights are all equal to one and the -modeling weights
are
1
D
0:1;
2
D
0:2;
3
D
0:4;
4
D
0:3;
5
D
0:6;
6
D
0:55,seeFig.
10.6
(in
this figure we use the same notation used in Fig.
10.4
).
In this example the optimal solution is given by x
1
D
p.
f
1;2
g
;1:5/, x
2
D
p.
f
3;4
g
;1:5/ and x
3
D
p.
f
4;5
g
;4:5/ (see Table
10.7
). It can be seen that x
1
is
an equilibrium point, x
2
2
Y.1:5/ and x
3
neither belongs to Y nor is a component
of a pair of T .
This example illustrates that in order to obtain the optimal solution for the
3-facility problem new points have to be added. Our conjecture is that these points
3
50
6
50
10
v
1
v
2
v
3
v
4
v
5
v
6
|
|
|
|
| | ||
Fig. 10.6
Illustration of Example
10.6
