nach oben

Erschienen in:

2011 | OriginalPaper | Buchkapitel

3. Median Problems in Networks

verfasst von : Vladimir Marianov, Daniel Serra

Erschienen in: Foundations of Location Analysis

Verlag: Springer US

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Suppose a number of geographically distributed customers are demanding a service or good, and facilities providing it need to be optimally located. Once facilities are deployed, either customers travel to the facilities to satisfy their needs, or vehicles travel from the facilities to customers’ locations, carrying the goods to be delivered. The p-median problem finds the optimal location of exactly p facilities, so that the sum of the distances between customers and their closest facilities, measured along the shortest paths, is minimized. Since the number n of customers is known, by dividing the objective by n, the minimum average distance between customers and facilities is obtained too.

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 Uncapacitated and Capacitated Facility Location Problems

Nächstes Kapitel Continuous Center Problems

Arbib C, Marinelli F (2004) An optimization model for trim loss minimization in an automotive glass plant. Eur J Oper Res 183:1421–1432

Balinski ML (1965) Integer programming: methods, uses and computation. Manag Sci 12:253–313

Berman O, Larson RC, Chiu SS (1985) Optimal server location on a network operating as an M/G/1 Queue. Oper Res 33:746–771

Berman O, Odoni AR (1982) Locating mobile servers on a network with Markovian properties. Networks 12:73–86

Brandeau ML, Chiu SS (1989) An overview of representative problems in location research. Manag Sci 35:645–674

Calvo A, Marks H (1973) Location of health care facilities: an analytical approach. Socio-Econ Plan Sci 7:407–422

Christofides N (1975) Graph theory—an algorithmic approach. Academic Press, London

Church R, Meadows ME (1979) Location modeling utilizing maximum service distance criteria. Geogr Anal 11:358–373

Cooper L (1963) Location–allocation problems. Oper Res 11:331–343

Cooper L (1964) Heuristic methods for location–allocation problems. SIAM Rev 6:37–53

Drezner Z (1987) Heuristic solution methods for two location problems with unreliable facilities. J Oper Res Soc 38:509–514

Drezner T, Drezner Z (2007) The gravity p-median model. Eur J Oper Res 179:1239–1251

Efroymson MA, Ray TL (1966) A branch-bound algorithm for plant location. Oper Res 14:361–368

Frank H (1966) Optimum locations on a graph with probabilistic demands. Oper Res 14:409–421

Gass S (1958) Linear programming, 1st edn. McGraw-Hill, New York

Goldman AJ (1969) Optimal locations for centers in a network. Transp Sci 3:352–360

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

Goldman AJ (1972) Approximate localization theorems for optimal facility placement. Transp Sci 6:407–418

Gülicher H (1965) Einige Eigenschaften optimaler Standorte in Verkehrsnetzen. Schr Ver Socialpolit 42:111–137

Hakimi SL (1964) Optimal location 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, Maheshwari SN (1972) Optimum locations of centers in networks. Oper Res 20:967–973

Hale TS, Moberg CR (2003) Location science research: a review. Ann Oper Res 123:21–35

Hansen P, Jaumard B (1997) Cluster analysis and mathematical programming. Math Program 79:191–215

Hillsman E, Rhoda R (1978) Errors in measuring distance from populations to service centers. Ann Reg Sci Assoc 12:74–88

Holmes J, Williams F, Brown L (1972) Facility location under maximum travel restriction: an example using day care facilities. Geogr Anal 4:258–266

Hooker JN, Garfinkel RS, Chen CK (1991) Finite dominating sets for network location problems. Oper Res 39:100–118

Hortel J, Lobo JM (2005) An ED-based protocol of optimal sampling of biodiversity. Biodivers Conserv 14:2913–2947

Hua Lo-Keng, others (1962) Application of mathematical methods to wheat harvesting. Chin Math 2:77–91

Kariv O, Hakimi SL (1979) An algorithmic approach to network location problems. Part II: The p-medians. SIAM J Appl Math 37:539–560

Kolesar P (1980) Testing for vision loss in glaucoma suspects. Manag Sci 26:439–450

Kuehn AA, Hamburger MJ (1963) A heuristic program for locating warehouses. Manag Sci 9:643–666

Land AH, Doig AG (1960) An automatic method for solving discrete programming problems. Econometrica 28:497–520

Levy J (1972) An extended theorem for location on a network. Oper Res Q 18:433–442

Maranzana F (1964) On the location of supply points to minimize transport costs. Oper Res Q 15:261–270

Marianov V (2003) Location of multiple-server congestible facilities for maximizing expected demand, when services are non-essential. Ann Oper Res 123:125–141

Marianov V, Serra D (1998) Probabilistic maximal covering location-allocation models for congested systems. J Reg Sci 13:401–424

Marianov V, Serra D (2001) Hierarchical location-allocation models for congested systems. Eur J Oper Res 135:195–208

Marianov V, Serra D (2002) Location problems in the public sector. In: Drezner Z, Hamacher H (eds) Facility location: applications and theory. Springer, Berlin

Marianov V, Taborga P (2001) Optimal location of public health centres which provide free and paid services. J Oper Res Soc 52:391–400

Minieka E (1977) The centers and medians of a graph. Oper Res 25:641–650

Mirchandani PB (1980) Locational decisions on stochastic networks. Geogr Anal 12:172–183

Mirchandani PB (1990) The p-median problem and generalizations. In: Mirchandani PB, Francis RL (eds) Discrete location theory. Wiley, New York

Mirchandani PB, Odoni AR (1979) Locations of medians on stochastic networks. Transp Sci 13:85–97

Mladenović N, Brimberg J, Hansen P, Moreno-Pérez JA (2007) The p-median problem: a survey of metaheuristic approaches. Eur J Oper Res 179:927–939

Morris J (1978) On the extent to which certain fixed-charge depot location problems can be solved by LP. J Oper Res Soc 29:71–76

Narula SC (1984) Hierarchical location–allocation problems: a classification scheme. Eur J Oper Res 15:183–189

Ng RT, Han J (1994) Efficient and effective clustering methods for spatial data mining. Proceedings of the 20th international conference on very large data bases. Santiago pp 144–154

Reese J (2006) Solution methods for the p-median problem: an annotated bibliography. Networks 48:125–142

ReVelle CS, Swain RW (1970) Central facilities location. Geogr Anal 2:30–42

Rojeski P, ReVelle C (1970) Central facilities location under an investment constraint. Geogr Anal 2:343–360

Rosing K, ReVelle C, Rosing-Vogelaar H (1979) The p-median model and its linear programming relaxation: an approach to large problems. J Oper Res Soc 30:815–823

Serra D, Marianov V (1998) The p-median problem in a changing network: the case of Barcelona. Locat Sci 6:383–394

Shiode S, Drezner Z (2003) A competitive facility location problem on a tree network with stochastic weights. European J Oper Res 149:47–52

Snyder LV (2006) Facility location under uncertainty: a review. IIE Trans 38:537–554

Tansel BC, Francis RL, Lowe TJ (1983a) Location on networks: a survey. Part I: the p-center and p-median problems. Manag Sci 29:482–497

Tansel BC, Francis RL, Lowe TJ (1983b) Location on networks: a survey. Part II: exploiting tree network structure. Manag Sci 29:498–511

Teitz M, Bart P (1968) Heuristic methods for estimating the generalized vertex median of a weighted graph. Oper Res 16:955–961

Toregas C, Swain RW, ReVelle CS, Bergman L (1971) The location of emergency service facilities. Oper Res 19:1363–1373

Wesolowsky GO, Truscott WG (1975) The multiperiod location–allocation problem with relocation of facilities. Manag Sci 22:57–65

Won Y (2000) New p-median approach to cell formation with alternative process plans. Int J Prod Res 38:229–240

Titel: Median Problems in Networks
verfasst von: Vladimir Marianov
Daniel Serra
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_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner