Top

Published in:

2015 | OriginalPaper | Chapter

9. Location Problems with Multiple Criteria

Authors : Stefan Nickel, Justo Puerto, Antonio M. Rodríguez-Chía

Published in: Location Science

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This chapter analyzes multicriteria continuous, network, and discrete location problems. In the continuous framework, we provide a complete description of the set of weak Pareto, Pareto, and strict Pareto locations for a general Q-criteria location problem based on the characterization of three criteria problems. In the network case, the set of Pareto locations is characterized for general networks as well as for tree networks using the concavity and convexity properties of the distance function on the edges. In the discrete setting, the entire set of Pareto locations is characterized using rational generating functions of integer points in polytopes. Moreover, we describe algorithms to obtain the solutions sets (the different Pareto locations) using the above characterizations. We also include a detailed complexity analysis. A number of references has been cited throughout the chapter to avoid the inclusion of unnecessary technical details and also to be useful for a deeper analysis.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Facility Location Under Uncertainty

next chapter Ordered Median Location Problems

Barvinok A (1994) A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math Oper Res 19:769–779CrossRef

Barvinok A, Woods K (2003) Short rational generating functions for lattice point problems. J Am Math Soc 16:957–979CrossRef

Blanco V, Puerto J (2012) A new complexity result on multiobjective linear integer programming using short rational generating functions. Optim Lett 6:537–543CrossRef

Brion M (1988) Points entiers dans les polyèdres convexes. Ann Sci Ecole Norm S Sér 4 21:653–663

Carrizosa E, Conde E, Fernández FR, Puerto J (1993) Efficiency in Euclidean constrained location problems. Oper Res Lett 14:291–295CrossRef

Chinchuluun A, Pardalos PM (2007) A survey of recent developments in multiobjective optimization. Ann Oper Res 154:29–50CrossRef

Colebrook M, Sicilia J (2007a) A polynomial algorithm for the multicriteria cent-dian location problem. Eur J Oper Res 179:1008–1024CrossRef

Colebrook M, Sicilia J (2007b) Undesirable facility location problems on multicriteria networks. Comput Oper Res 34:1491–1514CrossRef

De Loera JA, Haws D, Hemmecke R, Huggins P, Sturmfels B, Yoshida R (2004) Short rational functions for toric algebra and applications. J Symb Comput 38:959–973CrossRef

De Loera JA, Haws D, Hemmecke R, Huggins P, Yoshida R (2005) A computational study of integer programming algorithms based on Barvinok’s rational functions. Discrete Optim 2:135–144CrossRef

De Loera JA, Hemmecke R, Köppe M (2009) Pareto optima of multicriteria integer linear programs. INFORMS J Comput 21:39–48CrossRef

Dearing P, Francis R, Lowe T (1976) Convex location problems on tree networks. Oper Res 24:628–642CrossRef

Drezner Z (1995) Facility location. A survey of applications and methods. Springer, New YorkCrossRef

Durier R (1990) On Pareto optima, the Fermat–Weber problem, and polyhedral gauges. Math Program 47:65–79CrossRef

Durier R, Michelot C (1985) Geometrical properties of the Fermat-Weber problem. Eur J Oper Res 20:332–343CrossRef

Durier R, Michelot C (1986) Sets of efficient points in a normed space. J Math Anal Appl 117:506–528CrossRef

Edelsbrunner H (1987) Algorithms in combinatorial geometry. Springer, New YorkCrossRef

Ehrgott M (2005) Multicriteria optimization. Springer, Heidelberg

Ehrgott M, Gandibleux X (2000) A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spectrum 22:425–460CrossRef

Ehrgott M, Gandibleux X (2002) Multiple criteria optimization. State of the art annotated bibliographic surveys. Kluwer, Boston

Fernández E, Puerto J (2003) Multiobjective solution of the uncapacitated plant location problem. Eur J Oper Res 145:509–529CrossRef

Gandibleux X, Jaszkiewicz A, Freville A, Slowinski RE (2000) Special issue ‘multiple objective metaheuristics’. J Heuristics 6:291–431CrossRef

Goldman A (1971) Optimal center location in simple networks. Transp Sci 5:212–221CrossRef

Hakimi S (1964) Optimum location of switching centers and the absolute centers and medians of a graph. Oper Res 12:450–459CrossRef

Hamacher H, Nickel S (1996) Multicriteria planar location problems. Eur J Oper Res 94:66–86CrossRef

Hamacher HW, Labbé M, Nickel S (1999) Multicriteria network location problems with sum objectives. Networks 33:79–92CrossRef

Hamacher HW, Labbé M, Nickel S, Skriver AJ (2002) Multicriteria semi-obnoxious network location problems (MSNLP) with sum and center objectives. Ann Oper Res 110:33–53CrossRef

Hansen P, Perreur J, Thisse J (1980) Location theory, dominance and convexity: some further results. Oper Res 28:1241–1250CrossRef

Hansen P, Labbé M, Thisse JF (1991) From the median to the generalized center. RAIRO 25:73–86

Hershberger J (1989) Finding the upper envelope of n line segments in o(\(n\log n\)) time. Inf Process Lett 33:169–174CrossRef

Kalcsics, J., Nickel, S., Puerto, J. and Rodríguez-Chía, A. M. (2014), Several 2-facility location problems on networks with equity objectives. NETWORKS. doi:10.1002/net.21568

Nickel S (1995) Discretization of planar location problems. Ph.D. dissertation, Fachbereich Mathematik, University of Kaiserslautern

Nickel S (1997) Bicriteria and restricted 2-facility weber problems. Math Method Oper Res 45:167–195CrossRef

Nickel S, Puerto J (2005) Location theory: a unified approach. Springer, Berlin/Heildelberg

Nickel S, Puerto J, Rodríguez-Chía AM (2005a) MCDM location problems. In: Figueira JA, Greco S, Ehrogott M (eds) Multiple criteria decision analysis: state of the art surveys. International series in operations research & management science, vol 78. Springer, New York, pp 761–787

Nickel S, Puerto J, Rodríguez-Chía AM, Weissler A (2005b) Multicriteria planar ordered median problems. J Optim Theory Appl 126:657–683CrossRef

Puerto J, Fernández F (1999) Multicriteria minisum facility location problem. J Multi-Criteria Decis Anal 8:268–280CrossRef

Puerto J, Fernández F (2000) Geometrical properties of the symmetrical single facility location problem. J Nonlinear Convex A 1:321–342

Rockafellar R (1970) Convex analysis. Princeton University Press, Princeton

Rodríguez-Chía A, Puerto J (2002) Geometrical description of the weakly efficient solution set for multicriteria location problems. Ann Oper Res 111:179–194CrossRef

Rodríguez-Chía A, Nickel S, Puerto J, Fernández F (2000) A flexible approach to location problems. Math Method Oper Res 51:69–89CrossRef

Ross GT, Soland RM (1980) A multicriteria approach to the location of public facilities. Eur J Oper Res 4:307–321CrossRef

Skriver AJ, Andersen KA, Holmberg K (2004) Bicriteria network location (BNL) problems with criteria dependent lengths and minisum objectives. Eur J Oper Res 156:541–549CrossRef

Ulungu E, Teghem J (1994) Multi-objective combinatorial optimization problems: a survey. J Multi-Criteria Decis Anal 3:83–104CrossRef

Verdoolaege S (2008) Software barvinok. http://freecode.com/projects/barvinok

Warburton A (1983) Quasiconcave vector maximization: connectedness of the sets of pareto-optimal and weak pareto-optimal alternatives. J Optim Theory Appl 40:537–557CrossRef

Weissler A (1999) General bisectors and their application in planar location theory. Shaker, Aachen

Wendell R, Hurter AJ (1973) Location theory, dominance and convexity. Oper Res 21:314–320CrossRef

Wendell R, Hurter A, Lowe T (1977) Efficient points in location problems. AIIE Trans 9:238–246CrossRef

Woods K, Yoshida R (2005) Short rational generating functions and their applications to integer programming. SIAG/OPT Views News 16:15–19

Title: Location Problems with Multiple Criteria
Authors: Stefan Nickel
Justo Puerto
Antonio M. Rodríguez-Chía
Publisher: Springer International Publishing
Book: Location Science
Print ISBN: 978-3-319-13110-8

Electronic ISBN: 978-3-319-13111-5

Copyright Year: 2015
DOI: https://doi.org/10.1007/978-3-319-13111-5_9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner