×

On the global convergence of a generalized iterative procedure for the minisum location problem with \(\ell _{p }\) distances for \(p > 2\). (English) Zbl 1262.90080

The classical single facility location problem with \(\ell_p\) norm in dimension \(n\) is considered, for which no convergence results of the generalized Weiszfeld algorithm are known for \(p>2\). For such cases new stepsizes are developed for a hyperbolic \(\varepsilon\)-approximation of the problem guaranteeing convergence to the optimal solution. Using stepwise decreasing \(\varepsilon\) values and a diagonal argument a globally convergent algorithm is obtained for the original problem. Extensive numerical results show the effectiveness of the procedure.

MSC:

90B85 Continuous location
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Attouch H.: Variational Convergence for Functions and Operators. Pitman Advanced Publishing Program, Boston (1984) · Zbl 0561.49012
[2] Beckenbach E.F., Bellman R.: Inequalities. Second Revised Printing. Springer, Berlín (1965) · Zbl 0128.27401
[3] Brimberg J., Love R.F.: A new distance function for modeling travel distances in a transportation network. Transp. Sci. 26(2), 129–137 (1992) · Zbl 0766.90054 · doi:10.1287/trsc.26.2.129
[4] Brimberg J., Love R.F.: Local convergence in a generalized Fermat-Weber problem. Ann. Oper. Res. 40, 33–65 (1992) · Zbl 0787.90040 · doi:10.1007/BF02060469
[5] Brimberg J., Love R.F.: Global convergence of a generalized iterative procedure for the minisum location problem with l p distances. Oper. Res. 41(6), 1153–1163 (1993) · Zbl 0795.90037 · doi:10.1287/opre.41.6.1153
[6] Brimberg J.: The Fermat-Weber location problem revisited. Math. Program. 71, 71–76 (1995) · Zbl 0855.90075
[7] Brimberg J., Chen R., Chen D.: Accelerating convergence in the Fermat-Weber location problem. Oper. Res. Lett. 22, 151–157 (1998) · Zbl 0911.90239 · doi:10.1016/S0167-6377(98)00016-9
[8] Brimberg J., Chen R.: A note on convergence in the single facility minisum location problem. Comput. Math. Appl. 35(9), 25–31 (1998) · Zbl 0992.90043 · doi:10.1016/S0898-1221(98)00054-6
[9] Brimberg J., Wesolowsky G.O.: Minisum location with closest Euclidean distances. Ann. Oper. Res. 111, 151–165 (2002) · Zbl 1040.90020 · doi:10.1023/A:1020901719463
[10] Brimberg J.: Further notes on convergence of the Weiszfeld algorithm. Yugosl. J. Oper. Res. 13(2), 199–206 (2003) · Zbl 1274.90207 · doi:10.2298/YJOR0302199B
[11] Cánovas L., Cañavate R., Marín A.: On the convergence of the Weiszfeld algorithm. Math. Program. 93, 327–330 (2002) · Zbl 1065.90054 · doi:10.1007/s101070200297
[12] Chandrasekaran R., Tamir A.: Open questions concerning Weiszfeld’s algorithm for the Fermat-Weber location problem. Math. Program. 44, 293–295 (1989) · Zbl 0683.90026 · doi:10.1007/BF01587094
[13] Chen R.: Solution of location problems with radial cost functions. Comput. Math. Appl. 10, 87–94 (1984) · Zbl 0524.65046 · doi:10.1016/0898-1221(84)90089-0
[14] Chen R.: Location problems with costs being sums of powers of Euclidean distances. Comput. Oper. Res. 11, 285–294 (1984) · Zbl 0608.90018 · doi:10.1016/0305-0548(84)90017-0
[15] Chen R.: Optimal location of a single facility with circular demand areas. Comput. Math. Appl. 41, 1049–1061 (2001) · Zbl 0980.90047 · doi:10.1016/S0898-1221(00)00339-4
[16] Chong E.K.P., Zak S.H.: An Introduction to Optimization. Wiley, New York (1996) · Zbl 1266.90001
[17] Cooper L.: An extension of the generalized Weber problem. J. Reg. Sci. 8(2), 181–197 (1968) · doi:10.1111/j.1467-9787.1968.tb01323.x
[18] Drezner Z.: A note on the Weber location problem. Ann. Oper. Res. 40, 153–161 (1992) · Zbl 0787.90042 · doi:10.1007/BF02060474
[19] Drezner Z.: A note on accelerating the Weiszfeld procedure. Locat. Sci. 3(4), 275–279 (1995) · Zbl 0916.90178 · doi:10.1016/0966-8349(96)00004-6
[20] Eckhardt U.: Weber’s problem and Weiszfeld’s algorithm in general spaces. Math. Program. 18, 186–196 (1980) · Zbl 0433.65035 · doi:10.1007/BF01588313
[21] Espejo I., Rodríguez-Chía A.M., Valero C.: Convex ordered median problem with p -norms. Comput. Oper. Res. 36, 2250–2262 (2009) · Zbl 1158.90375 · doi:10.1016/j.cor.2008.08.019
[22] Frenk J.B.G., Melo M.T., Zhang S.: A Weiszfeld method for a generalized p distance minisum location model in continuous space. Locat. Sci. 2(2), 111–127 (1994) · Zbl 0926.90055
[23] Harris B.: Speeding up iterative algorithms–the generalized Weber problem. J. Reg. Sci. 16(3), 411–413 (1976) · doi:10.1111/j.1467-9787.1976.tb00985.x
[24] Katz I.N.: On the convergence of a numerical scheme for solving some locational equilibrium problems. SIAM J. Appl. Math. 17(6), 1224–1231 (1969) · Zbl 0187.18001 · doi:10.1137/0117113
[25] Katz I.N.: Local convergence in Fermat’s problem. Math. Program. 6, 89–104 (1974) · Zbl 0291.90069 · doi:10.1007/BF01580224
[26] Kuhn H.W.: A note on Fermat’s problem. Math. Program. 4, 98–107 (1973) · Zbl 0255.90063 · doi:10.1007/BF01584648
[27] Love R.F., Morris J.G.: Mathematical models of road travel distances. Manag. Sci. 25(2), 130–139 (1979) · Zbl 0419.90053 · doi:10.1287/mnsc.25.2.130
[28] Love R.F., Morris J.G., Wesolowsky G.O.: Facilities Location: Models and Methods. North-Holland, New York (1988) · Zbl 0685.90036
[29] Morris J.G., Verdini W.A.: Minisum l p distance location problems solved via a perturbed problem and Weiszfeld’s algorithm. Oper. Res. 27, 1180–1188 (1979) · Zbl 0442.90023 · doi:10.1287/opre.27.6.1180
[30] Morris J.G.: Convergence of the Weiszfeld algorithm for Weber problems using a generalized ”distance” function. Oper. Res. 29(1), 37–48 (1981) · Zbl 0452.90023 · doi:10.1287/opre.29.1.37
[31] Ostresh L.M.: On the convergence of a class of iterative methods for solving the Weber location problem. Oper. Res. 26(4), 597–609 (1978) · Zbl 0396.90073 · doi:10.1287/opre.26.4.597
[32] Puerto J., Rodríguez-Chía A.M.: Location of a moving service facility. Math. Methods Oper. Res. 49, 373–393 (1999) · Zbl 0941.90047 · doi:10.1007/s001860050055
[33] Puerto J., Rodríguez-Chía A.M.: New models for locating a moving service facility. Math. Methods Oper. Res. 63(1), 31–51 (2006) · Zbl 1103.90063 · doi:10.1007/s00186-005-0011-y
[34] Üster H., Love R.F.: The convergence of the Weiszfeld algorithm. Comput. Math. Appl. 40, 443–451 (2000) · Zbl 0978.90066 · doi:10.1016/S0898-1221(00)00172-3
[35] Valero Franco C., Rodríguez-Chía A.M., Espejo Miranda I.: The single facility location problem with average-distances. TOP 16(1), 164–194 (2008) · Zbl 1162.90500 · doi:10.1007/s11750-008-0040-9
[36] Vardi Y., Zhang C.-H.: A modified Weiszfeld algorithm for the Fermat-Weber location problem. Math. Program. 90, 559–566 (2001) · Zbl 0990.65064 · doi:10.1007/PL00011435
[37] Weiszfeld E.: Sur le point pour lequel la somme des distances de n points donnés est minimum. Tôhoku Math. J. 43, 355–386 (1937) · JFM 63.0583.01
[38] Zhang L.: On the convergence of a modified algorithm for the spherical facility location problem. Oper. Res. Lett. 31, 161–166 (2003) · Zbl 1041.90024 · doi:10.1016/S0167-6377(02)00190-6
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.