Geoscience Reference
In-Depth Information
9.3
Network Location Problems
9.3.1
1-Facility Median Problems
9.3.1.1
Pareto Locations in General Networks
Let G
D
.V;E/ be a connected graph with node set V
Df
v
1
;:::;v
n
g
and edge
set E
Df
e
1
;:::;e
m
g
. Each edge e
2
E has a positive length `.e/, and is assumed
to be rectifiable. Let P.G/ denote the continuum set of points on edges of G.We
denote a point x
2
e
Df
u
;v
g
as a pair x
D
.e;t/,wheret (0
t
1)gives
the relative distance of x from node
u
along edge e. For the sake of readability, we
identify P.G/ with G and P.e/ with e for e
2
E.Wealsodefine.e;.t
1
;t
2
//
WD
f
x
D
.e;t/
W
t
2
.t
1
;t
2
/
g
; .e;Œt
1
;t
2
/, .e;.t
1
;t
2
/,and.e;Œt
1
;t
2
// are used in an
analogous way.
We denote by d.x;y/ the length of the shortest path connecting two points
x;y
2
G.Letv
i
2
V and x
D
.
f
v
r
;v
s
g
;t/
2
G. The distance from v
i
to x
entering the edge
f
v
r
;v
s
g
through v
r
(v
s
) is given as D
i
.x/
D
d.v
r
;x/
C
d.v
r
;v
i
/
(D
i
.x/
D
d.v
s
;x/
C
d.v
s
;v
i
/). Hence, the length of a shortest path from v
i
to x is given by D
i
.x/
D
min
f
D
i
.x/; D
i
.x/
g
.Asd.v
r
;x/
D
t
`.e/ and
d.v
s
;x/
D
.1
t/
`.e/, the functions D
i
.x/ and D
i
.x/ are linear in x and D
i
.x/
is piecewise linear and concave in x (cf. Drezner
1995
). The distance from v
i
to a
facility located at x is finally defined as d.v
i
;x/
D
D
i
.x/
D
min
f
D
i
.x/;D
i
.x/
g
.
We consider the objective function f.x/
D
.f
1
.x/;:::;f
Q
.x//, where each
f
q
.x/, q
2
Q
, is a median function defined as:
f
q
.x/
D
X
v
i
2V
w
i
d.v
i
;x/:
More formally, we assign a vector of weights
0
1
w
:
:
:
w
i
@
A
6D
0 to every vertex v
i
2
V; with
w
i
0; q
2
w
i
D
Q
WDf
1;:::;Q
g
:
The quality of a point x
2
P.G/in this multicriteria setting is defined by
0
@
1
A
0
@
P
v
i
2V
w
i
d.x;v
i
/
:
:
:
P
v
i
2V
w
i
d.x;v
i
/
1
A
f
1
.x/
:
:
:
f
Q
.x/
f.x/
WD
WD
