Geoscience Reference
In-Depth Information
can be generated using recursively the construction of the set of radii but now
regarding the distances from the points in
2
.F/
WD f
x
2
W
.x
1
;x
2
/
2
F
g
,that
is, the points in P.G/ which correspond to the second candidate of any pair in F ,
and the node set:
R
1
Df
r
W
r
D
w
i
d.v
i
;y/;v
i
2
V;y
2
2
.F/
g
;
Y
1
.r/
Df
y
W
y
2
P.G/;
w
i
d.v
i
;y/
D
r;v
i
2
V
g
;
Y
1
D
[
r2R
1
Y
1
.r/:
The same situation occurs in the p-facility case, so that in general this construc-
tion must be repeated p-times in order to obtain a finite candidate set to be optimal
solutions for that problem. Therefore the structure of the candidate set defined in
the previous section depends on the number of facilities to be located. Actually,
Puerto and Rodríguez-Chía (
2005
) prove that there is no polynomial size FDS for
the general ordered p-median problem even on path networks. The proof consists
of building a family of O.n
n
/ problems on the same graph with different solutions
(each solution contains at least one point not included in the remaining), n being the
number of nodes.
10.5
The Capacitated Discrete Ordered Median Problem
In this section our goal is to introduce the family of discrete ordered median location
problems. As we have seen in previous sections, the main feature of these models
is their flexibility to generalize the most popular objective functions studied in the
location analysis literature and to allow modeling a wide variety of new problems
appearing in logistics and manufacturing.
The uncapacitated version of the discrete ordered median location models has
been analyzed in several papers, Boland et al. (
2006
), Nickel (
2001
), Nickel and
Puerto (
2005
), Marín et al. (
2009
,
2010
), Puerto et al. (
2011
,
2013
), and different
formulations and algorithms to solve medium sized problems have been developed.
Recently, these models were extended to deal with capacities in Kalcsics et al.
(
2010a
,
b
). However, although the approach in the initial papers leads to satisfactory
results concerning motivations, applications and interpretations the solution times
of larger problem instances need further improvements.
The goal of this section is to present, first, an intuitive formulation of the
problem based on three-indexed variables, see Boland et al. (
2006
); and second,
a formulation which makes use of the coverage ideas in Marín et al. (
2009
,
2010
), applied to the capacitated version of the Discrete Ordered Median Problem,
CDOMP, with binary assignment, see Puerto (
2008
), Puerto et al. (
2011
,
2013
).
To perform this task, first we introduce the Capacitated Discrete Ordered Median
Problem formally and give these two mathematical programming formulations.
