×

A variational inequality approach for constrained multifacility Weber problem under gauge. (English) Zbl 1412.90079

Summary: The classical multifacility Weber problem (MFWP) is one of the most important models in facility location. This paper considers more general and practical case of MFWP called constrained multifacility Weber problem (CMFWP), in which the gauge is used to measure distances and locational constraints are imposed to facilities. In particular, we develop a variational inequality approach for solving it. The CMFWP is reformulated into a linear variational inequality, whose special structures lead to new projection-type methods. Global convergence of the projection-type methods is proved under mild assumptions. Some preliminary numerical results are reported which verify the effectiveness of proposed methods.

MSC:

90B85 Continuous location
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. S. Burachik; A. N. Iusem, A generalized proximal point algorithm for the variational inequality problem in a Hilbert space, SIAM J. Optim., 8, 197-216 (1998) · Zbl 0911.90273 · doi:10.1137/S1052623495286302
[2] E. Carrizosa; E. Conde; M. Munõz; J. Puerto, Simpson points in planar problems with locational constraints -the polyhedral gauge case, Math. Oper. Res., 22, 297-300 (1997) · Zbl 0883.90076 · doi:10.1287/moor.22.2.291
[3] M. Cera; J. A. Mesa; F. A. Ortega; F. Plastria, Locating a central hunter on the plane, J. Optim. Theory Appl., 136, 155-166 (2008) · Zbl 1146.90462 · doi:10.1007/s10957-007-9293-y
[4] F. Daneshzand; R. Shoeleh, Multifacility location problem, in Facility Location: Concepts, Models, Algorithms and Case Studies, R.Z. Farahani and M. Hekmatfar (eds.), Springer, Berlin, 69-92 (2009)
[5] Z. Drezner, Facility Location: A Survey of Applications and Methods, Springer, New York, 1995.
[6] Z. Drezner and H. W. Hamacher, Facility Location: Applications and Theory, Springer-Verlag, Berlin, 2002. · Zbl 0988.00044
[7] R. Durier, On Pareto optima, the Fermat-Weber problem and polyhedral gauges, Math. Program., 47, 65-79 (1990) · Zbl 0706.90066 · doi:10.1007/BF01580853
[8] B. C. Eaves, On the basic theorem of complememtarity, Math. Program., 1, 68-75 (1971) · Zbl 0227.90044 · doi:10.1007/BF01584073
[9] J. W. Eyster; J. A. White; W. W. Wierwille, On solving multifacility location problems using a hyperboloid approximation procedure, AIIE Trans., 5, 275-280 (1973) · doi:10.1080/05695557308974912
[10] F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003. · Zbl 1062.90001
[11] M. C. Ferris; C. Kanzow, Engineering and economic applications of complementarity problems, SIAM Review, 39, 669-713 (1997) · Zbl 0891.90158 · doi:10.1137/S0036144595285963
[12] B. S. He, A new method for a class of linear variational inequalities, Math. Program., 66, 137-144 (1994) · Zbl 0813.49009 · doi:10.1007/BF01581141
[13] B. S. He, A modified projection and contraction method for a class of linear complementarity problems, J. Comput. Math., 14, 54-63 (1996) · Zbl 0854.65047
[14] B. S. He; X. M. Yuan; W. X. Zhang, A customized proximal point algorithm for convex minimization with linear constraints, Comput. Optim. Appl., 56, 559-572 (2013) · Zbl 1287.90048 · doi:10.1007/s10589-013-9564-5
[15] I. N. Katz; S. R. Vogl, A Weiszfeld algorithm for the solution of an asymmetric extension of the generalized Fermat location problem, Comput. Math. Appl., 59, 399-410 (2010) · Zbl 1189.90086 · doi:10.1016/j.camwa.2009.07.007
[16] R. F. Love; J. G. Morris, Mathematical models of road travel distances, Manag. Sci., 25, 130-139 (1979) · Zbl 0419.90053 · doi:10.1287/mnsc.25.2.130
[17] R. F. Love; J. G. Morris, On estimating road distances by mathematical functions, Euro. J. Oper. Res., 36, 251-253 (1988) · doi:10.1016/0377-2217(88)90431-6
[18] R. F. Love, J. G. Morris and G. O. Wesolowsky, Facilities Location: Models and Methods, North-Holland, Amsterdam, 1988. · Zbl 0685.90036
[19] B. Martinet, Regularision d’inéquations variationnelles par approximations successive, Revue Francaise d’Automatique et Informatique Recherche Opérationnelle, 4, 154-158 (1970) · Zbl 0215.21103
[20] W. Miehle, Link length minimization in networks, Oper. Res., 6, 232-243 (1958) · Zbl 1414.90068 · doi:10.1287/opre.6.2.232
[21] H. Minkowski, Theorie der konvexen Körper, Gesammelte Abhandlungen, Teubner, Berlin, 1911.
[22] S. Nickel, Restricted center problems under polyhedral gauges, Euro. J. Oper. Res., 104, 343-357 (1998) · Zbl 0955.90071 · doi:10.1016/S0377-2217(97)00189-6
[23] L. M. Ostresh, The multifacility location problem: Applications and descent theorems, J. Regional Sci., 17, 409-419 (1977) · doi:10.1111/j.1467-9787.1977.tb00511.x
[24] F. Plastria, Asymmetric distances, semidirected networks and majority in Fermat-Weber problems, Ann. Oper. Res., 167, 121-155 (2009) · Zbl 1163.90038 · doi:10.1007/s10479-008-0351-0
[25] F. Plastria, The Weiszfeld algorithm: proof, amendments, and extensions, in Foundations of Location Analysis, H.A. Eiselt and V. Marianov (eds.), Springer, US, 155, 357-389 (2011) · Zbl 1387.90115 · doi:10.1007/978-1-4419-7572-0_16
[26] J. B. Rosen; G. L. Xue, On the convergence of Miehle’s algorithm for the Euclidean multifacility location problem, Oper. Res., 40, 188-191 (1992) · Zbl 0749.90046 · doi:10.1287/opre.40.1.188
[27] J. B. Rosen; G. L. Xue, On the convergence of a hyperboloid approximation procedure for the perturbed Euclidean multifacility location problem, Oper. Res., 41, 1164-1171 (1993) · Zbl 0802.90067 · doi:10.1287/opre.41.6.1164
[28] M. V. Solodov; P. Tseng, Modified projection-type methods for monotone variational inequalities, SIAM J. Control Optim., 34, 1814-1830 (1996) · Zbl 0866.49018 · doi:10.1137/S0363012994268655
[29] H. Uzawa, Iterative methods for concave programming, in Studies in Linear and Nonlinear Programming, K.J. Arrow, L. Hurwicz and H. Uzawa (eds.), Stanford University Press, Stanford, 154-165 (1958) · Zbl 0091.16002
[30] J. E. Ward; R. E. Wendell, A new norm for measuring distance which yields linear location problems, Oper. Res., 28, 836-844 (1980) · Zbl 0443.90029
[31] J. E. Ward; R. E. Wendell, Using block norms for location modelling, Oper. Res., 33, 1074-1090 (1985) · Zbl 0582.90026 · doi:10.1287/opre.33.5.1074
[32] E. Weiszfeld, Sur le point pour lequel la somme des distances de n points donnés est minimum, Tohoku Math. J., 43, 355-386 (1937) · Zbl 0017.18007
[33] C. Witzgall, Optimal location of a central facility, mathematical models and concepts, Report 8388, National Bureau of Standards, Washington DC, US, 1964.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.