Ordered Median Location Problems - Location Science - page 257

This easy example shows the limit for the set Cand D V [ EQ to be a FDS (finite
dominating set) for the multifacility extension of our model. In the literature we
can find some characterizations of FDS for particular cases of the p-facility ordered
median problem. For instance, Kalcsics et al. ( 2003 ) studies the multifacility ordered
median problem where the -weights are defined as:

a D 1 D ::: D k ¤ kC1 D ::: D n D b;

for a fixed k, such that, 1 k<n. They prove that the set Y ,definedby( 10.31 ), is
a FDS for this problem.
However, none of these papers deals with the general case of the multifacility
ordered median problem. In fact, these papers impose very restrictive hypotheses
such that their respective results can not be extended further. In the following section
we characterize a FDS for the general 2-facility ordered median problem.

10.4.2.1 A Finite Set of Candidates for the Two Facility Case

In this section we identify a finite set of candidates to be optimal solutions of the
2-facility ordered median problem. In order to consider the set of equilibrium points
as a finite set we will assume that EQ only contains the equilibrium points that are
isolated and the extreme points of the subedges in equilibrium, see Rodríguez-Chía
et al. ( 2005 ) for further details.

Theorem 10.8 Consider the following sets:

R Df r W r D w i d.v i ;y/;v i 2 V; y 2 V [ EQ g ;
Y.r/ Df y 2 P.G/ W w i d.v i ;y/ D r; v i 2 V g with r 2 R;
Y D [
r2R

Y.r/; (10.31)

T DfX 2 D .x 1 ;x 2 / 2 P.G/ P.G/ W9v r ;v s served by x 1 and v r 0 ;v s 0 served by x 2 ; such
that w r d.v r ;x 1 /D w r 0 d.v r 0 ;x 2 / and w s d.v s ;x 1 /D w s 0 d.v s 0 ;x 2 /: Moreover, if w r D w r 0
and w s D w s 0 , then the slopes of the functions d.v r ;/ and d.v s ;/ , in the edge that
x 1 belongs to, must have the same signs at x 1 and the slopes of the functions d.v r 0 ;/
and d.v s 0 ;/ , in the edge that x 2 belongs to, must have different signs at x 2 g:

F D .. EQ [ V/ Y/ [ T P.G/ P.G/: (10.32)

The set F is a finite set of candidates to be optimal solutions of the 2 -facility ordered
median problem in the network N .