Searching the Efficient Frontier for the Coherent Covering Location Problem

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).

Authors:

• Felipe Azocar Simonet
• Luis Acosta Espejo

Keywords:

• Coherent covering location problem
• efficient frontier
• Lagrangian relaxation
• data envelopment analysis.

References:

[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.