\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

A variational inequality approach for constrained multifacility Weber problem under gauge

  • * Corresponding author: Su Zhang

    * Corresponding author: Su Zhang 
The first author is supported by National Natural Science Foundation of China No. 11571169, the Qing Lan Project and the Fundamental Research Funds for the Central Universities No. NQ2016002. The third author is supported by National Natural Science Foundation of China No. 11401322.
Abstract Full Text(HTML) Figure(0) / Table(4) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 90B85; Secondary: 90C33.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  MA, GMA, Algorithm 1 and Algorithm 2 for MFWP

    Problem MA GMA Algorithm 1 Algorithm 2
    E1 CPU 0.0003 0.0004 0.0147 0.0143
    Iter. 2 9 152.44 157.52
    Obj. 182.23 182.43 181.42 181.42
    E2 CPU 0.0109 0.0006 0.0149 0.0144
    Iter. 206 5 158.58 159.96
    Obj. 182.19 182.68 181.42 181.42
    E1' CPU / / 0.0145 0.0138
    Iter. / / 154.32 156.04
    Obj. / / 181.42 181.42
    E2' CPU / / 0.0147 0.0141
    Iter. / / 158.84 161.82
    Obj. / / 181.42 181.42
    E3 CPU 0.1949 0.0050 0.0206 0.0207
    Iter. 3733.40 85.86 195.76 197.14
    Obj. 63737.39 65188.08 63515.97 63515.97
     | Show Table
    DownLoad: CSV

    Table 2.  HAP, GHAP, SHAP, SGHAP, Algorithm 1 and Algorithm 2 for MFWP

    m HAP GHAP SHAP SGHAP Algo. 1 Algo. 2
    ε=50 ε=5 ε=0.5 ε=0.05 ε=50 s=5 ε=0.5 ε=0.05
    2 CPU 0.21 0.44 1.08 2.75 0.15 0.27 0.60 1.53 0.87 0.80 1.38 1.32
    Iter. 48.52 101.78 247.60 630.34 33.88 61.28 138.00 348.72 262.84 243.48 272.78 272.84
    Dobj. 82.2151 28.6441 9.0927 2.6080 82.2156 28.6446 9.0932 2.6083 2.6082 2.6052 0.0000 0.0002
    4 CPU 0.98 2.48 6.60 17.89 0.58 1.33 3.45 9.26 2.61 2.33 2.15 2.08
    Iter. 107.70 270.20 720.00 1936.20 63.50 145.90 376.10 1003.40 378.30 337.80 168.90 168.90
    Dobj. 283.4897 94.6138 30.0266 9.0773 283.4903 94.6144 30.0271 9.0767 9.0713 9.0701 0.0000 0.0005
    6 CPU 2.26 5.95 16.08 43.94 1.28 3.17 8.52 23.22 5.71 4.00 2.82 2.73
    Iter. 164.36 431.30 1167.66 3145.08 92.64 230.90 616.96 1664.60 541.94 382.48 126.82 126.84
    Dobj. 475.4137 155.9050 49.3255 15.0577 475.4124 155.9035 49.3238 15.0528 15.0468 15.0480 0.0000 -0.0003
    8 CPU 3.80 10.14 27.60 74.81 2.11 5.44 14.72 39.90 8.44 5.98 3.20 3.12
    Iter. 216.50 578.56 1573.84 4245.06 119.98 309.62 836.70 2262.78 638.06 453.98 101.70 101.74
    Dobj. 698.8811 227.5549 72.0128 22.1839 698.8829 227.5570 72.0143 22.1790 22.1858 22.1714 0.0000 0.0021
    10 CPU 6.08 16.40 44.55 120.77 3.34 8.77 23.73 64.28 14.02 9.34 4.27 4.14
    Iter. 274.60 740.54 2012.20 5414.64 150.90 396.42 1072.20 2899.56 840.34 563.34 97.68 97.80
    Dobj. 925.6176 299.2628 94.3543 28.8958 925.6183 299.2637 94.3537 28.8839 28.8930 28.8793 0.0000 -0.0123
     | Show Table
    DownLoad: CSV

    Table 3.  Numerical results for CMFWP under Euclidean distances

    n m PC method PPA1 PPA2 Algorithm 1 Algorithm 2
    CPU Iter. CPU Iter. CPU Iter. CPU Iter. CPU Iter.
    50 2 0.034 34.45 0.018 31.32 0.018 32.93 0.018 29.84 0.015 30.34
    4 0.093 40.32 0.044 36.60 0.046 37.78 0.044 36.39 0.043 37.11
    6 0.197 45.92 0.071 39.23 0.072 40.92 0.068 37.82 0.063 38.08
    8 0.314 49.93 0.096 41.63 0.100 43.87 0.093 41.91 0.090 41.76
    10 0.499 53.08 0.141 47.04 0.151 49.52 0.141 45.92 0.137 45.72
    100 2 0.036 17.27 0.027 25.87 0.028 27.21 0.024 22.44 0.022 22.65
    4 0.135 24.74 0.063 31.24 0.065 32.14 0.057 27.51 0.054 28.48
    6 0.277 26.42 0.099 33.51 0.113 35.02 0.097 31.42 0.098 31.99
    8 0.570 29.63 0.154 35.44 0.169 38.68 0.147 34.51 0.147 34.82
    10 0.830 30.46 0.221 38.73 0.238 40.56 0.221 37.22 0.219 37.81
    200 2 0.098 19.98 0.054 26.81 0.059 29.40 0.051 26.68 0.052 27.49
    4 0.370 22.05 0.121 28.88 0.126 30.43 0.116 28.23 0.111 28.13
    6 0.825 23.80 0.216 33.26 0.243 37.04 0.208 31.44 0.202 31.59
    8 1.574 24.02 0.333 35.37 0.344 36.59 0.299 31.36 0.293 32.24
    10 2.391 25.59 0.523 40.48 0.557 42.38 0.500 37.77 0.489 38.27
    500 2 0.241 9.62 0.150 25.82 0.156 27.45 0.121 21.26 0.118 21.82
    4 1.131 11.73 0.490 37.29 0.505 38.14 0.388 29.03 0.371 28.75
    6 3.335 16.14 0.884 38.74 0.993 42.53 0.770 32.16 0.727 32.02
    8 6.072 17.01 1.281 39.89 1.358 41.56 1.057 33.45 1.006 33.16
    10 9.968 18.62 2.138 48.18 2.266 50.49 1.653 36.62 1.646 37.34
    1000 2 0.716 7.78 0.386 28.34 0.414 29.86 0.321 22.47 0.320 23.51
    4 3.306 9.75 1.443 45.45 1.484 45.77 1.214 37.59 1.231 38.65
    6 8.109 10.88 2.879 49.66 3.036 51.44 2.108 35.86 2.132 36.42
    8 20.743 13.95 4.956 55.43 5.132 56.06 3.942 42.44 3.642 40.38
    10 37.590 17.52 7.712 59.15 7.941 59.95 5.819 43.43 5.893 45.85
     | Show Table
    DownLoad: CSV

    Table 4.  Numerical results for CMFWP under gauge

    n m PC method PPA1 PPA2 Algorithm 1 Algorithm 2
    CPU Iter. CPU Iter. CPU Iter. CPU Iter. CPU Iter.
    50 2 0.077 58.93 0.038 52.66 0.037 53.87 0.028 39.33 0.028 40.22
    4 0.219 77.85 0.084 60.53 0.086 61.71 0.066 49.14 0.063 46.94
    6 0.471 86.40 0.141 65.16 0.145 68.42 0.116 54.87 0.111 54.47
    8 0.859 101.61 0.231 76.47 0.222 76.93 0.183 62.82 0.183 64.13
    10 1.238 103.24 0.300 77.12 0.306 78.26 0.264 65.93 0.254 65.08
    100 2 0.130 47.82 0.053 38.50 0.055 39.37 0.038 28.84 0.039 29.39
    4 0.416 56.39 0.133 48.53 0.131 48.98 0.101 37.98 0.101 39.32
    6 0.778 58.80 0.239 57.14 0.235 57.93 0.175 43.07 0.174 44.15
    8 1.922 86.76 0.351 62.63 0.369 66.90 0.294 52.46 0.279 51.38
    10 2.986 90.21 0.507 67.44 0.514 67.12 0.436 56.77 0.426 56.10
    200 2 0.146 21.38 0.077 29.11 0.081 30.09 0.056 21.32 0.058 23.21
    4 0.634 31.07 0.201 37.14 0.204 37.92 0.148 27.76 0.156 30.00
    6 1.363 33.58 0.384 45.09 0.390 45.95 0.297 34.45 0.293 35.05
    8 2.796 37.18 0.622 50.46 0.651 53.04 0.473 38.48 0.510 42.54
    10 8.218 79.37 1.112 69.73 1.128 69.27 0.941 57.59 0.934 58.11
    500 2 0.280 9.53 0.166 23.66 0.198 29.26 0.139 20.84 0.153 23.46
    4 1.686 16.28 0.579 37.75 0.624 40.80 0.420 27.21 0.470 31.33
    6 5.626 22.22 1.072 41.50 1.048 40.41 0.815 31.00 0.854 33.42
    8 9.956 27.75 1.826 43.97 2.061 48.70 1.529 35.96 1.601 38.73
    10 23.448 43.14 2.762 53.52 2.831 53.89 2.067 39.27 2.228 43.10
    1000 2 0.700 7.49 0.379 23.81 0.391 24.30 0.314 19.23 0.266 16.97
    4 3.450 8.06 1.385 32.74 1.451 33.15 0.982 22.62 1.060 24.86
    6 7.448 9.23 2.457 37.53 2.721 40.88 1.880 28.29 2.050 31.22
    8 14.150 10.25 4.177 41.70 4.380 42.95 2.981 29.10 3.212 32.05
    10 39.917 13.78 8.838 51.66 9.151 51.74 6.629 38.16 6.997 41.41
     | Show Table
    DownLoad: CSV
  • [1] R. S. Burachik and A. N. Iusem, A generalized proximal point algorithm for the variational inequality problem in a Hilbert space, SIAM J. Optim., 8 (1998), 197-216.  doi: 10.1137/S1052623495286302.
    [2] E. CarrizosaE. CondeM. Munõz and J. Puerto, Simpson points in planar problems with locational constraints -the polyhedral gauge case, Math. Oper. Res., 22 (1997), 297-300.  doi: 10.1287/moor.22.2.291.
    [3] M. CeraJ. A. MesaF. A. Ortega and F. Plastria, Locating a central hunter on the plane, J. Optim. Theory Appl., 136 (2008), 155-166.  doi: 10.1007/s10957-007-9293-y.
    [4] F. Daneshzand and R. Shoeleh, Multifacility location problem, in Facility Location: Concepts, Models, Algorithms and Case Studies, R.Z. Farahani and M. Hekmatfar (eds.), Springer, Berlin, (2009), 69-92. 
    [5] Z. Drezner, Facility Location: A Survey of Applications and Methods, Springer, New York, 1995. doi: 10.1007/978-1-4612-5355-6.
    [6] Z. Drezner and H. W. Hamacher, Facility Location: Applications and Theory, Springer-Verlag, Berlin, 2002. doi: 10.1007/978-3-642-56082-8.
    [7] R. Durier, On Pareto optima, the Fermat-Weber problem and polyhedral gauges, Math. Program., 47 (1990), 65-79.  doi: 10.1007/BF01580853.
    [8] B. C. Eaves, On the basic theorem of complememtarity, Math. Program., 1 (1971), 68-75.  doi: 10.1007/BF01584073.
    [9] J. W. EysterJ. A. White and W. W. Wierwille, On solving multifacility location problems using a hyperboloid approximation procedure, AIIE Trans., 5 (1973), 275-280.  doi: 10.1080/05695557308974912.
    [10] F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2003.
    [11] M. C. Ferris and C. Kanzow, Engineering and economic applications of complementarity problems, SIAM Review, 39 (1997), 669-713.  doi: 10.1137/S0036144595285963.
    [12] B. S. He, A new method for a class of linear variational inequalities, Math. Program., 66 (1994), 137-144.  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 (1996), 54-63. 
    [14] B. S. HeX. M. Yuan and W. X. Zhang, A customized proximal point algorithm for convex minimization with linear constraints, Comput. Optim. Appl., 56 (2013), 559-572.  doi: 10.1007/s10589-013-9564-5.
    [15] I. N. Katz and S. R. Vogl, A Weiszfeld algorithm for the solution of an asymmetric extension of the generalized Fermat location problem, Comput. Math. Appl., 59 (2010), 399-410.  doi: 10.1016/j.camwa.2009.07.007.
    [16] R. F. Love and J. G. Morris, Mathematical models of road travel distances, Manag. Sci., 25 (1979), 130-139.  doi: 10.1287/mnsc.25.2.130.
    [17] R. F. Love and J. G. Morris, On estimating road distances by mathematical functions, Euro. J. Oper. Res., 36 (1988), 251-253.  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.
    [19] B. Martinet, Regularision d'inéquations variationnelles par approximations successive, Revue Francaise d'Automatique et Informatique Recherche Opérationnelle, 4 (1970), 154-158. 
    [20] W. Miehle, Link length minimization in networks, Oper. Res., 6 (1958), 232-243.  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 (1998), 343-357.  doi: 10.1016/S0377-2217(97)00189-6.
    [23] L. M. Ostresh, The multifacility location problem: Applications and descent theorems, J. Regional Sci., 17 (1977), 409-419.  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 (2009), 121-155.  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 (2011), 357-389.  doi: 10.1007/978-1-4419-7572-0_16.
    [26] J. B. Rosen and G. L. Xue, On the convergence of Miehle's algorithm for the Euclidean multifacility location problem, Oper. Res., 40 (1992), 188-191.  doi: 10.1287/opre.40.1.188.
    [27] J. B. Rosen and G. L. Xue, On the convergence of a hyperboloid approximation procedure for the perturbed Euclidean multifacility location problem, Oper. Res., 41 (1993), 1164-1171.  doi: 10.1287/opre.41.6.1164.
    [28] M. V. Solodov and P. Tseng, Modified projection-type methods for monotone variational inequalities, SIAM J. Control Optim., 34 (1996), 1814-1830.  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, (1958), 154-165. 
    [30] J. E. Ward and R. E. Wendell, A new norm for measuring distance which yields linear location problems, Oper. Res., 28 (1980), 836-844. 
    [31] J. E. Ward and R. E. Wendell, Using block norms for location modelling, Oper. Res., 33 (1985), 1074-1090.  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 (1937), 355-386. 
    [33] C. Witzgall, Optimal location of a central facility, mathematical models and concepts, Report 8388, National Bureau of Standards, Washington DC, US, 1964.
  • 加载中

Tables(4)

SHARE

Article Metrics

HTML views(1486) PDF downloads(311) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return