METAHEURÍSTICAS PARA EL PROBLEMA DE LA DIVERSIDAD CON RESTRICCIONES

Abstract

El problema de la máxima diversidad con restricciones de coste y capacidad (MDP-CBC) es un problema de optimización derivado del clásico problema de la diversidad, muy usado en tareas de la vida real como la localización de estructuras. En este Trabajo de Fin de Grado (TFG), se aplica una metaheurística de búsqueda local iterativa al problema, metaheurística nunca antes aplicada al problema con restricciones, haciendo uso de un constructivo GRASP y una búsqueda local que explorará varios vecinos. Para ello, se seguirá una metodología incremental, que empezará con la generación de soluciones aleatorias para un subproblema, para luego terminar con el algoritmo completo, en el que además se implementarán varias optimizaciones que harán que el rendimiento mejore notablemente. Se realizarán varios experimentos sobre el algoritmo para establecer varios parámetros que irán apareciendo a lo largo del desarrollo del algoritmo y, una vez obtenida la versión definitiva del mismo, se comparará con el mejor algoritmo contenido en el estado del arte.