Abstract
Ordered median functions have been developed to model flexible discrete location problems. To do this, a weight is associated to the distance from a customer to its closest facility, depending on the position of that distance relative to the distances of all the customers. In this paper this idea is extended in the following way. The position of each customer in the ordering with respect to the closest facility is used to choose a second weight that will be multiplied times a second measure of the customer. In our case, this second measure is the distance from the customer to the closest facility of a different type. For the solution of this model several integer programming formulations are built and computationally compared.
Similar content being viewed by others
References
Blanco V (2019) Ordered $p$-median problems with neighbourhoods. Comput Optim Appl 73(2):603–645
Blanco V, El-Haj S, Puerto J (2016) Continuous multifacility ordered median location problems. Eur J Oper Res 250(1):56–64
Boland N, Domínguez-Marín P, Nickel S, Puerto J (2006) Exact procedures for solving the discrete ordered median problem. Comput Oper Res 33(11):3270–3300
Calik H, Labbé M, Yaman H (2015) $p$-center problems. In: Location science. Springer, Berlin, pp 79–92
Cánovas L, García S, Labbé M, Marín A (2007) A strengthened formulation for the simple plant location problem with order. Oper Res Lett 35(2):141–150
Cho DC, Johnson EL, Padberg M, Rao MR (1983) On the uncapacitated plant location problem I: valid inequalities and facets. Math Oper Res 8:579–589
Cornuéjols G, Thizy JM (1982) Some facets of the simple plant location polytope. Math Program 23:50–74
Cornuéjols G, Fisher M, Nemhauser GL (1977) On the uncapacitated location problem. Ann Discrete Math 1:163–177
Daskin M (1995) Network and discrete location: models, algorithms, and applications. Wiley, New York
Domínguez-Marín P, Nickel S, Hansen P, Mladenović N (2001) Heuristic procedures for solving the discrete ordered median problem. Ann Oper Res 136(1):145–173
Drezner Z, Hamacher H (2002) Facility location: applications and theory. Springer, Berlin
Elloumi S, Labbé M, Pochet Y (2004) A new formulation and resolution method for the $p$-center problem. INFORMS J Comput 16:84–94
Espejo I, Rodríguez-Chía AM, Valero C (2009) Convex ordered median problem with lp-norms. Comput Oper Res 36(7):2250–2262
Fernández E, Landete M (2015) Fixed-charge facility location problems. In: Location science. Springer, Berlin, pp 47–77
García S, Labbé M, Marín A (2011) Solving large $p$-median problems with a radius formulation. INFORMS J Comput 22:546–556
Guignard M (1980) Fractional vertices, cuts and facets of the simple plant location problem. Math Program 12:150–162
Hakimi SL (1964) Optimum locations of switching centers and the absolute centers and medians of a graph. Oper Res 12(3):450–459
Kalcsics J, Nickel S, Puerto J, Rodríguez-Chía AM (2010) The ordered capacitated facility location problem. Top 18(1):203–222
Kaufman L, Broeckx F (1978) An algorithm for the quadratic assignment problem using Benders decomposition. Eur J Oper Res 2(3):207–211
Labbé M, Ponce D, Puerto J (2017) A comparative study of formulations and solution methods for the discrete ordered $p$-median problem. Comput Oper Res 78:230–242
Landete M, Marín A (2014) Looking for edge-equitable spanning trees. Comput Oper Res 41:44–52
Laporte G, Nickel S, Saldanha da Gama F (eds) Location science, 2nd edn. Springer, Berlin (2019)
Lawler E (1963) The quadratic assignment problem. Manag Sci 9(4):586–599
Marín A (2007) Lower bounds for the two-stage uncapacitated facility location problem. Eur J Oper Res 179:1126–1142
Marín A, Pelegrín M (2019) $p$-Median problems. In: Location science, 2nd edn. Springer, Berlin
Marín A, Nickel S, Puerto J, Velten S (2009) A flexible model and efficient solution strategies for discrete location problems. Discrete Appl Math 157(5):1128–1145
Marín A, Nickel S, Velten S (2010) An extended covering model for flexible discrete and equity location problems. Math Methods Oper Res 71(1):125–163
Marín A, Ortigosa PM, Redondo JL (2016) A parallelized Lagrangean relaxation approach for the discrete ordered median problem. Ann Oper Res 246(1, 2):253–272
Melo MT, Nickel S, Saldanha da Gama F (2006) Dynamic multi-commodity capacitated facility location: a mathematical modeling framework for strategic supply chain planning. Comput Oper Res 33:181–208
Nickel S (2001) Discrete ordered Weber problems. In: Operations research proceedings. Springer, Berlin, pp 71–76
Olender P, Ogryczak W (2019) A revised variable neighborhood search for the discrete ordered median problem. Eur J Oper Res 274(2):445–465
Puerto J, Ramos AB, Rodríguez-Chía AM (2011) Single-allocation ordered median hub location problems. Comput Oper Res 38(2):559–570
Puerto J, Pérez-Brito D, García-González CG (2014) A modified variable neighborhood search for the discrete ordered median problem. Eur J Oper Res 234(1):61–76
Puerto J, Rodríguez-Chía AM (2015) Ordered median location problems. In: Location science. Springer, Berlin, pp 249–288
ReVelle CS, Swain R (1970) Central facilities location. Geogr Anal 2:30–42
Tamir A (2001) The $k$-centrum multi-facility location problem. Discrete Appl Math 109(3):293–307
Funding
This study was funded by Ministerio de Economía, Industria y Competitividad, Gobierno de España (No. MTM2015-65915-R).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Domínguez, E., Marín, A. Discrete ordered median problem with induced order. TOP 28, 793–813 (2020). https://doi.org/10.1007/s11750-020-00570-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-020-00570-1