Initialization and Local Search Methods Applied to the Set Covering Problem: A Systematic Mapping
The set covering problem (SCP) is a classical combinatorial optimization problem part of Karp's 21 NP-complete problems. Many real-world applications can be modeled as set covering problems (SCPs), such as locating emergency services, military planning, and decision-making in a COVID-19 pandem...
| Main Authors: | , , |
|---|---|
| Format: | Online |
| Language: | eng |
| Published: |
Universidad Pedagógica y Tecnológica de Colombia
2023
|
| Subjects: | |
| Online Access: | https://revistas.uptc.edu.co/index.php/ingenieria/article/view/15235 |
| _version_ | 1801706102070444032 |
|---|---|
| author | Quemá-Taimbud, Nelson-Enrique Mendoza-Becerra, Martha-Eliana Bedoya-Leyva, Oscar-Fernando |
| author_facet | Quemá-Taimbud, Nelson-Enrique Mendoza-Becerra, Martha-Eliana Bedoya-Leyva, Oscar-Fernando |
| author_sort | Quemá-Taimbud, Nelson-Enrique |
| collection | OJS |
| description | The set covering problem (SCP) is a classical combinatorial optimization problem part of Karp's 21 NP-complete problems. Many real-world applications can be modeled as set covering problems (SCPs), such as locating emergency services, military planning, and decision-making in a COVID-19 pandemic context. Among the approaches that this type of problem has solved are heuristic (H) and metaheuristic (MH) algorithms, which integrate iterative methods and procedures to explore and exploit the search space intelligently. In the present research, we carry out a systematic mapping of the literature focused on the initialization and local search methods used in these algorithms that have been applied to the SCP in order to identify them and that they can be applied in other algorithms. This mapping was carried out in three main stages: research planning, implementation, and documentation of results. The results indicate that the most used initialization method is random with heuristic search, and the inclusion of local search methods in MH algorithms improves the results obtained in comparison to those without local search. Moreover, initialization and local search methods can be used to modify other algorithms and evaluate the impact they generate on the results obtained. |
| format | Online |
| id | oai:oai.revistas.uptc.edu.co:article-15235 |
| institution | Revista Facultad de Ingeniería |
| language | eng |
| publishDate | 2023 |
| publisher | Universidad Pedagógica y Tecnológica de Colombia |
| record_format | ojs |
| spelling | oai:oai.revistas.uptc.edu.co:article-152352023-07-20T18:59:51Z Initialization and Local Search Methods Applied to the Set Covering Problem: A Systematic Mapping Métodos de inicialización y búsqueda local aplicados al problema de cobertura de conjuntos: un mapeo sistemático Quemá-Taimbud, Nelson-Enrique Mendoza-Becerra, Martha-Eliana Bedoya-Leyva, Oscar-Fernando set covering problem local search systematic mapping heuristics initialization metaheuristics optimization problema de cobertura de conjuntos búsqueda local mapeo sistemático heurísticas inicialización metaheurísticas optimización The set covering problem (SCP) is a classical combinatorial optimization problem part of Karp's 21 NP-complete problems. Many real-world applications can be modeled as set covering problems (SCPs), such as locating emergency services, military planning, and decision-making in a COVID-19 pandemic context. Among the approaches that this type of problem has solved are heuristic (H) and metaheuristic (MH) algorithms, which integrate iterative methods and procedures to explore and exploit the search space intelligently. In the present research, we carry out a systematic mapping of the literature focused on the initialization and local search methods used in these algorithms that have been applied to the SCP in order to identify them and that they can be applied in other algorithms. This mapping was carried out in three main stages: research planning, implementation, and documentation of results. The results indicate that the most used initialization method is random with heuristic search, and the inclusion of local search methods in MH algorithms improves the results obtained in comparison to those without local search. Moreover, initialization and local search methods can be used to modify other algorithms and evaluate the impact they generate on the results obtained. El problema de cobertura de conjuntos (PCC) es un problema de optimización combinatorio clásico que hace parte de los 21 problemas NP-completos de Karp. Muchas aplicaciones del mundo real pueden modelarse como PCC, como la ubicación servicios de emergencia, la planificación militar, la toma de decisiones en el contexto de la pandemia por COVID-19, entre otros. Entre los enfoques que han resuelto este tipo de problema se encuentran los algoritmos heurísticos (H) y metaheurísticos (MH), que integran métodos y procedimientos iterativos para explorar y explotar el espacio de búsqueda de forma inteligente. En la presente investigación realizamos un mapeo sistemático de la literatura enfocado en los métodos de inicialización y búsqueda local utilizados en estos algoritmos que se han aplicado al PCC con el fin de identificarlos y que puedan ser aplicados en otros algoritmos. Este mapeo se realizó en tres etapas principales: planificación de la investigación, ejecución y documentación de resultados. Se encontró que el método de inicialización más utilizado es el aleatorio con búsqueda heurística y que la inclusión de métodos de búsqueda local en los algoritmos MH mejoran los resultados obtenidos en comparación con estos sin búsqueda local. Por otra parte, se identificaron métodos de inicialización y búsqueda local que pueden ser utilizados para modificar otros algoritmos y evaluar el impacto que generan en los resultados obtenidos. Universidad Pedagógica y Tecnológica de Colombia 2023-02-28 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion application/pdf text/xml https://revistas.uptc.edu.co/index.php/ingenieria/article/view/15235 10.19053/01211129.v32.n63.2023.15235 Revista Facultad de Ingeniería; Vol. 32 No. 63 (2023): January-March 2023 (Continuous Publication); e15235 Revista Facultad de Ingeniería; Vol. 32 Núm. 63 (2023): Enero-Marzo 2023 (Publicación Continua); e15235 2357-5328 0121-1129 eng https://revistas.uptc.edu.co/index.php/ingenieria/article/view/15235/12691 https://revistas.uptc.edu.co/index.php/ingenieria/article/view/15235/13183 Copyright (c) 2023 Nelson-Enrique Quemá-Taimbud, Martha-Eliana Mendoza-Becerra, Oscar-Fernando Bedoya-Leyva http://creativecommons.org/licenses/by/4.0 |
| spellingShingle | set covering problem local search systematic mapping heuristics initialization metaheuristics optimization problema de cobertura de conjuntos búsqueda local mapeo sistemático heurísticas inicialización metaheurísticas optimización Quemá-Taimbud, Nelson-Enrique Mendoza-Becerra, Martha-Eliana Bedoya-Leyva, Oscar-Fernando Initialization and Local Search Methods Applied to the Set Covering Problem: A Systematic Mapping |
| title | Initialization and Local Search Methods Applied to the Set Covering Problem: A Systematic Mapping |
| title_alt | Métodos de inicialización y búsqueda local aplicados al problema de cobertura de conjuntos: un mapeo sistemático |
| title_full | Initialization and Local Search Methods Applied to the Set Covering Problem: A Systematic Mapping |
| title_fullStr | Initialization and Local Search Methods Applied to the Set Covering Problem: A Systematic Mapping |
| title_full_unstemmed | Initialization and Local Search Methods Applied to the Set Covering Problem: A Systematic Mapping |
| title_short | Initialization and Local Search Methods Applied to the Set Covering Problem: A Systematic Mapping |
| title_sort | initialization and local search methods applied to the set covering problem a systematic mapping |
| topic | set covering problem local search systematic mapping heuristics initialization metaheuristics optimization problema de cobertura de conjuntos búsqueda local mapeo sistemático heurísticas inicialización metaheurísticas optimización |
| topic_facet | set covering problem local search systematic mapping heuristics initialization metaheuristics optimization problema de cobertura de conjuntos búsqueda local mapeo sistemático heurísticas inicialización metaheurísticas optimización |
| url | https://revistas.uptc.edu.co/index.php/ingenieria/article/view/15235 |
| work_keys_str_mv | AT quemataimbudnelsonenrique initializationandlocalsearchmethodsappliedtothesetcoveringproblemasystematicmapping AT mendozabecerramarthaeliana initializationandlocalsearchmethodsappliedtothesetcoveringproblemasystematicmapping AT bedoyaleyvaoscarfernando initializationandlocalsearchmethodsappliedtothesetcoveringproblemasystematicmapping AT quemataimbudnelsonenrique metodosdeinicializacionybusquedalocalaplicadosalproblemadecoberturadeconjuntosunmapeosistematico AT mendozabecerramarthaeliana metodosdeinicializacionybusquedalocalaplicadosalproblemadecoberturadeconjuntosunmapeosistematico AT bedoyaleyvaoscarfernando metodosdeinicializacionybusquedalocalaplicadosalproblemadecoberturadeconjuntosunmapeosistematico |
