Partial evaluation and efficient discarding for the maximal covering location problem
Cargando...
Fecha
2021-01-28
Título de la revista
ISSN de la revista
Título del volumen
Editor
Institute of Electrical and Electronics Engineers Inc.
Resumen
The maximal covering location problem attempts to locate a limited number of facilities in order to maximize the coverage over a set of demand nodes. This problem is NP-Hard and it has been often addressed by using metaheuristics, where the execution time directly depends on the number of evaluations of the objective function. In this article, the principles of efficient discarding and partial evaluation are applied to obtain more efficient versions of the objective function of this problem, i.e. not-approximate surrogate objective functions. An experimental study is presented to compare the surrogate functions in terms of number of distance comparisons and runtime. The results show that (on average) the best surrogate function is more than 5 times faster than the original function in general, and more than 8 times faster in the largest instances. This proposal allows for a more efficient metaheuristic solution based on swap operators.
Palabras clave
Efficient discarding
Maximal covering location problem
Objective function
Partial evaluation
Maximal covering location problem
Objective function
Partial evaluation
Descripción
Materias
Cita
Porras, C., Fajardo, J., Rosete, A., & Masegosa, A. D. (2021). Partial evaluation and efficient discarding for the maximal covering location problem. IEEE Access, 9, 20542-20556. https://doi.org/10.1109/ACCESS.2021.3055295