Location Problems with Multiple Criteria - Location Science - page 201

d !

In our proofs we use the concept of level sets. For a function f W R R the

d W f.x/ g (the

level set for a value 2 R is given by L .f;/ WD f x 2 R

d W f.x/< g ) and the level curve for a value

strict level set is L < .f;/ WDf x 2 R

d W f.x/ D g : For a function f i . / we use

2 R is given by L D .f;/ WDf x 2 R

the notation

.f i / WD arg min
x2 R

f i .x/:

X

d

For two points x and y we denote the segment defined by x and y as xy .
In this chapter we focus on some fundamental results in the continuous,
network and discrete cases. We will describe in some detail a complete geometric
characterization for the planar 1-facility case, an optimal time algorithm for the
1-facility network problem as well as the computation of the entire set of Pareto-
optimal solutions of the discrete multicriteria p-median problem. Although we are
concentrating on the median case we will give some outlook to extensions.

9.2 1 -Facility Planar/Continuous Location Problems

In this section we study Problem ( 9.1 )wheref 1 . /;:::;f Q . / are convex, inf-
compact functions, defined in

2 , which represent different criteria or scenarios.
Recall that a real function f. / is said to be inf-compact if its lower level sets
f x 2

R

d W f.x/ g are compact for any 2

. The next result states a
useful characterization of the different solution sets defined in the previous section
using level sets and level curves which will be used later.

R R

Theorem 9.1 The following characterizations hold :

Q

\

X wPar f 1 ;:::;f Q ,

L < .f q ;f q .x// D; x 2 (9.2)

qD1

Q Q

\ \

X Par f 1 ;:::;f Q , L .f q ;f q .x// D L D .f q ;f q .x//

x 2

qD1 qD1

(9.3)

Q

\

X sPar f 1 ;:::;f Q , L .f q ;f q .x// Df x g : x 2 (9.4)

qD1