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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Pioneering Developments in Location Analysis Kapitel lesen Erstes Kapitel lesen

2011 | OriginalPaper | Buchkapitel

5. Discrete Center Problems

verfasst von : Barbaros Ç. Tansel

Erschienen in: Foundations of Location Analysis

Verlag: Springer US

Einloggen

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

search-config
loading …

Abstract

Our focus in this chapter is on discrete center location problems. This class of problems involves locating one or more facilities on a network to service a set of demand points at known locations in such a way that every demand receives its service from a closest facility, and the maximum distance between a demand and a closest facility is as small as possible. This leads to a minimax type of objective function, which is intrinsically different from the minisum objective that is more widely encountered in location models, for which the primary concern is to minimize the total transportation cost. The term discrete in the title refers to a finite set of demand points, while continuous versions of center location problems are also possible if the set of demand points to be served constitutes a continuum of points on the network under consideration.

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 Continuous Center Problems
Nächstes Kapitel Covering Problems
Literatur
Bozkaya B, Tansel B (1998) A spanning tree approach to the absolute p-center problem. Locat Sci 6:83–107
Chen ML, Francis RL, Lowe TJ (1988) The 1-center problem: exploiting block structure. Transp Sci 22:259–269
Christofides N (1975) Graph theory: an algorithmic approach. Academic, New York
Christofides N, Viola P (1971) The optimum location of multi-centers on a graph. Oper Res Quart 22:145–154
Dantzig GB (1967) All shortest routes in a graph. Theory of Graphs, International Symposium, Rome, 1966, Gordon and Breach, New York, pp 91–92
Dearing PM (1977) Minimax location problems with nonlinear costs. J Res Natl Bur Stand 82:65–72
Dearing PM, Francis RL (1974) A minimax location problem on a network. Transp Sci 8:333–343
Dearing PM, Francis RL, Lowe RL (1976) Convex location problems on tree networks. Oper Res 24:628–642
Elloumi S, Labbé M, Pochet Y (2004) A new formulation and resolution method for the p-center problem. INFORMS J Comput 16:84–94
Floyd RW (1962) Algorithm 97, shortest path. Commun ACM 5:345
Francis RL (1977) A note on nonlinear location problem in tree networks. J Res Natl Bur Stand 82:73–80
Frank H (1967) A note on graph theoretic game of Hakimi’s. Oper Res 15:567–570
Frederickson GN, Johnson DB (1983) Finding k-th paths and p-centers by generating and searching good data structures. J Algorithms 4:61–80
Garfinkel RS, Neebe AW, Rao MR (1977) The m-center problem: minimax facility location. Manag Sci 23:1133–1142
Goldman AJ (1971) Optimal center location in simple networks. Transp Sci 5:212–221
Goldman AJ (1972) Minimax location of a facility in a network. Transp Sci 6:407–418
Goldman AJ, Witzgall CJ (1970) A localization theorem for optimal facility placement. Transp Sci 4:406–409
Hakimi SL (1964) Optimum locations of switching centers and the absolute centers and medians of a graph. Oper Res 12:450–459
Hakimi SL (1965) Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Oper Res 13:462–475
Hakimi SL, Schmeichel EF, Pierce JG (1978) On p-centers in networks. Transp Sci 12:1–15
Halfin S (1974) On finding the absolute and vertex centers of a tree with distances. Transp Sci 8:75–77
Halpern J (1979) A simple edge elimination criterion in a search for the center of a graph. Manag Sci 25:105–113
Handler GY (1973) Minimax location of a facility in an undirected tree graph. Transp Sci 7:287–293
Handler GY (1974) Minimax network location: theory and algorithms. Ph.D. Thesis, Technical Report No. 107, Operations Research Center, M.I.T., Cambridge, MA
Handler GY (1978) Finding two-centers of a tree: the continuous case. Transp Sci 12:93–106
Hedetniemi SM, Cockayne EJ, Hedetniemi ST (1981) Linear algorithms for finding the Jordan center and path center of a tree. Transp Sci 15:98–114
Hooker J (1986) Solving nonlinear single-facility network location problems. Oper Res 34:732–743
Hooker J (1989) Solving nonlinear multiple-facility network location problems. Networks 19:117–133
Hooker JN, Garfinkel RS, Chen CK (1991) Finite dominating sets for network location problems. Oper Res 39:100–118
Jaeger M, Kariv O (1985) Algorithms for finding p-centers on a weighted tree (for relatively small p). Networks 15:381–389
Jordan C (1869) Sur les assemblages de lignes. J reine angew Math 70:185–190
Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems: the p-centers. SIAM J Appl Math 37:513–538
Kincaid RK, Lowe TJ (1990) Locating an absolute center on graphs that are almost trees. Eur J Oper Res 44:357–372
Lin CC (1975) On vertex addends in minimax location problems. Transp Sci 9:165–168
Megiddo N (1983) Linear-time algorithms for linear programming in \({\mathbb{R}^2}\) and related problems. SIAM J Comput 12:759–776
Megiddo N, Tamir A (1983) New results on the complexity of p-center problems. SIAM J Comput 12:751–758
Megiddo N, Tamir A, Zemel E, Chandrasekaran R (1981) An O(n log2n) algorithm for the k-th longest path in a tree with applications to location problems. SIAM J Comput 12:328–337
Minieka E (1970) The m-center problem. SIAM Rev 12:138–139
Minieka E (1977) The centers and medians of a graph. Oper Res 25:641–650
Minieka E (1981) A polynomial time algorithm for finding the absolute center of a network. Networks 11:351–355
Mirchandani PB, Francis RL (eds) (1990) Discrete location theory. Wiley, New York
Moreno JA (1986) A new result on the complexity of the p-center problem. Technical Report, Universidad Complutense, Madrid, Spain
Odoni AR (1974) Location of facilities on a network: a survey of results. Technical Report No. TR-03-74, Operations Research Center, M.I.T., Cambridge, MA
Sforza A (1990) An algorithm for finding the absolute center of a network. Eur J Oper Res 48:376–390
Shaw DX (1999) A unified limited column generation approach for facility location problems on trees. Ann Oper Res 87:363–382
Shier DR (1977) A min-max theorem for p-center problems on a tree. Transp Sci 11:243–252
Shier DR, Dearing PM (1983) Optimal locations for a class of nonlinear, single-facility location problems on a network. Oper Res 31:292–302
Tamir A (1988) Improved complexity bounds for center location problems on networks by using dynamic data structures. SIAM J Discrete Math 1:377–396
Tansel BC, Francis RL, Lowe TJ, Chen ML (1982) Duality and distance constraints for the nonlinear p-center problem and covering problem on a tree network. Oper Res 30:725–744
Toregas C, Swain R, ReVelle C, Bergman L (1971) The location of emergency service facilities. Oper Res 19:1363–1373
Metadaten
Titel
Discrete Center Problems
verfasst von
Barbaros Ç. Tansel
Copyright-Jahr
2011
Verlag
Springer US
Buch
Foundations of Location Analysis

Print ISBN: 978-1-4419-7571-3

Electronic ISBN: 978-1-4419-7572-0

Copyright-Jahr: 2011

DOI
https://doi.org/10.1007/978-1-4419-7572-0_5

Premium Partner

    Bildnachweise