Partial Evaluation and Efficient Discarding for the Maximal Covering Location Problem | Zendy

Cynthia Porras | Zendy; Jenny Fajardo | Zendy; Alejandro Rosete | Zendy; Antonio D. Masegosa | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Partial Evaluation and Efficient Discarding for the Maximal Covering Location Problem

Author(s) -

Cynthia Porras,

Jenny Fajardo,

Alejandro Rosete,

Antonio D. Masegosa

Publication year - 2021

Publication title -

ieee access

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.587

H-Index - 127

ISSN - 2169-3536

DOI - 10.1109/access.2021.3055295

Subject(s) - aerospace , bioengineering , communication, networking and broadcast technologies , components, circuits, devices and systems , computing and processing , engineered materials, dielectrics and plasmas , engineering profession , fields, waves and electromagnetics , general topics for engineers , geoscience , nuclear engineering , photonics and electrooptics , power, energy and industry applications , robotics and control systems , signal processing and analysis , transportation

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research