Skip to main content

20.05.2024 | Research Paper

An improved algorithm for solving the Weber location problem

verfasst von: Zvi Drezner

Erschienen in: 4OR

Einloggen

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

search-config
loading …

Abstract

In this note we propose an improved algorithm for the solution of the Weber problem which is the most fundamental problem in location analysis. It is used as a building block in many algorithms for solving more complicated location problems. The algorithm is very simple to implement and the idea behind it can inspire solution approaches to other optimization problems as well. Computational experiments demonstrated the superior performance of the proposed algorithm. Such an improvement will assist in the solution of more complicated models that apply the solution to Weber problem repeatedly many times as part of their solution algorithms.

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!

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!

Literatur
Zurück zum Zitat Brimberg J, Drezner Z (2013) A new heuristic for solving the \(p\)-median problem in the plane. Comput Oper Res 40:427–437CrossRef Brimberg J, Drezner Z (2013) A new heuristic for solving the \(p\)-median problem in the plane. Comput Oper Res 40:427–437CrossRef
Zurück zum Zitat Brimberg J, Love RF (1993) Global convergence of a generalized iterative procedure for the minisum location problem with \(l_p\) distances. Oper Res 41:1153–1163CrossRef Brimberg J, Love RF (1993) Global convergence of a generalized iterative procedure for the minisum location problem with \(l_p\) distances. Oper Res 41:1153–1163CrossRef
Zurück zum Zitat Brimberg J, Hansen P, Mladenović N, Taillard E (2000) Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem. Oper Res 48:444–460CrossRef Brimberg J, Hansen P, Mladenović N, Taillard E (2000) Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem. Oper Res 48:444–460CrossRef
Zurück zum Zitat Brimberg J, Drezner Z, Mladenović N, Salhi S (2014) A new local search for continuous location problems. Eur J Oper Res 232:256–265CrossRef Brimberg J, Drezner Z, Mladenović N, Salhi S (2014) A new local search for continuous location problems. Eur J Oper Res 232:256–265CrossRef
Zurück zum Zitat Brimberg J, Hansen P, Mladonovic N, Salhi S (2008) A survey of solution methods for the continuous location allocation problem. Int J Oper Res 5:1–12 Brimberg J, Hansen P, Mladonovic N, Salhi S (2008) A survey of solution methods for the continuous location allocation problem. Int J Oper Res 5:1–12
Zurück zum Zitat Church RL (2019) Understanding the Weber location paradigm. In: Eiselt HA, Marianov V (eds) Contributions to location analysis—in honor of Zvi Drezner’s 75th birthday. Springer, Switzerland, pp 69–88 Church RL (2019) Understanding the Weber location paradigm. In: Eiselt HA, Marianov V (eds) Contributions to location analysis—in honor of Zvi Drezner’s 75th birthday. Springer, Switzerland, pp 69–88
Zurück zum Zitat Cooper L (1964) Heuristic methods for location-allocation problems. SIAM Rev 6:37–53CrossRef Cooper L (1964) Heuristic methods for location-allocation problems. SIAM Rev 6:37–53CrossRef
Zurück zum Zitat Drezner Z (1992) A note on the Weber location problem. Ann Oper Res 40:153–161CrossRef Drezner Z (1992) A note on the Weber location problem. Ann Oper Res 40:153–161CrossRef
Zurück zum Zitat Drezner Z (1996) A note on accelerating the Weiszfeld procedure. Locat Sci 3:275–279CrossRef Drezner Z (1996) A note on accelerating the Weiszfeld procedure. Locat Sci 3:275–279CrossRef
Zurück zum Zitat Drezner Z (2015) The fortified Weiszfeld algorithm for solving the Weber problem. IMA J Manag Math 26:1–9 Drezner Z (2015) The fortified Weiszfeld algorithm for solving the Weber problem. IMA J Manag Math 26:1–9
Zurück zum Zitat Drezner Z, Simchi-Levi D (1992) Asymptotic behavior of the Weber location problem on the plane. Ann Oper Res 40:163–172CrossRef Drezner Z, Simchi-Levi D (1992) Asymptotic behavior of the Weber location problem on the plane. Ann Oper Res 40:163–172CrossRef
Zurück zum Zitat Drezner Z, Klamroth K, Schöbel A, Wesolowsky GO (2002) The Weber problem. In: Drezner Z, Hamacher HW (eds) Facility location: applications and theory. Springer, Berlin, pp 1–36CrossRef Drezner Z, Klamroth K, Schöbel A, Wesolowsky GO (2002) The Weber problem. In: Drezner Z, Hamacher HW (eds) Facility location: applications and theory. Springer, Berlin, pp 1–36CrossRef
Zurück zum Zitat Francis RL, McGinnis LF Jr, White JA (1992) Facility layout and location: an analytical approach, 2nd edn. Prentice Hall, Englewood Cliffs Francis RL, McGinnis LF Jr, White JA (1992) Facility layout and location: an analytical approach, 2nd edn. Prentice Hall, Englewood Cliffs
Zurück zum Zitat Hansen P, Mladenović N, Taillard É (1998) Heuristic solution of the multisource Weber problem as a \(p\)-median problem. Oper Res Lett 22:55–62CrossRef Hansen P, Mladenović N, Taillard É (1998) Heuristic solution of the multisource Weber problem as a \(p\)-median problem. Oper Res Lett 22:55–62CrossRef
Zurück zum Zitat Katz IN (1969) On the convergence of a numerical scheme for solving some locational equilibrium problems. SIAM J Appl Math 17:1224–1231CrossRef Katz IN (1969) On the convergence of a numerical scheme for solving some locational equilibrium problems. SIAM J Appl Math 17:1224–1231CrossRef
Zurück zum Zitat Katz IN (1974) Local convergence in Fermat’s problem. Math Program 6:89–104CrossRef Katz IN (1974) Local convergence in Fermat’s problem. Math Program 6:89–104CrossRef
Zurück zum Zitat Krarup J, Vajda S (1997) On Torricelli’s geometrical solution to a problem of Fermat. IMA J Manag Math 8:215–224 Krarup J, Vajda S (1997) On Torricelli’s geometrical solution to a problem of Fermat. IMA J Manag Math 8:215–224
Zurück zum Zitat Kuenne RE, Soland RM (1972) Exact and approximate solutions to the multisource Weber problem. Math Program 3:193–209CrossRef Kuenne RE, Soland RM (1972) Exact and approximate solutions to the multisource Weber problem. Math Program 3:193–209CrossRef
Zurück zum Zitat Kuhn HW (1967) On a pair of dual nonlinear programs. In: Abadie J (ed) Nonlinear programming. North-Holland, Amsterdam, pp 38–45 Kuhn HW (1967) On a pair of dual nonlinear programs. In: Abadie J (ed) Nonlinear programming. North-Holland, Amsterdam, pp 38–45
Zurück zum Zitat Love RF, Morris JG, Wesolowsky GO (1988) Facilities location: models and methods. North Holland, New York Love RF, Morris JG, Wesolowsky GO (1988) Facilities location: models and methods. North Holland, New York
Zurück zum Zitat Ostresh LM Jr (1978) On the convergence of a class of iterative methods for solving the Weber location problem. Oper Res 26:597–609CrossRef Ostresh LM Jr (1978) On the convergence of a class of iterative methods for solving the Weber location problem. Oper Res 26:597–609CrossRef
Zurück zum Zitat Vardi Y, Zhang C-H (2001) A modified Weiszfeld algorithm for the Fermat–Weber location problem. Math Program 90:559–566CrossRef Vardi Y, Zhang C-H (2001) A modified Weiszfeld algorithm for the Fermat–Weber location problem. Math Program 90:559–566CrossRef
Zurück zum Zitat Weber A (1909) Über den Standort der Industrien, 1. Teil: Reine Theorie des Standortes. English Translation: on the Location of Industries. University of Chicago Press, Chicago, IL. Translation published in 1929 Weber A (1909) Über den Standort der Industrien, 1. Teil: Reine Theorie des Standortes. English Translation: on the Location of Industries. University of Chicago Press, Chicago, IL. Translation published in 1929
Zurück zum Zitat Weiszfeld E (1937) Sur le point pour lequel la somme des distances de n points donnés est minimum. Tohoku Math J First Ser 43:355–386 Weiszfeld E (1937) Sur le point pour lequel la somme des distances de n points donnés est minimum. Tohoku Math J First Ser 43:355–386
Zurück zum Zitat Weiszfeld E, Plastria F (2009) On the point for which the sum of the distances to n given points is minimum. Ann Oper Res 167:7–41 (English Translation of Weiszfeld (1937))CrossRef Weiszfeld E, Plastria F (2009) On the point for which the sum of the distances to n given points is minimum. Ann Oper Res 167:7–41 (English Translation of Weiszfeld (1937))CrossRef
Zurück zum Zitat Wesolowsky GO (1993) The Weber problem: history and perspectives. Locat Sci 1:5–23 Wesolowsky GO (1993) The Weber problem: history and perspectives. Locat Sci 1:5–23
Metadaten
Titel
An improved algorithm for solving the Weber location problem
verfasst von
Zvi Drezner
Publikationsdatum
20.05.2024
Verlag
Springer Berlin Heidelberg
Erschienen in
4OR
Print ISSN: 1619-4500
Elektronische ISSN: 1614-2411
DOI
https://doi.org/10.1007/s10288-024-00565-9

    Marktübersichten

    Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen.