Location Problems with Multiple Criteria - Location Science - page 225

Since we delete after every domination step the corresponding node from the tree
according to Algorithm 9.7 and no leaf with status not considered is left we end up
with

X par D LŒv 9 ;v 3 :

9.3.2 Other Multicriteria Location Problems on Networks

In the previous two subsections we presented optimal time algorithms for one
facility median problems when looking for Pareto locations. We chose these two
problems because the reader gets some insight into the needed properties. In
addition, the simplification on trees caused by the uniqueness of paths can be seen.
In the recent survey Nickel et al. ( 2005a ) an overview on other location problems
can be found. In Hamacher et al. ( 2002 ) an extension to 1-facility center problems
as well as to positive and negative weight vectors on the nodes is developed.
Those ideas have been further extended to problems with criteria dependent lengths
in Skriver et al. ( 2004 ). A unified framework for multicriteria ordered median
functions can be found in Nickel and Puerto ( 2005 ). In Colebrook and Sicilia
( 2007b ) the location of undesirable facilities on multicriteria networks is looked
at by using convex combinations of two objective functions. Some complexity
analysis for the cent-dian location problem has been developed by Colebrook and
Sicilia ( 2007a ). Most approaches to the (in general NP-hard) multi-facility case are
treated as discrete location problems (see Sect. 9.4 ). Only recently Kalcsics et al.
( 2014 ) started looking into polynomial cases of multi-facility multicriteria location
problems on networks.

9.4 Discrete Location Problems

The previous sections show that planar and network multicriteria location problems
have been widely developed from a methodological point of view so that important
structural results and algorithms are known to determine solution sets. On the
contrary, multicriteria analysis of discrete location problems has attracted less
attention. In spite of that, several authors have dealt with problems and applications
of multicriteria decision analysis in this field. An annotated bibliography with
many references up to 2005 can be found in Nickel et al. ( 2005a ). In general,
very few papers focus in the complete determination of the whole set of Pareto-
optimal solutions. Nevertheless, there are some exceptions, such as the paper by
Ross and Soland ( 1980 ) that gives a theoretical characterization but does not exploit
its algorithmic possibilities, as well as the work by Fernández and Puerto ( 2003 )
that addresses the computation of the entire set of Pareto-optimal solutions of the
multiobjective uncapacitated plant location problem.