Heurísticas eficientes para el problema de localización de cobertura mínima

M. Alcaide Catalán, A. Martínez Gavara, S. Pérez Peló

El Problema de Localización de Cobertura Mínima Gradual (GMCLP, por sus siglas en inglés)
busca ubicar instalaciones no deseadas que, aunque necesarias para cubrir una demanda,
impactan negativamente en la población cercana. El objetivo es satisfacer dicha demanda minimizando
el impacto de estas en la población cercana. El problema impone dos restricciones:
asegurar la cobertura total de la demanda del producto y mantener una distancia mínima de
seguridad d_min > 0 entre instalaciones.
El problema fue propuesto originalmente por Karatas y Eriskin en 2021, donde definieron un
modelo no lineal y propusieron dos aproximaciones lineales. En este trabajo presentamos una
alternativa mediante un algoritmo heurístico basado en GRASP y búsqueda local descenso
de vecindad variable (VND). Los resultados experimentales muestran soluciones ligeramente
superiores, con una mejora significativa en los tiempos de ejecución para alcanzar resultados
de alta calidad.

Keywords: Problema de localización, Metodología GRASP, Instalaciones no deseadas.

GT Heurísticas y metaheurísticas II
September 2, 2026  5:40 PM
Aula 29

R. Martín Santamaría, S. Salazar Cárdenas, J. M. Colmenar Verdugo, E. García Pardo

A. Martínez Gavara, H. Zheng, R. Martí, F. Glover

J. Sánchez-Díaz, S. Cavero, E. García Pardo, L. Hernando