Geoscience Reference
In-Depth Information
10.3
The Continuous Ordered Median Problem
This section is devoted to the analysis of the Ordered Median Location Problem
in a continuous framework. For the ease of understanding, we have divided this
section in two main parts. In the first one, we restrict ourselves to the polyhedral
gauges emphasizing the planar case. In this setting one can derive nice geometrical
properties that help to capture the main elements of the problem, namely its
linearity domains, ordered regions and intuitive algorithms for obtaining the optimal
solutions. Second, we address the general case where we shall apply a new global
optimization technique that allows us to handle and solve a wide range of ordered
median location problems.
10.3.1
The Single Facility Polyhedral Ordered Median
Location Problem
n
(representing existing
facilities or clients) and two sets of non negative scalars
w
D
.
w
1
;:::;
w
n
/ and
D
.
1
;:::;
n
/. The element
w
i
is the weight assigned to the existing facility a
i
and it represents the importance of this demand point. The elements of allow us
to choose between different kinds of objective functions. We also consider a gauge
.
/
W
Consider a set of demand points A
Df
a
1
;a
2
;:::;a
n
g
R
n
!
to measure distances. Recall that any gauge is defined by the
Minkowski functional of a compact, convex set with the zero in its interior (see
Nickel and Puerto
2005
).
The ordered median problem is given by:
R
R
min
x2
R
n
F.x/
Dh
;
sort
n
...x
a
1
/;:::;.x
a
n
///
i
:
(10.4)
Note that the problem is well-defined even if ties occur. In that case any order of the
tied positions gives the same value.
Example 10.1
Consider two demand points a
1
D
.0;0/ and a
2
D
.10;5/,
1
D
100
and
2
D
1 with `
1
-norm and
w
1
D
w
2
D
1. We obtain only two optimal solutions
to problem (
10.4
), lying in each demand point. Observe that a linear representation
of the objective function is regionwise defined and that the objective function is not
convex since we have a nonconvex optimal solution set. See Fig.
10.1
.
F.a
1
/
D
100
0
C
1
15
D
15
F.a
2
/
D
100
0
C
1
15
D
15
F.
1
2
.a
1
C
a
2
//
D
100
7:5
C
1
7:5
D
757:5
