Geoscience Reference
In-Depth Information
Instead, one should solve the problem using Ǜ
1
D
1
1
,where
1
>0
is a suitably small value so that we are guaranteed to get one of the (possibly)
alternate optima for the
p
-median problem. Let
Z
1
be the objective function value
we obtain and let D
1
D
X
i2
I
X
d
j
c
ij
x
ij
be the demand-weighted total distance
corresponding to this solution and U
1
D
X
i2
I
j2
J
X
d
j
O
c
ij
x
ij
be the total uncovered
j2
J
demand corresponding to this solution. Next, solve the problem with Ǜ
2
D
2
,
where
2
>0is a suitably small value such that we are guaranteed to get one
of the (possibly) alternate optima for the maximum covering problem. Let
Z
2
be
the corresponding objective function value and let
D
2
and
U
2
be the demand-
weighted total distance and uncovered demand corresponding to this solution. We
then solve Ǜ
3
D
1
C
.1
Ǜ
3
/U
1
D
Ǜ
3
D
2
C
.1
Ǜ
3
/U
2
for Ǜ
3
. This results in
Ǜ
3
D
U
2
U
1
=
D
1
D
2
C
U
2
U
1
. We then use this value of Ǜ to weight
the two objectives. This will either result in a new solution being found with a
demand-weighted total distance of
D
3
and uncovered demand
U
3
, or the solution
will return one of the two original solutions on the tradeoff curve. If a new solution
is found, the procedure continues by exploring the region between solution 1 and
solution 3 (i.e., using Ǜ
4
D
.U
3
U
1
/=.D
1
D
3
C
U
3
U
1
/) and then between
solution 3 and solution 2. If no new solution is found, then no new solution can
be identified between solutions 1 and 2. This process continues until all adjacent
solutions have been explored in this manner. As a final note, we observe that this
is the weighting method, which will fail to find the so-called duality gap solutions
(Cohon
1978
).
The tradeoff between the demand weighted total distance and the maximum
distance—the
p
-center objective—can also be found using formulation (
2.1
)-(
2.6
)if
we suitably modify the distance (or cost) matrix, assuming all distances are integer
valued. (This is not an overly restrictive assumption since we can approximate any
real distances by integer values. For example, if we need distances accurate to the
nearest 0.01 mile (or about 50 ft) we just multiply all distances by 100 and round the
resulting values.) We do so by initially solving the problem as formulated, letting
c
ij
be the distance between demand node j
2
.
We record the maximum distance,
D
max
. We then modify the distance matrix so
that c
new
J
and candidate location i
2
I
ij
D
c
ij
if
c
ij
<D
max
,where
M
is a very large number. We then resolve
formulation (
2.1
)-(
2.6
) replacing the original costs or distances
c
ij
by
c
new
M
if
c
ij
D
max
ij
.If
M
is
sufficiently large, the new solution will not entail assignments with distances greater
than or equal to
D
max
.LetD
max
<D
max
be the new maximum distance. The process
continues in this manner until no feasible solution can be found, indicating that the
final value of
D
max
that was obtained is the solution to the
p
-center problem. While
