GRASP with Evolutionary Path Relinking for the conditional p-Dispersion problem

Resumen

En este artículo, proponemos un nuevo método heurístico que hibridiza GRASP con Reconexión de Caminos para resolver el problema de p-Dispersión condicional. Dados n elementos, de los cuales $q < n$ ya han sido seleccionados, este problema busca seleccionar $p < n$ elementos adicionales no seleccionados para maximizar la disimilitud mínima entre ellos. El problema de p-dispersión condicional modela un problema de localización de instalaciones motivado por una situación real enfrentada en muchos entornos prácticos que surgen cuando algunas instalaciones ya han sido localizadas. El algoritmo incluye una propuesta novedosa basada en una interacción eficiente entre intensificación y diversificación de búsqueda proporcionada por el componente de Reconexión de Caminos, y también incorpora una manera inteligente de medir la diversidad entre soluciones. Se realiza una experimentación computacional extensa para comparar el rendimiento de nuestra heurística con el método estado del arte. La comparación muestra que nuestra propuesta es competitiva con el método existente, ya que es capaz de identificar 17 valores mejor conocidos. Adicionalmente, nuestra experimentación incluye un caso práctico real resuelto para una empresa española en su proceso de expansión. Este caso ilustra tanto la aplicabilidad del modelo de p-dispersión condicional, como la idoneidad de nuestro algoritmo para resolver eficientemente instancias prácticas.

Citar Esta Publicación

Sánchez-Oro, J., Martínez-Gavara, A., López-Sánchez, A. D., Martí, R., & Duarte, A. (2025). GRASP with Evolutionary Path Relinking for the conditional p-Dispersion problem. Applied Soft Computing, 168, 112494.