Abstract
To model flexible objectives for discrete location problems, ordered median functions can be applied. These functions multiply a weight to the cost of fulfilling the demand of a customer which depends on the position of that cost relative to the costs of fulfilling the demand of the other customers. In this paper a reformulated and more compact version of a covering model for the discrete ordered median problem (DOMP) is considered. It is shown that by using this reformulation better solution times can be obtained. This is especially true for some objectives that are often employed in location theory. In addition, the covering model is extended so that ordered median functions with negative weights are feasible as well. This type of modeling weights has not been treated in the literature on the DOMP before. We show that several discrete location problems with equity objectives are particular cases of this model. As a result, a mixed-integer linear model for this type of problems is obtained for the first time.
Similar content being viewed by others
References
Boland N, Domí nguez-Marí n P, Nickel S, Puerto J (2005) Exact procedures for solving the discrete ordered median problem. Comput Oper Res 33: 3270–3300
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
Daskin M (1995) Network and discrete location. Wiley, New York
Domínguez-Marín P (2003) The discrete ordered median problem: models and solution methods. Kluwer, PhD Thesis
Domínguez-Marín P, Nickel S, Mlandenović N, Hansen P (2005) Heuristic procedures for solving the discrete ordered median problem. Ann Oper Res 136: 145–173
Drezner, Z, Hamacher, H (eds) (2002) Facility location: applications and theory. Springer, Berlin
Drezner Z, Thisse J-F, Wesolowsky G (1986) The minmax-min location problem. J Reg Sci 26: 87–101
Eiselt H, Laporte G (1995) Objectives in location. In: Drezner Z(eds) Facility location: a survey of applications and methods. Springer, New York, pp 151–180
Erkut E (1993) Inequality measures for location problems. Locat Sci 1: 199–217
Francis R, Lowe T, Tamir A (2002) Aggregation error bounds for a class of location models. Oper Res 48: 294–307
Hakimi S (1964) Optimal locations of switching centers and the absolute centers and medians of a graph. Oper Res 12: 450–459
Halpern J (1978) Finding minimal center-median convex combination (cent-dian) of a graph. Manage Sci 24: 353–544
Kalcsics J (2006) Unified approaches to territory design and facility location. Shaker, Aachen
Kariv O, Hakimi S (1979) An algorithmic approach to network location problems. II: the p-medians. SIAM J Appl Math 37: 539–560
Marín A (2007) Lower bounds for the two-stage uncapacitated facility location problem. Eur J Oper Res 179: 1126–1142
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: 1128–1145
Marsh M, Schilling D (1994) Equity measurement in facility location analysis: a review and framework. Eur J Oper Res 74: 1–17
Melo T, Nickel S, Saldanha da Gama F (2006) Dynamic multi-commodity facility location: a mathematical framework for strategic supply chain planning. Comput Oper Resh 33: 181–208
Mirchandani, P, Francis, R (eds) (1990) Discrete location theory.. Wiley, New York
Nickel S (2001) Discrete ordered weber problems. In: Operations research proceedings 2000. Springer, Heidelberg, pp 71–76
Nickel S, Puerto J (1999) A unified approach to network location problems. Networks 34: 283–290
Nickel S, Puerto J (2005) Facility location: a unified approach. Springer, Berlin
Puerto J, Fernández F (1995) The symmetrical single facility location problem. Technical Report, Prepublicación de la Facultaf de Mathemáticas, Universidad de Sevilla
Rodríguez-Chía A, Nickel S, Puerto J, Fernández F (2000) A flexible approach to location problems. Math Methods Oper Res 51(1): 69–89
Slater P (1978) Structure of the k-centra in a tree. In: Proceedings of the 9th Southwest conference on combinatorics, Graph Theory and Computing, pp 663–670
van Roy T, Erlenkotter D (1982) A dual-based procedure for dynamic facility location. Manage Sci 28((10): 1091–1105
Wesolowsky G (1993) The Weber problem: history and perspectives. Locat Sci 1: 5–23
Yager R (1988) On ordered weighted averaging aggregation operators in multicriteria decision making. IEEE Trans Syst Man Cybernat 18: 183–190
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Marín, A., Nickel, S. & Velten, S. An extended covering model for flexible discrete and equity location problems. Math Meth Oper Res 71, 125–163 (2010). https://doi.org/10.1007/s00186-009-0288-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00186-009-0288-3