×

zbMATH — the first resource for mathematics

On location-allocation problems for dimensional facilities. (English) Zbl 1418.90143
Summary: This paper deals with a bilevel approach of the location-allocation problem with dimensional facilities. We present a general model that allows us to consider very general shapes of domains for the dimensional facilities, and we prove the existence of optimal solutions under mild assumptions. To achieve these results, we borrow tools from optimal transport mass theory that allow us to give explicit solution structure of the considered lower level problem. We also provide a discretization approach that can approximate, up to any degree of accuracy, the optimal solution of the original problem. This discrete approximation can be optimally solved via a mixed-integer linear program. To address very large instance sizes, we also provide a GRASP heuristic that performs rather well according to our experimental results. The paper also reports some experiments run on test data.

MSC:
90B85 Continuous location
49M25 Discrete approximations in optimal control
90B80 Discrete location and assignment
90C30 Nonlinear programming
Software:
GRASP
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Laporte, G., Nickel, S., Saldanha da Gama, F. (eds.): Location Science. Springer, Berlin (2015) · Zbl 1329.90003
[2] Mallozzi, L., D’Amato, E., Pardalos, P.M. (eds.): Spatial Interaction Models. Springer Optimizaion and Its Applications, vol. 118. Springer, Switzerland (2017)
[3] Nickel, S., Puerto, J.: Facility Location: A Unified Approach. Springer, Berlin (2005) · Zbl 1229.90001
[4] Okabe, A., Boots, B., Sugihara, K.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, vol. 501. Wiley, New York (1992) · Zbl 0877.52010
[5] Borwein, JM; Lewis, AS, Partially finite convex programming, part II: explicit lattice models, Math. Program., 57, 49-83, (1992) · Zbl 0778.90050
[6] Diaz-Banez, JM; Mesa, JA; Schobel, A., Continuous location of dimensional structures, Eur. J. Oper. Res., 152, 22-44, (2004) · Zbl 1040.90021
[7] Drezner, Z.; Steiner, S.; Wesolowsky, GO, On the circle closest to a set of points, Comput. Oper. Res., 29, 637-650, (2002) · Zbl 0994.90088
[8] Kalcsics, J.; Laporte, G. (ed.); Nickel, S. (ed.); Saldanha da Gama, F. (ed.), Districting problems, 595-622, (2015), Berlin
[9] Lowe, TJ; Hurter, AP, The generalized market area problem, Manag. Sci., 22, 1105-1115, (1976) · Zbl 0354.90019
[10] Puerto, J.; Ricca, F.; Scozzari, A., Extensive facility location problems on networks: an updated review, TOP, 26, 187-226, (2018) · Zbl 1397.90081
[11] Nickel, S.; Puerto, J.; Rodríguez-Chía, AM, An approach to location models involving sets as existing facilities, Math. Oper. Res., 28, 693-715, (2003) · Zbl 1082.90059
[12] 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, 373-401, (2011) · Zbl 1279.90106
[13] Mallozzi, L.; Puerto, J., The geometry of optimal partitions in location problems, Optim. Lett., 12, 203-220, (2018) · Zbl 1388.90070
[14] Carlier, G.; Mallozzi, L., Optimal monopoly pricing with congestion and random utility via partial mass transport, J. Math. Anal. Appl., 457, 1218-1231, (2018) · Zbl 1415.91130
[15] Mallozzi, L.; Passarelli Di Napoli, A., Optimal transport and a bilevel location-allocation problem, J. Glob. Optim., 67, 207-221, (2017) · Zbl 1387.90036
[16] Alvarez-Esteban, PC; Barrio, E.; Cuesta-Albertos, JA; Matran, C., A fixed-point approach to barycenters in Wasserstein space, J. Math. Anal. Appl., 441, 744-762, (2016) · Zbl 1383.49052
[17] Ambrosio, L.: Lecture notes on optimal transport problems. In: Colli, P., Rodrigues, J.F., Ambrosio, L., et al. (eds.) Mathematical Aspects of Evolving Interfaces. LNM 1812, pp. 1-52. Springer, Berlin (2003) · Zbl 1047.35001
[18] Carlier, G.; Kusuoka, S. (ed.); Maruyama, T. (ed.), Duality and existence for a class of mass transportation problems and economic applications, No. 5, 1-21, (2003), Tokyo
[19] Villani, C.: Optimal Transport, Old and New. Fundamental Principles of Mathematical Sciences, vol. 338. Springer, Berlin (2009) · Zbl 1156.53003
[20] Bard, J.F.: Practical Bilevel Optimization. Nonconvex Optimization and Its Applications. Springer, New York (1998) · Zbl 0943.90078
[21] Dempe, S., Annotated bibliography on bilevel programming and mathematical progrmas with equilibrium constraints, Optimization, 52, 333-359, (2003) · Zbl 1140.90493
[22] Carrizosa, E.; Puerto, J., A discretizing algorithm for location problems, Eur. J. Oper. Res., 80, 166-174, (1995) · Zbl 0928.90050
[23] Nickel, S.; Puerto, J., A unified approach to network location, Networks, 34, 283-290, (1999) · Zbl 0948.90086
[24] Puerto, J.; Rodríguez-Chía, AM, On the exponential cardinality of FDS for the ordered \(p\)-median problem, Oper. Res. Lett., 33, 641-651, (2005) · Zbl 1141.90471
[25] Feo, TA; Resende, MG, Greedy randomized adaptive search procedures, J. Glob. Optim., 6, 109-133, (1995) · Zbl 0822.90110
[26] Festa, P.; Resende, MGC; Ribeiro, CC (ed.); Hansen, P. (ed.), GRASP: an annotated bibliography, 325-367, (2002), Dordrecht
[27] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (2015)
[28] Brazil, M.; Ras, CJ; Thomas, DA, A geometric characterisation of the quadratic min-power centre, Eur. J. Oper. Res., 233, 34-42, (2014) · Zbl 1339.90191
[29] Casas-Ramirez, MS; Camacho-Vallejo, JF; Martinez-Salazar, IA, Approximating solutions to a bilevel capacitated facility location problem with customer’s patronization toward a list of preferences, Appl. Math. Comput., 319, 369-386, (2018) · Zbl 1426.90174
[30] Fourer, R., A simplex algorithm for piecewise-linear programming I: derivation and proof, Math. Program., 33, 204-233, (1985) · Zbl 0579.90084
[31] Dehne, F.; Klein, R., “The big sweep”: on the power of the wavefront approach to Voronoi diagrams, Algorithmica, 17, 19-32, (1997) · Zbl 0864.68107
[32] Hazewinkel, M. (ed.): “Greedy algorithm”, Encyclopedia of Mathematics. Springer/Kluwer Academic Publishers. ISBN 978-1-55608-010-4 (2001) [1994]
[33] Icking, C.; Klein, R.; Ma, L.; Nickel, S.; Weißler, A., On bisectors for different distance functions, Discrete Appl. Math., 109, 139-161, (2001) · Zbl 0967.68161
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.