Abstract
In this paper, we consider a multi-source Weber problem of m new facilities with respect to n demand regions in order to minimize the sum of the transportation costs between these facilities and the demand regions. We find a point on the border of each demand region from which the facilities serve the demand regions at these points. We present an algorithm including a location phase and an allocation phase in each iteration for solving this problem. An algorithm is also proposed for carrying out the location phase. Moreover, global convergence of the new algorithm is proved under mild assumptions, and some numerical results are presented.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Altinel IK, Durmaz E, Aras N, Özksack KC (2009) A location-allocation heuristic for the capacitated multi-facility Weber problem with probabilistic customer locations. Eur J Oper Res 198:790–799
Aryanezhad MB, Hemati M (2008) A new genetic algorithm for solving nonconvex nonlinear programming problems. Appl Math Comput 199:186–194
Bauschke HH, Borwein JM (1996) On projection algorithms for solving convex feasibility problems. SIAM Rev 38:367–426
Bauschke HH, Luke DR, Phan HM, Wang X (2013) Restricted normal cones and the method of alternating projections: theory. Set Valued Anal 21:431–473
Bazara MS, Sherali HD, Shetty CM (2006) Nonlinear programming: theory and algorithms. Wiley, New York
Bischoff M, Klamroth K (2007) An efficient solution method for Weber problems with barriers based on genetic algorithms. Eur J Oper Res 177:22–41
Borwein JM, Li G, Yao L (2014) Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets. SIAM J Optim 24(1):498–527
Brimberg J, Hansen P, Mladenovic N, Taillard ED (2000) Improvements and comparison of heuristics for solving the uncapacitated multi source Weber problem. Oper Res 48(3):444–460
Brimberg J, Wesolowsky GO (2000) Note: facility location with closest rectangular distances. Nav Res Logist 47:77–84
Brimberg J, Wesolowsky GO (2002a) Locating facilities by minimax relative to closest points of demand areas. Comput Oper Res 29(6):625–636
Brimberg J, Wesolowsky GO (2002b) Minisum location with closest Euclidean distances. Ann Oper Res 111:151–165
Buchanan DJ, Wesolowsky GO (1993) Locating a noxious facility with respect to several polygonal regions using asymmetric distances. IIE Trans 25(1):77–88
Canbolat MS, Wesolowsky GO (2012) On the use of the Varignon frame for single facility Weber problems in the presence of convex barriers. Eur J Oper Res 217:241–247
Carrizosa E, Muñoz-Márquez M, Puerto J (1998) The Weber problem with regional demand. Eur J Oper Res 104:358–365
Clarke FH, Ledyaev YS, Stern J, Subbotin AI (1998) Nonsmooth analysis and control theory. Springer, New York
Combettes PL, Trussell HJ (1990) Method of successive projections for finding a common point of sets in metric space. J Optim Theory Appl 67:487–507
Cooper L (1964) Heuristic methods for location-allocation problems. SIAM Rev 6:37–53
Ghosh A, Rushton G (1987) Spatial analysis and location-allocation models. Van Nostrand Reinhold, New York
Giaquinta M, Modica G (2011) Mathematical analysis: foundations and advanced techniques for functions of several variables. Birkhäuser, Boston
Gunawardana A, Byrne W (2005) Convergence theorems for generalized alternating minimization procedures. J Mach Learn Res 6:2049–2073
Hamacher HW, Nickel S (1995) Restricted planar location problems and applications. Nav Res Logist 42:967–992
Hausdorff F (1949) Grundzüge der Mengenlehre (1914), reprinted by the Chelsea Publishing Company, New York
Jiang JL, Yuan XM (2008) A heuristic algorithm for constrained multi-source Weber problem—the variational inequality approach. Eur J Oper Res 187:357–370
Kinderlehrer D, Stampacchia G (1980) An introduction to variational inequalities and their application. Academic Press, New York
Larson RC, Odoni AR (1981) Urban operations research. Prentice-Hall, Englewood Cliffs
Levin Y, Ben-Israel A (2004) A heuristic method for large-scale multi-facility location problems. Comput Oper Res 31:257–272
Love RF, Morris JG, Wesolowsky GO (1988) Facilities location: models and methods. North Holland, Amsterdam
Pilotta EA, Torres GA (2011) A projected Weiszfeld algorithm for the box-constrained Weber location problem. Appl Math Comput 218:2932–2943
Weiszfeld E (1937) Sur le point lequel la somme des distances de n points donnés est minimum. Tôhoku Math J 43:355–386
Wesolowsky GO, Love RF (1971) Location of facilities with rectangular distances among point and area destinations. Nav Res Logist Q 18:83–90
Acknowledgements
The first-named author was partially supported by a grant from IPM (No. 96900422).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Nobakhtian, S., Raeisi Dehkordi, A. An algorithm for generalized constrained multi-source Weber problem with demand substations. 4OR-Q J Oper Res 16, 343–377 (2018). https://doi.org/10.1007/s10288-017-0366-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10288-017-0366-y