Geoscience Reference
In-Depth Information
r, one can solve a set covering problem with unit column costs by constructing A as
follows:
a
ji
D
1; if d.j;i/
r;
0; otherwise
8
j
2
J;i
2
I:
If the optimal value of the set covering problem is greater than p, then the optimal
value of the p-center problem needs to be greater than r; if it is less than or equal to
p, then it means that the optimal value of the p-center problem is less than or equal
to r.
The first set covering based approach was proposed by Minieka (
1970
). Let r
1
<
r
2
<:::<r
K
be an ordering of the distinct distance values in the distance matrix
D
D
Œd
ji
W
d
ji
D
d.j;i/;i
2
I;j
2
J and R
Df
r
1
;r
2
;:::;r
K
g
. The method
by Minieka (
1970
) solves the set covering problem for a smaller value in R not yet
considered at each step by updating the matrix A. The algorithm terminates when
the optimal value of the set covering problem is greater than p. Since the number
of different distance values in D is at most
j
I
j
:
j
J
j
, the algorithm converges to an
optimal solution in a finite number of steps.
Garfinkel et al. (
1977
) improved the set covering based approach by Minieka
(
1970
) by first finding a heuristic solution, then, reducing the search space of the
radius values and eliminating some of the intersection points. They also reduce the
size of the set covering matrix by using standard matrix reductions and heuristic
techniques. For the selection of the radius values at the next step, they proposed
using a bisection or binary search strategy instead of moving to the next smaller
radius value.
The first mixed integer programming (MIP) formulation for the discrete p-center
problem was proposed by Daskin (
2013
). The following decision variables are
defined: y
i
D
1 if a facility is placed at node i
2
I and 0 otherwise, x
ij
D
1 if
j
2
J is assigned to a facility placed at i
2
I and 0 otherwise. The formulation by
Daskin can be stated as follows:
Minimize
z
(4.1)
X
subject to
d
ji
x
ij
z
8
j
2
J;
(4.2)
i2I
X
x
ij
D
1
8
j
2
J;
(4.3)
i2I
x
ij
y
i
8
i
2
I;j
2
J;
(4.4)
X
y
i
p;
(4.5)
i2I
y
i
2f
0;1
g
8
i
2
I;
(4.6)
x
ij
2f
0;1
g
8
i
2
I;j
2
J:
(4.7)
