Geoscience Reference
In-Depth Information
The objective function (
4.1
) together with (
4.2
) ensure that the objective value is no
less than the maximum of the distances between demand points and their facilities.
Constraints (
4.3
) establish the assignment of each demand point to exactly one
facility. Constraints (
4.4
) avoid assignment of demand points to locations with no
facility. Constraint (
4.5
) restricts the number of facilities to p. Constraints (
4.6
)
and (
4.7
) are the binary restrictions.
Daskin (
2013
) also proposed a set covering based algorithm, in which the radius
value of the set covering problem is selected from an interval of real numbers
between pre-determined lower and upper bounds. At each step of the algorithm,
the interval is halved and one of the segments is removed depending on whether the
objective value of the set covering problem is greater than p or less than or equal
to p.
Ilhan and Pınar (
2001
) proposed a two-phase extension of the algorithm devel-
oped by Daskin (
2013
). In the first phase, they solve the linear programming (LP)
relaxation of the feasibility problem defined by (
4.5
), (
4.6
), and
X
a
ji
y
i
1;
8
j
2
J;
(4.8)
i2I
iteratively for fixed r values to obtain a relatively tight lower bound for the p-center
problem. In the second phase, they restrict the interval of the radius values with
the lower bound obtained in the first phase and solve the integer programming (IP)
version of the same feasibility problem iteratively to obtain the optimal value of the
p-center problem.
Elloumi et al. (
2004
) proposed a new IP formulation for the p-center problem.
This formulation utilizes the fact that the optimal value of the p-center problem
is restricted to a finite set of distance values. They introduced additional binary
variables
z
k
, k
D
2;:::;K, with
z
k
D
0 if all demand points can be covered by
p facilities within a radius value of r
k1
and
z
k
D
1 otherwise. The formulation is
given below:
X
K
.r
k
r
k1
/
z
k
Minimize
r
1
C
(4.9)
kD2
subject to
(
4.5
), (
4.6
),
X
y
i
1;
(4.10)
i2I
z
k
C
X
iWd
ji
<r
k
y
i
1
8
j
2
J;k
D
2;:::;K;
(4.11)
z
k
2f
0;1
g
k
D
2;:::;K:
(4.12)
