Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction to Location Science Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

4.  p-Center Problems

verfasst von : Hatice Calik, Martine Labbé, Hande Yaman

Erschienen in: Location Science

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

A p-center is a minimax solution that consists in a set of p points that minimizes the maximum distance between a demand point and a closest point belonging to that set. We present different variants of that problem. We review special polynomial cases, determine the complexity of the problems and present mixed integer linear programming formulations, exact algorithms and heuristics. Several extensions are also reviewed.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Fixed-Charge Facility Location Problems
Nächstes Kapitel Covering Location Problems
Literatur
Albareda-Sambola M, Díaz JA, Fernández E (2010) Lagrangean duals and exact solution to the capacitated p-center problem. Eur J Oper Res 201:71–81CrossRef
Averbakh I (1997) On the complexity of a class of robust location problems. Working paper. Western Washington University, Bellingham
Averbakh I, Berman O (1997) Minimax regret p-center location on a network with demand uncertainty. Locat Sci 5:247–254CrossRef
Averbakh I, Berman O (2000) Algorithms for the robust 1-center problem on a tree. Eur J Oper Res 123:292–302CrossRef
Bar-Ilan J, Kortsarz G, Peleg D (1993) How to allocate network centers. J Algorithm 15:385–415CrossRef
Beasley JE (1990) OR-Library: distributing test problems by electronic mail. J Oper Res Soc 41:1069–1072CrossRef
Berge B (1967) Théorie des graphes et ses applications. Dunod, Paris
Berman O, Drezner Z (2008) A new formulation for the conditional p-median and p-center problems. Oper Res Lett 36:481–483CrossRef
Berman O, Simchi-Levi D (1990) Conditional location problems on networks. Transp Sci 24:77–78CrossRef
Bozkaya B, Tansel B (1998) A spanning tree approach to the absolute p-center problem. Locat Sci 6:83–107CrossRef
Calik H (2013) Exact solution methodologies for the p-center problem under single and multiple allocation strategies. Ph.D. thesis, Bilkent University, Ankara
Calik H, Tansel BC (2013) Double bound method for solving the p-center location problem. Comput Oper Res 40:2991–2999CrossRef
Chechik S, Peleg D (2012) The fault tolerant capacitated k-center problem. In: Structural information and communication complexity. Springer, Berlin/Heidelberg
Chen D, Chen R (2013) Optimal algorithms for the α-neighbor p-center problem. Eur J Oper Res 225:36–43CrossRef
Daskin MS (2013) Network and discrete location: models, algorithms, and applications, 2nd edn. Wiley, HobokenCrossRef
Drezner Z (1989) Conditional p-center problems. Transp Sci 23:51–53CrossRef
Dyer ME, Frieze AM (1985) A simple heuristic for the p-center problem. Oper Res Lett 3:285–288CrossRef
Elloumi S, Labbé M, Pochet Y (2004) A new formulation and resolution method for the p-center problem. INFORMS J Comput 16:84–94CrossRef
Garfinkel R, Neebe A, Rao M (1977) The m-center problem: minimax facility location. Manag Sci 23:1133–1142CrossRef
Goldman AJ (1972) Minimax location of a facility in a network. Transp Sci 6:407–418CrossRef
Hakimi SL (1964) Optimum locations of switching centers and the absolute centers and medians of a graph. Oper Res 12:450–459CrossRef
Hakimi SL (1965) Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Oper Res 13:462–475CrossRef
Handler GY (1973) Minimax location of a facility in an undirected tree network. Transp Sci 7:287–293CrossRef
Hansen P, Labbé M, Nicloas B (1991) The continuous center set of a network. Discrete Appl Math 30:181–195CrossRef
Hochbaum DS, Shmoys DB (1985) A best possible heuristic for the k-center problem. Math Oper Res 10:180–184CrossRef
Hsu W-L, Nemhauser GL (1979) Easy and hard bottleneck location problems. Discrete Appl Math 1:209–215CrossRef
Jaeger M, Goldberg J (1994) A polynomial algorithm for the equal capacity p-center problem on trees. Transp Sci 28:167–175CrossRef
Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems. I: the p-centers. SIAM J Appl Math 37:513–538CrossRef
Khuller S, Sussmann YJ (2000) The capacitated k-center problem. SIAM J Discrete Math 13:403–418CrossRef
Khuller S, Pless R, Sussmann YJ (2000) Fault tolerant K-center problems. Theor Comput Sci 242:237–245CrossRef
Krumke OS (1995) On a generalization of the p-center problem. Inform Process Lett 56:67–71CrossRef
Lorena LAN, Senne ELF (2004) A column generation approach to capacitated p-median problems. Comput Oper Res 31:863–876CrossRef
Martinich JS (1988) A vertex-closing approach to the p-center problem. Nav Res Log 35:185–201CrossRef
Megiddo N (1983) Linear-time algorithms for linear programming in R 3 and related problems. SIAM J Comput 12:759–776CrossRef
Mihelič J, Robič B (2005) Solving the k-center problem efficiently with a dominating set algorithm. J Comput Inform Technol 13:225–233CrossRef
Minieka E (1980) Conditional centers and medians on a graph. Networks 10:265–272CrossRef
Mladenović N, Labbé M, Hansen P (2003) Solving the p-center problem with tabu search and variable neighborhood search. Networks 42:48–64CrossRef
Ozsoy FA, Pinar MC (2006) An exact algorithm for the capacitated vertex p-center problem. Comput Oper Res 33:1420–1436CrossRef
Pullan W (2008) A memetic genetic algorithm for the vertex p-center problem. Evol Comput 16:417–436CrossRef
Reinelt G (1991) TSPLIB - a traveling salesman problem library. ORSA J Comput 3:376–384CrossRef
Salhi S, Al-Khedhairi A (2010) Integrating heuristic information into exact methods: the case of the vertex p-centre problem. J Oper Res Soc 61:1619–1631CrossRef
Scapparra MP, Pallotino S, Scutella MG (2004) Large-scale local search heuristics for the capacitated vertex p-center problem. Networks 43:241–255CrossRef
Tamir A (1987) On the solution value of the continuous p-center location problem on a graph. Math Oper Res 12:340–349CrossRef
Tamir A (1988) Improved complexity bounds for center location problems on networks fy using dynamic data structures. SIAM J Discrete Math 1:377–396CrossRef
Tansel BÇ (2011) Discrete center problems. In: Eiselt HA, Marianov V (eds) Foundations of location analysis. Springer, New York, pp 79–106CrossRef
Metadaten
Titel
p-Center Problems
verfasst von
Hatice Calik
Martine Labbé
Hande Yaman
Copyright-Jahr
2015
Buch
Location Science

Print ISBN: 978-3-319-13110-8

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

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-13111-5_4