zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Accelerating the convergence in the single-source and multi-source Weber problems. (English) Zbl 1241.90076
Summary: The modified Weiszfeld method [{\it Y. Vardi} and {\it C.H. Zhang}, Math. Program. 90, No. 3 (A), 90, 559--566 (2001; Zbl 0990.65064)] is perhaps the most widely-used algorithm for the single-source Weber problem (SWP). In this paper, in order to accelerate the efficiency for solving SWP, a new numerical method, called Weiszfeld-Newton method, is developed by combining the modified Weiszfeld method with the well-known Newton method. Global convergence of the new Weiszfeld-Newton method is proved under mild assumptions. For the multi-source Weber problem (MWP), a new location-allocation heuristic, Cooper-Weiszfeld-Newton method, is presented in the spirit of Cooper algorithm [{\it L. Cooper}, SIAM Rev. 6, 37--53 (1964; Zbl 0956.90014)], using the new Weiszfeld-Newton method in the location phase to locate facilities and adopting the nearest center reclassification algorithm (NCRA) in the allocation phase to allocate the customers. Preliminary numerical results are reported to verify the evident effectiveness of Weiszfeld-Newton method for SWP and Cooper-Weiszfeld-Newton method for MWP.
90B85Continuous location
90C25Convex programming
90C59Approximation methods and heuristics
65K05Mathematical programming (numerical methods)
Full Text: DOI
[1] Argyrosa, I. K.; Hilout, S.: Weak convergence conditions for inexact Newton-type methods, Applied mathematics and computation 218, No. 6, 2800-2809 (2011) · Zbl 1296.47065
[2] Bongartz, I.; Calamai, P. H.; Conn, A. R.: A projection method for lp norm location-allocation problems, Mathematical programming 66, 283-312 (1994) · Zbl 0829.90085 · doi:10.1007/BF01581151
[3] Brimberg, J.; Chen, R.; Chen, D.: Accelerating convergence in the Fermat -- Weber location problem, Operations research letters 22, 151-157 (1998) · Zbl 0911.90239 · doi:10.1016/S0167-6377(98)00016-9
[4] Brimberg, J.; Mladenovic, N.: Degeneracy in the multi-source Weber problem, Mathematical programming 85, 213-220 (1999) · Zbl 0956.90016 · doi:10.1007/s101070050054
[5] Chandrasekaran, R.; Tamir, A.: Open question concerning weiszfeld’s algorithm for the Fermat -- Weber location problem, Mathematical programming 44, 193-295 (1989) · Zbl 0683.90026 · doi:10.1007/BF01587094
[6] Cooper, L.: Heuristic methods for location-allocation problems, SIAM review 6, 37-53 (1964) · Zbl 0956.90014
[7] Cooper, L.: Solutions of generalized location equilibrium models, Journal of regional science 7, 1-18 (1967)
[8] Bertsekas, D. P.: Projection Newton methods for optimization problems with simple constraints, SIAM journal on control and optimization 20, 221-246 (1982) · Zbl 0507.49018 · doi:10.1137/0320018
[9] Drezner, Z.: A note on the Weber location problem, Annals of operations research 40, 153-161 (1992) · Zbl 0787.90042 · doi:10.1007/BF02060474
[10] Drezner, Z.: Facility location: A survey of applications and methods, (1995) · Zbl 0917.90224
[11] Drezner, Z.; Hamacher, H.: Facility location: applications and theory, (2002) · Zbl 0988.00044
[12] Fletcher, R.: Practical methods of optimization, (2000) · Zbl 0905.65002
[13] Fukunaga, K.: Introduction to statistical pattern recognition, (1990) · Zbl 0711.62052
[14] Gamal, M. D. H.; Salhi, S.: Constructive heuristics for the uncapacitated continuous location-allocation problem, Journal of the operational research society 52, 821-829 (2001) · Zbl 1131.90407 · doi:10.1057/palgrave.jors.2601176
[15] Grippo, L.; Lampariello, F.; Lucidi, S.: A truncated Newton method with nonmonotone line search for unconstrained optimization, Journal of optimization theory and applications 60, 401-419 (1989) · Zbl 0632.90059 · doi:10.1007/BF00940345
[16] Jiang, J. L.; Xu, Y.: Minimum location problem with farthest Euclidean distance, Mathematical methods of operations research 64, 285-308 (2006) · Zbl 1132.90344 · doi:10.1007/s00186-006-0084-2
[17] Jiang, J. L.; Yuan, X. M.: A heuristic algorithm for constrained multi-source Weber problem -- the variational inequality approach, European journal of operational research 187, 357-370 (2008) · Zbl 1149.90091 · doi:10.1016/j.ejor.2007.02.043
[18] Katz, I. N.: Local convergence in Fermat’s problem, Mathematical programming 6, 89-104 (1974) · Zbl 0291.90069 · doi:10.1007/BF01580224
[19] Kuhn, H. W.; Kuenne, R. E.: An efficient algorithm for the numerical solution of the generalized Weber problem in spatial economics, Journal of regional science 4, 21-33 (1962)
[20] Kuhn, H. W.: A note on Fermat’s problem, Mathematical programming 4, 98-107 (1973) · Zbl 0255.90063 · doi:10.1007/BF01584648
[21] Levin, Y.; Ben-Israel, A.: A heuristic method for large-scale multi-facility location problems, Computers & operations research 31, 257-272 (2004) · Zbl 1088.90036 · doi:10.1016/S0305-0548(02)00191-0
[22] Love, R. F.; Morris, J. G.; Wesolowsky, G. O.: Facilities location: models & methods, (1988) · Zbl 0685.90036
[23] Mladenovic, N.; Brimberg, J.; Hansen, P.; Moreno-Perez, J.: The p-median problem: A survey of metaheuristic approaches, European journal of operational research 179, 927-939 (2007) · Zbl 1163.90610 · doi:10.1016/j.ejor.2005.05.034
[24] Megiddo, N.; Supowit, K. J.: On the complexity of some common geometric location problems, SIAM journal on computing 13, 182-196 (1984) · Zbl 0534.68032 · doi:10.1137/0213014
[25] Michelot, C.; Lefebvre, O.: A primal-dual algorithm for the Fermat -- Weber problem involving mixed gauses, Mathematical programming 39, 319-335 (1987) · Zbl 0641.90034 · doi:10.1007/BF02592080
[26] Nocedal, J.; Wright, S.: Numerical optimization (Series: Springer series in operation research and financial engineering), (2006)
[27] Jr., L. M. Ostresh: An efficient algorithm for solving the two-center location-allocation problem, Journal of regional science 15, 209-216 (1975)
[28] Jr., L. M. Ostresh: On the convergence of a class of iterative methods for solving the Weber location problem, Operations research 26, 597-609 (1978) · Zbl 0396.90073 · doi:10.1287/opre.26.4.597
[29] Polyak, B. T.: Newtons method and its use in optimization, European journal of operational research 181, 1086-1096 (2007) · Zbl 1123.90070 · doi:10.1016/j.ejor.2005.06.076
[30] Qi, L. Q.; Sun, D. F.; Ulbrich, M.: Semismooth and smoothing Newton methods (Series: Springer series in operations research and financial engineering), (2011)
[31] Rado, F.: The Euclidean multifacility location problem, Operations research 36, 485-492 (1988) · Zbl 0651.90024 · doi:10.1287/opre.36.3.485
[32] Sun, W. Y.; Sampaio, R. J. B.; Yuan, J. Y.: Quasi-Newton trust region algorithm for non-smooth least squares problems, Applied mathematics and computation 105, 183-194 (1999) · Zbl 1026.90066 · doi:10.1016/S0096-3003(98)10103-0
[33] Salhi, S.; Gamal, M. D.: A GA-based heuristic for the multi-source Weber problem, Annals of operations research 123, 203-222 (2003) · Zbl 1053.90089
[34] Taji, K.; Fukushima, M.; Ibaraki, T.: A globally convergent Newton method for solving strongly monotone variational inequalities, Mathematical programming 58, 369-383 (1993) · Zbl 0792.49007 · doi:10.1007/BF01581276
[35] Vardi, Y.; Zhang, C. H.: A modified weiszfeld algorithm for the Fermat -- Weber location problem, Mathematical programming 90, 559-566 (2001) · Zbl 0990.65064 · doi:10.1007/s101070100222
[36] Weiszfeld, E.: Sur le point pour lequal la somme des distance de n points donnest minimum, Tohoku mathematical journal 43, 355-386 (1937) · Zbl 0017.18007 · doi:10.2748/tmj/1178227459
[37] Yao, Z. S.; Lee, L. H.; Jaruphongsa, W.; Tan, V.; Hui, C. F.: Multi-source facility location callocation and inventory problem, European journal of operational research 207, 750-762 (2010) · Zbl 1205.90178 · doi:10.1016/j.ejor.2010.06.006