Geoscience Reference
In-Depth Information
Chapter 10
OrderedMedianLocationProblems
Justo Puerto and Antonio M. Rodríguez-Chía
Abstract
This chapter analyzes the ordered median location problem in three
different frameworks: continuous, discrete and networks; where some classical but
also new results have been collected. For each solution space we study general
properties that lead to resolution algorithms. In the continuous case, we present two
solution approaches for the planar case with polyhedral norms (the most intuitive
case) and a novel approach applicable for the general case based on a hierarchy
of semidefinite programs that can approximate up to any degree of accuracy the
solution of any ordered median problem in finite dimension spaces with polyhedral
or `
p
-norms. We also cover the problems on networks deriving finite dominating
sets for some particular classes of parameters and showing the impossibility of
finding a FDS with polynomial cardinality for general lambdas in the multifacility
case. Finally, we present a covering based formulation for the capacitated discrete
ordered median problem with binary assignment which is rather promising in terms
of gap and CPU time for solving this family of problems.
Keywords
Finite dominating set Mixed integer linear programming Ordered
median function
10.1
Introduction
The Ordered Median location problem, see Nickel and Puerto (
2005
), has been
recognized as a powerful tool from a modeling point of view within the field of
Location Analysis. Actually, this problem provides a common framework for most
of the classical location problems (median, center, k-centrum, centdian, trimmed-
mean, among others) as well as for others which have not been studied before. As an
illustrative example, in the well-known case of logistics supply chain networks,
