Abstract
A general family of single facility continuous location–allocation problems is introduced, which includes the decreasingly weighted ordered median problem, the single facility Weber problem with supply surplus, and Weber problems with alternative fast transportation network. We show in this paper that the extension of the well known Weiszfeld iterative decrease method for solving the corresponding location problems with fixed allocation yields an always convergent scheme for the location allocation problems. In a generic way, from each starting point, the limit point will be a locally minimal solution, whereas for each possible exceptional situation, a possible solution is indicated. Some computational results are presented, comparing this method with an alternating location–allocation approach.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Brimberg J (2003) Further notes on convergence of the Weiszfeld algorithm. Yugosl J Oper Res 13(2):199–206
Cánovas L, Cañavate R, Marín A (2002) On the convergence of the Weiszfeld algorithm. Math Program 93(2):327–330
Carrizosa E, Rodríguez-Chía AM (1997) Weber problems with alternative transportation systems. Eur J Oper Res 97:87–93
Chandrasekaran R, Tamir A (1989) Open questions concerning Weiszfeld’s algorithm for the Fermat–Weber location problem. Math Program 44(3):293–295
Cooper L (1963) Location–allocation problems. Oper Res 11:331–343
Cooper L (1964) Heuristic methods for location–allocation problems. SIAM Rev 6:37–52
Dantzig GB (1957) Discrete variable extremum problems. Oper Res 5:266–277
Drezner Z, Suzuki A (2004) The big triangle small triangle method for the solution of non-convex facility location problems. Oper Res 52(1):128–135
Drezner Z, Klamroth K, Schöbel A, Wesolowsky GO (2003) The Weber problem. In: Drezner Z, Hamacher H (eds) Facility location: applications and theory. Springer, Berlin, pp 1–36
Eilon S, Watson-Gandy CDT, Christofides N (1971) Distribution management. Hafner, New York
Francis RL, McGinnis LF, White JA (1992) Facility layout and location: an analytical approach, 2nd edn. Prentice Hall, Englewood Cliffs
Gugat M, Pfeiffer B (2007) Weber problems with mixed distances and regional demand. Math Methods Oper Res 66:419–449
Hansen P, Peeters D, Thisse J-F (1983) Public facility location models: a selective survey. In: Thisse J-F, Zoller HG (eds) Locational analysis of public facilities. North-Holland, Amsterdam, pp 223–262
Hansen P, Peeters D, Richard D, Thisse J-F (1985) The minisum and minimax location problems revisited. Oper Res 33:1251–1265
Kaufman L, Plastria F (1988) The Weber problem with supply surplus. Belgian J Oper Res Stat Comput Sci 28:15–31
Kuhn HW, Kuenne RE (1962) An efficient algorithm for the numerical solution of the generalized Weber problem in spatial economics. J Reg Sci 4:21–33
Kupitz YS, Martini H (1997) Geometric aspects of the generalized Fermat-Torricelli problem. In: Intuitive geometry, Bolyai society, Mathematical studies, vol 6, pp 55–127
Martello S, Toth P (1990) Knapsack problems—algorithms and computer implementations. Wiley, Chichester
Nickel S, Puerto J (2005) Location theory—a unified approach. Springer, Berlin
Okabe A, Boots B, Sugihara K (1992) Spatial tessellations. Concept and applications of Voronoi diagram. Wiley, Chichester
Pfeiffer B, Klamroth K (2008) A unified model for Weber problems with continuous and network distances. Comput Oper Res 35(2):312–326
Plastria F (1992) GBSSS: the generalized big square small square method for planar single facility location. Eur J Oper Res 62(2):163–174
Vardi Y, Zhang C-H (2001) A modified Weiszfeld algorithm for the Fermat–Weber location problem. Math Program 90:559–566
Weiszfeld E (2008) On the point for which the sum of the distances to n given points is minimum (translated and annotated by F. Plastria). Ann Oper Res. doi:10.1007/s10479-008-0352-z
Weiszfeld E (1936–1937) Sur le point pour lequel la somme des distances de n points donnés est minimum. Tohoku Math J 355–386
Wesolowsky G (1993) The Weber problem: History and perspective. Location Sci 1:5–23
Author information
Authors and Affiliations
Corresponding author
Additional information
The research of the second author was partially supported by the grant of the Algerian Ministry of High Education 001BIS/PNE/ENSEIGNANTS/BELGIQUE.
Rights and permissions
About this article
Cite this article
Plastria, F., Elosmani, M. On the convergence of the Weiszfeld algorithm for continuous single facility location–allocation problems. TOP 16, 388–406 (2008). https://doi.org/10.1007/s11750-008-0056-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-008-0056-1