×

Continuous location under the effect of ‘refraction’. (English) Zbl 1355.90038

Summary: In this paper we address the problem of locating a new facility on a \(d\)-dimensional space when the distance measure (\(\ell _p\)- or polyhedral-norms) is different at each one of the sides of a given hyperplane \(\mathcal {H}\). We relate this problem with the physical phenomenon of refraction, and extend it to any finite dimensional space and different distances at each one of the sides of any hyperplane. An application to this problem is the location of a facility within or outside an urban area where different distance measures must be used. We provide a new second order cone programming formulation, based on the \(\ell _p\)-norm representation given in [the first author et al., Comput. Optim. Appl. 58, No. 3, 563–595 (2014; Zbl 1297.90073)] that allows to solve the problem in any finite dimensional space with second order cone or semidefinite programming tools. We also extend the problem to the case where the hyperplane is considered as a rapid transit media (a different third norm is also considered over \(\mathcal {H}\)) that allows the demand to travel, whenever it is convenient, through \(\mathcal {H}\) to reach the new facility. Extensive computational experiments run in Gurobi are reported in order to show the effectiveness of the approach. Some extensions of these models are also presented.

MSC:

90B85 Continuous location
90C22 Semidefinite programming
90C30 Nonlinear programming
47A30 Norms (inequalities, more than one norm, etc.) of linear operators

Citations:

Zbl 1297.90073

Software:

Gurobi
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Albareda, M., Fernández, E., Hinojosa, Y., Puerto, J.: The multi-period incremental service facility location problem. Comput. Oper. Res. 36, 1356-1375 (2009) · Zbl 1177.90242 · doi:10.1016/j.cor.2008.02.010
[2] Alizadeh, F., Goldfarb, D.: Second order cone programming. Math. Program. 95, 3-51 (2003) · Zbl 1153.90522 · doi:10.1007/s10107-002-0339-5
[3] Aybat, N.S., Iyengar, G.: A unified approach for minimizing composite norms. Math. Program. A 144, 181-226 (2014) · Zbl 1327.90190 · doi:10.1007/s10107-012-0622-z
[4] Blanco, V., Puerto, J.: El-Haj Ben-Ali, S.: Revisiting several problems and algorithms in continuous location with \[l_\tau\] lτ norms. Comput. Optim. Appl. 58(3), 563-595 (2014) · Zbl 1297.90073 · doi:10.1007/s10589-014-9638-z
[5] Brimberg, J.: The Fermat-Weber location problem revisited. Math. Program. 71(1), 71-76 (1995) · Zbl 0855.90075 · doi:10.1007/BF01592245
[6] Brimberg, J., Kakhki, H.T., Wesolowsky, G.O.: Location among regions with varying norms. Ann. Oper. Res. 122(1-4), 87-102 (2003) · Zbl 1038.90048 · doi:10.1023/A:1026190322164
[7] Brimberg, J., Kakhki, H.T., Wesolowsky, G.O.: Locating a single facility in the plane in the presence of a bounded region and different norms. J. Oper. Res.Soc. Jpn. 48(2), 135-147 (2005) · Zbl 1274.90192
[8] Cánovas, L., Marín, A., Cañavate, R.: On the convergence of the Weiszfeld algorithm. Math. Program. 93, 327-330 (2002) · Zbl 1065.90054 · doi:10.1007/s101070200297
[9] Carrizosa, E., Rodríguez-Chía, A.: Weber problems with alternative transportation systems. Eur. J. Oper. Res. 97(1), 87-93 (1997) · Zbl 0923.90111 · doi:10.1016/S0377-2217(96)00066-5
[10] Drezner, Z., Hamacher, H.W. (eds.): Facility Location: Applications and Theory. Springer, New York (2002) · Zbl 0988.00044
[11] Edlesbrunner, H.: Algorithms in Combinatorial Geometry. Springer, Berlin (1987) · doi:10.1007/978-3-642-61568-9
[12] Eilon, S., Watson-Gandy, C., Christofides, N.: Distribution management: mathematical modeling and practical analysis. Oper. Res. Q. 20, 309 (1971)
[13] 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
[14] Fathali, J., Zaferanieh, M.: Location problems in regions with \[\ell_p\] ℓp and block norms. Iran. J. Oper. Res. 2(2), 72-87 (2011)
[15] Franco, L., Velasco, F., Gonzalez-Abril, L.: Gate points in continuous location between regions with different \[\ell_p\] ℓp norms. Eur. J. Oper. Res. 218(3), 648-655 (2012) · Zbl 1244.90132 · doi:10.1016/j.ejor.2011.11.047
[16] Lasserre, J.B.: Moments, Positive Polynomials and Their Applications. Imperial College Press, London (2009) · doi:10.1142/p665
[17] Mangasarian, O.L.: Arbitrary-norm separating plane. Oper. Res. Lett. 24(1-2), 15-23 (1999) · Zbl 1028.90037 · doi:10.1016/S0167-6377(98)00049-2
[18] Parlar, M.: Single facility location problem with region-dependent distance metrics. Int. J. Syst. Sci. 25(3), 513-525 (1994) · Zbl 0801.90071 · doi:10.1080/00207729408928976
[19] Marín, A., Nickel, S., Puerto, J., Velten, S.: A flexible model and efficient solution strategies for discrete location problems. Discrete Appl. Math. 157, 1128-1145 (2009) · Zbl 1163.90609 · doi:10.1016/j.dam.2008.03.013
[20] Mesa, J.A., Puerto, J., Tamir, A.: Improved algorithms for several network location problems with equality measures. Discrete Appl. Math. 130, 437-448 (2003) · Zbl 1033.90011 · doi:10.1016/S0166-218X(02)00599-1
[21] Nickel, S., Puerto, J.: Facility Location—A Unified Approach. Springer, Berlin (2005) · Zbl 1229.90001
[22] Nickel, S., Puerto, J., Rodrguez-Cha, A.M.: An approach to location models involving sets as existing facilities. Math. Oper. Res. 28(4), 693-715 (2003) · Zbl 1082.90059 · doi:10.1287/moor.28.4.693.20521
[23] Puerto, J., Rodríguez-Chía, A.M.: On the structure of the solution set for the single facility location problem with average distances. Math. Program. 128, 373-401 (2011) · Zbl 1279.90106 · doi:10.1007/s10107-009-0308-3
[24] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401 · doi:10.1515/9781400873173
[25] Rodríguez-Chía, A., Valero-Franco, C.: On the global convergence of a generalized iterative procedure for the minisum location problem with \[\ell_p\] ℓp distances for \[p > 2\] p>2. Math. Program. 137, 477-502 (2013) · Zbl 1262.90080 · doi:10.1007/s10107-011-0501-z
[26] Ward, J.E., Wendell, R.E.: Using block norms for location modeling. Oper. Res. 33(5), 1074-1090 (1985) · Zbl 0582.90026 · doi:10.1287/opre.33.5.1074
[27] Zaferanieh, M., Taghizadeh Kakhki, H., Brimberg, J., Wesolowsky, G.O.: A BSSS algorithm for the single facility location problem in two regions with different norms. Eur. J. Oper. Res. 190(1), 79-89 (2008) · Zbl 1146.90465 · doi:10.1016/j.ejor.2007.06.004
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.