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 Mapa Sistemático

El problema de cobertura de conjuntos (SCP) es un problema clásico de optimización combinatoria que forma parte de los 21 problemas NP-completos de Karp. Muchas aplicaciones del mundo real pueden modelarse como problemas de cobertura de conjuntos (SCP), como la localización de servicios de emergencia, la planificación militar y la toma de decisiones en un contexto de pandemia COVID-19. Entre los enfoques que han resuelto este tipo de problemas 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 centrado en los métodos de inicialización y búsqueda local utilizados en estos algoritmos que han sido aplicados al SCP con el fin de identificarlos y que puedan ser aplicados en otros algoritmos. Este mapeo se llevó a cabo en tres etapas principales: planificación de la investigación, aplicación y documentación de los resultados. Los resultados indican 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 mejora los resultados obtenidos en comparación con aquellos sin búsqueda local. Además, los métodos de inicialización y búsqueda local pueden utilizarse para modificar otros algoritmos y evaluar el impacto que generan en los resultados obtenidos.

I. INTRODUCCIÓN

Entre los 21 problemas NP-completos de Karp [1] se encuentra el problema de cobertura de conjuntos (SCP). El SCP tiene muchas aplicaciones en el mundo real, como la localización de servicios de emergencia [2][3], la planificación militar [4][5] y la toma de decisiones en el contexto de una pandemia debida al COVID-19 [6][7]. Su solución viene dada por un subconjunto de elementos disponibles sujetos a las restricciones del problema. El SCP está definido por una matriz binaria 𝐴 = [𝑎_𝑖𝑗] de tamaño 𝑀 × 𝑁, en la que cada elemento puede ser 0 ó 1. La matriz es la siguiente 𝐼 = {1, ... , 𝑖, ... , 𝑁} y 𝐽 = {1, ... ,𝑗, ... 𝑀} se definen respectivamente como los conjuntos de filas y columnas de 𝐴, donde una columna 𝑗 cubre una fila 𝑖 si 𝑎_𝑖𝑗 = 1. Cada columna 𝑗 de la matriz 𝐴 está asociada a un coste no negativo 𝑐𝑗. El objetivo es elegir un subconjunto de columnas 𝑥_𝑗 ⊆ {1, . . . , 𝑁} que minimice la suma de costes 𝑐_𝑗, donde cada fila debe estar cubierta por al menos una columna. El SCP se formula según las ecuaciones (1), (2) y (3):

Minimizar:

​$𝑀𝑖𝑛 𝑓(𝑥) = displaystylesum_{j=1}^m 𝑐_𝑗𝑥_j$​