Geoscience Reference
In-Depth Information
network (assumed undirected) then
d
(
x
,
y
) is usually the length of a shortest path
between
x
and
y
. For planar problems when ǝ
D
R
2
, with
x
D
(
1
,
2
),
y
D
(
1
,
2
),
d
(
x
,
y
)isoftenthe`
p
-distance:
jj
x - y
jj
D
Œ
j
1
-
1
j
p
Cj
2
-
2
j
p
1=
p
, with
p
1. Taking
p
D
1 or 2 gives the well-known rectilinear or Euclidean distance,
respectively. The limiting case of the `
p
-distance as
p
goes to infinity, denoted
by
jj
x
y
jj
1
,isgivenby
jj
x - y
jj
1
D
max
fj
1
-
1
j
;
j
2
2
jg
, and is called
the Tchebyshev distance. The Tchebyshev distance in
R
2
is sometimes analytically
convenient because it is known (Francis et al.
1992
) to be equivalent to the planar
rectilinear distance under a 45-degree rotation of the axes. We define the diameter
of ǝ by
diam
.ǝ/
D
sup
f
d.x;y/
W
x;y
2
ǝ
g
, with the understanding that possibly
diam
(ǝ)
DC1
. More generally, ǝ can be a metric space (Goldberg
1976
) with
metric
d
, but no loss of insight occurs by considering the network and planar cases
for ǝ.
Suppose we have
n
DPs,
v
j
2
ǝ,
j
D
1, :::,
n
. Denote the list (or vector) of
DPs by
V
D
(
v
1
, :::,
v
n
). When we aggregate, we replace each DP
v
j
by some
p
ADP
v
j
in ǝ, obtaining an ADP list V
0
D
v
0
1
;:::;v
0
n
. While the DPs are usually
distinct, the ADPs are not, since otherwise there is no computational advantage to
the aggregation. When we wish to model
q
distinct ADPs, we let denote the set
of
q
distinct ADPs, say
Df
1
, :::,
q
g
. We use the former (latter) ADP notation
when the correspondence between DPs and ADPs is (is not) of interest. Usually we
have
q
n
.
For any positive integer
p
,let
S
Df
s
k
, :::,
s
p
g
denote any
p
-server, the set of
locations of the
p
servers,
S
ǝ. (This symbol
p
is a different symbol from the
one defining the `
p
-distance.) Denote the location model with the given original
DPs by
f
(
S
:
V
), and the one with the aggregate DPs by
f
(
S
:
V
0
). The notation
f
(
S
:
V
)
and
f
(
S
:
V
0
) captures a key idea that
an aggregation is a replacement of V by V
0
,
with
the entries of V
0
not all distinct
.
For the large class of location models with similar or indistinguishable
servers, with only the closest one to each DP assumed to serve the DP, for
any
p
-server
S
ǝ and DP
v
2
ǝ we denote by
D
(
S
,
v
)
min
f
d
(
s
k
,
v
):
k
D
1,
:::,
p
g
the distance between
v
and a closest element in
S
. We then define the
closest-distance vectors D.S;V/
D
S;v
j
W
j
D
1;:::;n
;D.S;V
0
/
D
S;v
0
j
W
j
D
1;:::;n
2
R
n
. Suppose
g
is some “costing” function with
C
domain R
n
C
attaching a cost to
D
(
S
,
V
)and
D
(
S
,
V
0
). This gives original and
approximating location models
f
(
S
:
V
)
g
(
D
(
S
,
V
)) and
f
(
S
:
V
0
)
g
(
D
(
S
,
V
0
)),
respectively. Important and perhaps best-known instances of
g
are the
p
-
median and
p
-center costing functions, g.U/
D
w
1
u
1
CC
w
n
u
n
,and
g.U/
D
max
f
w
1
u
1
;:::;
w
n
u
n
g
respectively; the
w
j
are positive constants, often
called “weights”, and may be proportional to the number of trips between servers
and DPs. Thus
f
(
S
:
V
) is either the
p
-median model,
w
1
D
(
S
,
v
1
)
C
:::
C
w
n
D
(
S
,
v
n
),
or the
p
-center model, max
f
w
1
D
(
S
,
v
1
), :::,
w
n
D
(
S
,
v
n
)
g
. These models originate
from Hakimi (
1965
) (each is called unweighted if all
w
j
D
1:
j
D
1, :::,
n
). They are
perhaps the two best-known models in location theory. The covering model, a model
related to the center model, will be described later in this chapter. Subsequently,