Justo Puerto (Universidad de Sevilla, Spain)
Short
Biography
Justo Puerto graduated in mathematics for
the Universidad de Sevilla where he is currently
full Professor of Statistics and Operations Research. He has been
visiting professor in several universities all around the world:
His research interest covers different areas of Operations Research: Decision Theory, Multicriteria Optimization, Game Theory, Location Analysis or Queuing Theory.
He has published over 80 papers in the most prestigious journals of Operations Research and Applied Mathematics and he is also co-author of several books in the fields of Game Theory, Multiobjective Optimization and Location Theory.
Detailed information can be found at the URL: http://www.us.es/gpb97/curri_sevilla/index.htm
Lecture to be presented in EWI 2007
Title
The
ordered median location location problem: A unified tool for location analysis
Abstract
When
talking about solving a location problem in practice at least the following
phases have to be considered: Definition of the problem, identification of side
constraints, choice of the right objective function(s), data collection, data
analysis (data mining), optimization (actual resolution), visualization of the
results and discussion whether the problem is solved or if the phases have to be
started again.
Typically researchers in location theory have been concentrating very much on
the resolution (optimization phase) of a given problem. The type of the problem
and to some extent also the side constraints were motivated by classical papers
in location theory (see [7, 8]). The idea of having a facility placed at a
location which is in average good for each client, led to the median objective
function (also called Weber or Fermat-Weber objective), see [8]. Finding a
location which is even for the most remote client as good as possible, brought
up the idea of the center objective (see [4]). The insight, that both points of
view might be too extreme, led to the cent-dian approach (see [1]). In addition
researchers always distinguished between continuous, network and discrete
location problems. Therefore, the main scope of researchers can be seen as
picking a problem from the table in Figure 1 by selecting a row and a column,
maybe adding some additional constraints to it, and then finding good solution
procedures.
|
Objective
function |
decision
space |
|||
|
|
continuous |
network |
discrete |
|
|
median |
|
|
|
|
|
Center |
|
|
|
|
|
cent-dian |
|
|
|
|
|
… |
|
|
|
|
Figure 1: A simplified classification of most of the classical location problems.
Although modern location theory is almost 100 years old the focus of the
researchers has been problem oriented. In this direction enormous advances have
been achieved since the first analytical approaches. Today sophisticated tools
from computer science, computational geometry and combinatorial optimization are
applied. However, despite the vast literature of papers and books in location
analysis, searching for a common theory has been an issue only recently
considered. This talk summarizes results published in the last years in several
papers and books. The aim is to present the ordered median objective function a
powerful tool for expressing all relevant location objectives with a single
methodology for all the three major branches of locational analysis: continuous,
network and discrete location problems. Or, looking at the table in Figure 1, a
tool that shrinks its number of rows to a single one.
This talk will present a rigorous mathematical foundation of this tool: the
ordered median function. Then, it will demonstrate its application in modeling
point location problems in continuous, network and discrete frameworks (see
[3]). Finally, in order to show its great potentiality, we will also consider
ordered median problems of dimensional structures (paths or trees) on networks
(see [5, 6]) and lines on the plane [2].
References
[1] J. Halpern. Finding the minimal center-median convex combination (cent-dian)
of a graph. Management Science, 24(5):535-547, 1978.
[2] A. Lozano and F. Plastria. Locating lines on the plane with the ordered
median objetive. Communication presented at ISOLDE X. Seville, 2005.
[3] S. Nickel and J. Puerto. Location Theory: A unified approach. Operations
Research and Decision Theory. Springer, 2005.
[4] F. Plastria. Facility Location: A Survey of Applications and Methods,
chapter Continuous location problems: research, results and questions, pages
85-127. Springer-Verlag, 1995.
[5] J. Puerto and A. Tamir. Locating tree-shaped facilities using the ordered
median objective. Mathematical Programming, 102(2):313-338, 2005.
[6] A. Tamir, J. Puerto, J.A. Mesa, and A.M. Rodriguez-Chía. Conditional
location of path and tree shaped facilities on trees. J. of Algorithms,
56:50-75, 2005.
[7] A. Weber. Ä Uber den Standort der Industrien, TÄubingen, 1909. (English
translation by Friedrich C.J. (1929). Theory of the Location of Industries.
University of Chicago Press, 1929.
[8] G.O. Wesolowsky. The Weber Problem: History and Perspectives. Location
Science, 1:5- 3, 1993.