Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 32727
Searching the Efficient Frontier for the Coherent Covering Location Problem

Authors: Felipe Azocar Simonet, Luis Acosta Espejo


In this article, we will try to find an efficient boundary approximation for the bi-objective location problem with coherent coverage for two levels of hierarchy (CCLP). We present the mathematical formulation of the model used. Supported efficient solutions and unsupported efficient solutions are obtained by solving the bi-objective combinatorial problem through the weights method using a Lagrangean heuristic. Subsequently, the results are validated through the DEA analysis with the GEM index (Global efficiency measurement).

Keywords: Coherent covering location problem, efficient frontier, Lagrangian relaxation, data envelopment analysis.

Digital Object Identifier (DOI):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 754


[1] Alminyana, M., F. Borras, and J. T. Pastor. “A new directed branching heuristic for the pq-median problem.” Location Science 6, no. 1 (1998): 1-23.
[2] Arnold, Victor, et al. ”Primal and dual optimality in computer codes using two-stage solution procedures in DEA.” Operations Research Methods, Models and Applications (1998): 57-96.
[3] Banker, Rajiv D., Abraham Charnes, and William Wager Cooper. “Some models for estimating technical and scale inefficiencies in data envelopment analysis.” Management science 30, no. 9 (1984): 1078-1092.
[4] Charnes, Abraham, William Wager Cooper, and Edwardo Rhodes. “Measuring the efficiency of decision-making units.” European journal of operational research 3, no. 4 (1979): 339.
[5] Church, Richard, and Charles ReVelle. “The maximal covering location problem.” In Papers of the Regional Science Association, vol. 32, no. 1, pp. 101-118. Springer-Verlag, 1974.
[6] Church, Richard L., and Charles S. ReVelle. “ Theoretical and computational links between the p-median, location set-covering, and the maximal covering location problem.” Geographical Analysis 8, no. 4 (1976): 406-415.
[7] Cooper, W. W., and J. T. Pastor. “Global efficiency measurement in dea.” Working Paper departamento de estadstica e investigacin operativa. Universidad de alicante (1995).
[8] Cooper, William W., and Kaoru Tone. “Measures of inefficiency in data envelopment analysis and stochastic frontier estimation.” European Journal of Operational Research 99, no. 1 (1997): 72-88.
[9] Cook, Wade D., William W. Cooper, Lawrence M. Seiford, and Kaoru Tone. “Data Envelopment Analysis: A Comprehensive Text with Models, Applications, References and DEA-Solver Software.” Kluwer Academic Publishers, Boston, 2000.
[10] Desai, Anand, and James E. Storbeck. “A data envelopment analysis for spatial efficiency.” Computers, Environment and Urban Systems 14, no. 2 (1990): 145-156.
[11] Desai, Anand, Kingsley Haynes, and James Storbeck. “A spatial efficiency framework for the support of locational decision.” In Data Envelopment Analysis: Theory, Methodology, and Applications, pp. 235-251. Springer Netherlands, 1994.
[12] Espejo, Luis Gonzalo Acosta, and Roberto Diguez Galv˜ao. “Uma aproximao da fronteira eficiente para um problema de localizao hierrquico de mxima cobertura.” Pesquisa Operacional 24, no. 2 (2004): 303-321.
[13] Farahani, Reza Zanjirani, Nasrin Asgari, Nooshin Heidari, Mahtab Hosseininia, and Mark Goh. “Covering problems in facility location: A review.” Computers & Industrial Engineering 62, no. 1 (2012): 368-407.
[14] Farahani, Reza Zanjirani, Masoud Hekmatfar, Behnam Fahimnia, and Narges Kazemzadeh. “Hierarchical facility location problem: Models, classifications, techniques, and applications.” Computers & Industrial Engineering 68 (2014): 104-117.
[15] Fisher, H. B., and Gerard Rushton. “Spatial efficiency of service locations and the regional development process.” In Papers of the Regional Science Association, vol. 42, no. 1, pp. 83-97. Springer-Verlag, 1979.
[16] Galv˜ao, Roberto Diguez, and Charles ReVelle. “A Lagrangean heuristic for the maximal covering location problem.” European Journal of Operational Research 88, no. 1 (1996): 114-123.
[17] Galv˜ao, Roberto D., Luis Gonzalo Acosta Espejo, and Brian Boffey. “A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem.” European Journal of Operational Research 124, no. 2 (2000): 377-389.
[18] Lovell, CA Knox, and Jess T. Pastor. “Radial DEA models without inputs or without outputs.” European Journal of operational research 118, no. 1 (1999): 46-51.
[19] ahin, Gven, and Haldun Sral. “A review of hierarchical facility location models.” Computers & Operations Research 34, no. 8 (2007): 2310-2331.
[20] Serra, Daniel. “The coherent covering location problem.” Papers in Regional Science 75, no. 1 (1996): 79-101.
[21] Swain, R. A. “A decomposition algorithm for a class of facility location problems.” Ph.D dissertation, Cornell University (1971).
[22] Tulkens, H. “On FDH eddiciency: some methodological issues and applications to retail banking, courts, and urban transit.” Journal of Productivity Analysis, 4 (1993): 183-210.
[23] Veerapen, Nadarajen, Gabriela Ochoa, Mark Harman, and Edmund K. Burke. “An integer linear programming approach to the single and bi-objective next release problem.” Information and Software Technology 65 (2015): 1-13.