Top

4OR

20-05-2024 | Research Paper

An improved algorithm for solving the Weber location problem

Author: Zvi Drezner

Published in: 4OR

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

search-config

AI-assisted search

Off

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.

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

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, 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, 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, Drezner Z, Mladenović N, Salhi S (2014) A new local search for continuous location problems. Eur J Oper Res 232:256–265CrossRef

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

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

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

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

Drezner Z (1992) A note on the Weber location problem. Ann Oper Res 40:153–161CrossRef

Drezner Z (1996) A note on accelerating the Weiszfeld procedure. Locat Sci 3:275–279CrossRef

Drezner Z (2015) The fortified Weiszfeld algorithm for solving the Weber problem. IMA J Manag Math 26:1–9

Drezner Z, Simchi-Levi D (1992) Asymptotic behavior of the Weber location problem on the plane. Ann Oper Res 40:163–172CrossRef

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

Francis RL, McGinnis LF Jr, White JA (1992) Facility layout and location: an analytical approach, 2nd edn. Prentice Hall, Englewood Cliffs

Hansen P, Mladenović N, Taillard É (1998) Heuristic solution of the multisource Weber problem as a \(p\)-median problem. Oper Res Lett 22:55–62CrossRef

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 (1974) Local convergence in Fermat’s problem. Math Program 6:89–104CrossRef

Krarup J, Vajda S (1997) On Torricelli’s geometrical solution to a problem of Fermat. IMA J Manag Math 8:215–224

Kuenne RE, Soland RM (1972) Exact and approximate solutions to the multisource Weber problem. Math Program 3:193–209CrossRef

Kuhn HW (1967) On a pair of dual nonlinear programs. In: Abadie J (ed) Nonlinear programming. North-Holland, Amsterdam, pp 38–45

Love RF, Morris JG, Wesolowsky GO (1988) Facilities location: models and methods. North Holland, New York

Ostresh LM Jr (1978) On the convergence of a class of iterative methods for solving the Weber location problem. Oper Res 26:597–609CrossRef

Vardi Y, Zhang C-H (2001) A modified Weiszfeld algorithm for the Fermat–Weber location problem. Math Program 90:559–566CrossRef

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

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, 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

Wesolowsky GO (1993) The Weber problem: history and perspectives. Locat Sci 1:5–23

Title: An improved algorithm for solving the Weber location problem
Author: Zvi Drezner
Publication date: 20-05-2024
Publisher: Springer Berlin Heidelberg
Published in: 4OR
Print ISSN: 1619-4500
Electronic ISSN: 1614-2411
DOI: https://doi.org/10.1007/s10288-024-00565-9