×

Solution methods for a min-max facility location problem with regional customers considering closest Euclidean distances. (English) Zbl 1432.90077

Summary: We study a facility location problem where a single facility serves multiple customers each represented by a (possibly non-convex) region in the plane. The aim of the problem is to locate a single facility in the plane so that the maximum of the closest Euclidean distances between the facility and the customer regions is minimized. Assuming that each customer region is mixed-integer second order cone representable, we firstly give a mixed-integer second order cone programming formulation of the problem. Secondly, we consider a solution method based on the Minkowski sums of sets. Both of these solution methods are extended to the constrained case in which the facility is to be located on a (possibly non-convex) subset of the plane. Finally, these two methods are compared in terms of solution quality and time with extensive computational experiments.

MSC:

90B85 Continuous location
90C11 Mixed integer programming
90C47 Minimax problems in mathematical programming

Software:

Isabelle/HOL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alizadeh, F.; Goldfarb, D., Second order cone programming, Math. Program., 95, 3-51 (2003) · Zbl 1153.90522 · doi:10.1007/s10107-002-0339-5
[2] Aly, Aa; Marucheck, As, Generalized Weber problem with rectangular regions, J. Oper. Res. Soc., 33, 11, 983-989 (1982) · Zbl 0492.90026 · doi:10.1057/jors.1982.209
[3] Avigad, J., Donnelly, K.: Formalizing O notation in Isabelle/HOL. In: International Joint Conference on Automated Reasoning, pp. 357-371. Springer (2004). 10.1007/978-3-540-25984-8_27 · Zbl 1126.68557
[4] Bennett, Cd; Mirakhor, A., Optimal facility location with respect to several regions, J. Reg. Sci., 14, 1, 131-136 (1974) · doi:10.1111/j.1467-9787.1974.tb00435.x
[5] Benson, H.; Saglam, U., Mixed-integer second order cone programming: a survey, Tutor. Oper. Res., 34, 11 (2005) · doi:10.1287/educ.1053.0000
[6] Bentley, Jl; Ottmann, Ta, Algorithms for reporting and counting geometric intersections, IEEE Trans. Comput., 9, 9, 643-647 (1979) · Zbl 0414.68074 · doi:10.1109/TC.1979.1675432
[7] Berger, A.; Grigoriev, A.; Winokurow, A., An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions, Comput. Optim. Appl., 68, 3, 661-669 (2017) · Zbl 1392.90095 · doi:10.1007/s10589-017-9935-4
[8] Blanco, V., Ordered p-median problems with neighbourhoods, Comput. Optim. Appl. (2019) · Zbl 1414.90254 · doi:10.1007/s10589-019-00077-x
[9] Blanco, V.; Fernández, E.; Puerto, J., Minimum spanning trees with neighborhoods: Mathematical programming formulations and solution methods, Eur. J. Oper. Res., 262, 3, 863-878 (2016) · Zbl 1375.90295 · doi:10.1016/j.ejor.2017.04.023
[10] Blanco, V.; Puerto, J.; Ben-Ali, Seh, Revisiting several problems and algorithms in continuous location with \(\ell_p\) norms, Comput. Optim. Appl., 58, 3, 563-595 (2014) · Zbl 1297.90073 · doi:10.1007/s10589-014-9638-z
[11] Blanco, V.; Puerto, J.; Ben-Ali, Seh, Continuous multifacility ordered median location problems, Eur. J. Oper. Res., 250, 1, 56-64 (2016) · Zbl 1346.90527 · doi:10.1016/j.ejor.2015.10.065
[12] Brimberg, J., Wesolowsky, G.: Note: facility location with closest rectangular distances. Naval Res. Logist. 47(1), 77-84 (2000). doi:10.1002/(SICI)1520-6750(200002)47:1<77::AID-NAV5>3.0.CO;2-# · Zbl 0953.90033
[13] Brimberg, J.; Wesolowsky, Go, Locating facilities by minimax relative to closest points of demand areas, Comput. Oper. Res., 29, 6, 625-636 (2002) · Zbl 1001.90042 · doi:10.1016/S0305-0548(00)00106-4
[14] Brimberg, J.; Wesolowsky, Go, Minisum location with closest Euclidean distances, Ann. Oper. Res., 111, 1-4, 151-165 (2002) · Zbl 1040.90020 · doi:10.1023/A:1020901719463
[15] Carrizosa, E.; Conde, E.; Muñoz Marquez, M.; Puerto, J., The generalized Weber problem with expected distances, RAIRO Oper. Res., 29, 1, 35-57 (1995) · Zbl 0835.90040 · doi:10.1051/ro/1995290100351
[16] Carrizosa, E.; Muñoz-Márquez, M.; Puerto, J., Location and shape of a rectangular facility in \({\mathbb{R}}^n \), Convexity properties. Math. program., 83, 1-3, 277-290 (1998) · Zbl 0920.90089 · doi:10.1007/BF02680563
[17] Cooper, L., Bounds on the Weber problem solution under conditions of uncertainty, J. Reg. Sci., 18, 1, 87-92 (1978) · doi:10.1111/j.1467-9787.1978.tb00530.x
[18] De Berg, M.; Van Kreveld, M.; Overmars, M.; Schwarzkopf, O., Springer, Computational Geometry (1997) · Zbl 0877.68001 · doi:10.1007/978-3-662-03427-9_1
[19] Dinler, D.; Tural, Mk, A minisum location problem with regional demand considering farthest Euclidean distances, Optim. Meth. Softw, 31, 3, 446-470 (2016) · Zbl 1344.90030 · doi:10.1080/10556788.2015.1121486
[20] Dinler, D.; Tural, Mk; Iyigun, C., Heuristics for a continuous multi-facility location problem with demand regions, Comput. Oper. Res., 62, 237-256 (2015) · Zbl 1348.90431 · doi:10.1016/j.cor.2014.09.001
[21] Drezner, Z.; Wesolowsky, Go, Location models with groups of demand points, Inf. Syst. Oper. Res., 38, 4, 359-372 (2000) · Zbl 07677627 · doi:10.1080/07408170108936860
[22] Fogel, E.; Halperin, D.; Weibel, C., On the exact maximum complexity of Minkowski sums of polytopes, Discret. Comput. Geom., 42, 4, 654 (2009) · Zbl 1207.52012 · doi:10.1007/s00454-009-9159-1
[23] Gugat, M.; Pfeiffer, B., Weber problems with mixed distances and regional demand, Math. Methods Oper. Res., 66, 3, 419-449 (2007) · Zbl 1146.90464 · doi:10.1007/s00186-007-0165-x
[24] Jeroslow, Rg; Lowe, Jk; Korte, Bk; Klaus, R., Modelling with integer variables, Mathematical Programming at Oberwolfach II, 167-184 (1984), Berlin: Springer, Berlin · Zbl 0554.90081
[25] Jiang, J.; Yuan, X., A Barzilai-Borwein-based heuristic algorithm for locating multiple facilities with regional demand, Comput. Optim. Appl., 51, 3, 1275-1295 (2012) · Zbl 1243.90097 · doi:10.1007/s10589-010-9392-9
[26] Jiang, Jl; Xu, Y., Minisum location problem with farthest Euclidean distances, Math. Methods Oper. Res., 64, 2, 285-308 (2006) · Zbl 1132.90344 · doi:10.1007/s00186-006-0084-2
[27] Juel, H., Bounds in the generalized Weber problem under locational uncertainty, Oper. Res., 29, 6, 1219-1227 (1981) · Zbl 0474.90035 · doi:10.1287/opre.29.6.1219
[28] Lobo, M.; Vandenberghe, L.; Boyd, S.; Lebret, H., Applications of second-order cone programming, Linear Algebra Appl., 284, 193-228 (1998) · Zbl 0946.90050 · doi:10.1016/S0024-3795(98)10032-0
[29] Love, Rf, A computational procedure for optimally locating a facility with respect to several rectangular regions, J. Reg.Sci., 12, 2, 233-242 (1972) · doi:10.1111/j.1467-9787.1972.tb00345.x
[30] Megiddo, N., Linear-time algorithms for linear programming in \({\mathbb{R}}^3\) and related problems, SIAM J. Comput., 12, 4, 759-776 (1983) · Zbl 0521.68034 · doi:10.1137/0212052
[31] Megiddo, N., The weighted Euclidean 1-center problem, Math. Oper. Res., 8, 4, 498-504 (1983) · Zbl 0533.90030 · doi:10.1287/moor.8.4.498
[32] Megiddo, N.; Tamir, A., New results on the complexity of p-centre problems, SIAM J. Comput., 12, 4, 751-758 (1983) · Zbl 0521.68037 · doi:10.1137/0212051
[33] Mesadi, F.; Erdil, E.; Cetin, M.; Tasdizen, T., Image segmentation using disjunctive normal Bayesian shape and appearance models, IEEE Trans. Med. Imaging, 37, 1, 293-305 (2017) · doi:10.1109/TMI.2017.2756929
[34] Nickel, S.; Puerto, J.; Rodriguez-Chia, Am, 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
[35] Puerto, J.; Rodríguez-Chía, Am, On the structure of the solution set for the single facility location problem with average distances, Math. Program., 128, 1-2, 373-401 (2011) · Zbl 1279.90106 · doi:10.1007/s10107-009-0308-3
[36] Shamos, M.I., Hoey, D.: Geometric intersection problems. In: 17th Annual Symposium on Foundations of Computer Science (sfcs 1976), pp. 208-215. IEEE (1976). 10.1109/SFCS.1976.16
[37] Sylvester, Jj, A question in the geometry of situation, Q. J. Pure Appl. Math., 1, 1, 79-80 (1857)
[38] Vielma, Jp, Mixed integer linear programming formulation techniques, Siam Rev., 57, 1, 3-57 (2015) · Zbl 1338.90277 · doi:10.1137/130915303
[39] Welzl, E.; Maurer, H., Smallest enclosing disks (balls and ellipsoids), New Results and New Trends in Computer Science, 359-370 (1991), Berlin: Springer, Berlin
[40] Wesolowsky, Go; Love, R., Location of facilities with rectangular distances among point and area destinations, Naval Res. Logist. Q., 18, 1, 83-90 (1971) · Zbl 0216.54202 · doi:10.1002/nav.3800180107
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.