Geoscience Reference
In-Depth Information
10.4
The Ordered Median Problem on Networks
Let N
D
.G;`/ denote a network with underlying graph G
D
.V;E/, with node
set V
Df
v
1
;:::;v
n
g
and edge set E
Df
e
1
;:::;e
m
g
. We restrict ourselves to
undirected graphs. Therefore, we write every edge e
2
E as
f
i;j
g
;v
i
;v
j
2
V .
Each edge e
2
E is associated with a positive length by means of the function
`
W
E
!
R
C
.Byd.v
i
;v
j
/, we denote the length of the shortest path between v
i
and v
j
measured by `. Through
w
W
V
!
R
C
[f
0
g
, every vertex is assigned a non
negative weight.
A point x on an edge e
Df
i;j
g
is defined as a pair x
D
.e;t/; t
2
Œ0;1, with
d.v
k
;x/
WD
d.x;v
k
/
WD
min
f
d.v
k
;v
i
/
C
t`.e/;d.v
k
;v
j
/
C
.1
t/`.e/
g
: (10.26)
The set of all the points of a network .G;`/ is denoted by P.G/. It should be
noted that this set also contains the nodes V .
10.4.1
The Single Facility Ordered Median Problem
In this section we deal with the simplest version of the ordered median problem on
networks where just a single location is placed. In order to do that, we consider the
following notation. Let
d.x/
WD
.
w
1
d.v
1
;x/;:::;
w
n
d.v
n
;x//
and
d
.x/
WD
.
w
.1/
d.v
.1/
;x/;:::;
w
.n/
d.v
.n/
;x//
a permutation of the elements of d.x/, verifying
w
.1/
d.v
.1/
;x/
w
.2/
d.v
.2/
;x/
:::
w
.n/
d.v
.n/
;x/:
For the sake of simplicity, let d
.i/
.x/
WD
w
.i/
d.v
.i/
;x/.
The ordered median problem on N is defined as
X
n
f
.d.x//
WD
i
d
.i/
.x/ with
D
.
1
;:::;
n
/
0;
(10.27)
iD1
and
M./
WD
min
x2P.G/
f
.d.x//:
(10.28)
