Geoscience Reference
In-Depth Information
Fig. 18.1
Plot of demand
points and aggregate demand
points
40
30
20
10
0
0
10
20
30
40
X COORDINATE (MILES)
Customers
Aggregate Customers
v
j
to keep this error bound small keeps the covering error small. Note, if there are
n
distinct
v
j
,thatmax
n
d
v
j
;v
0
j
W
j
D
1;:::;n
o
may be viewed as the objective
function of an
n
-center problem with DPs
v
j
and facility locations defined by the
v
j
. This observation indicated that it would be reasonable to modify some
p-
center
algorithm to locate the ADPs. As discussed in Dekle et al. (
2005
), the team used
a variation of a Dyer and Frieze (
1985
) pick-the-farthest (PTF) algorithm to pick
the ADPs. Possible center locations were also similarly aggregated. Figure
18.1
illustrates that the algorithm chooses well-dispersed locations. A number of runs of
the PTF algorithm were made, and finally solutions were chosen that reduced the
number of DPs from 6,600 to 198 and the number of potential DRC sites from 3,900
to 162.
The teams' version of the Dyer-Frieze algorithm works as follows. First, an
arbitrary DP is chosen as an ADP. Next, a DP whose closest-distance to an ADP
is farthest is then chosen to be an ADP. Continuing, at each iteration a DP is chosen
as an ADP whose closest-distance to the collection of ADPs is farthest. This process
continues until the closest-distance of every remaining DP to the collection of ADPs
is no more than a “control parameter”
b
. This parameter may be adjusted to provide
a computationally manageable number of ADPs. Dyer and Frieze give a low-order
implementation of this approach.
Subsequently, the covering location model is solved using the ADPs as DPs; the
model formulation guarantees that each ADP will be within the radius
r
of at least
one center. However, original DPs not chosen as ADPs may possibly not be within
such a radius
r
; supposing that
v
is any such unchosen DP, the algorithm guarantees
that some ADP, say
v
0
, satisfies
d
(
v
0
,
v
)
b
. Thus for any center
s
that covers
v
0
,
d(s
,
v
)
d(s
,
v
0
)
C
d(v
0
,
v
)
r
C
b
. Hence if
b
can be kept small then the uncovered
DPs will be nearly covered, as was true in this application (see Table
18.1
).
