Problema de asignación cuadrática. Algoritmos heurísticos

Resumen

La monografía consta de ocho capítulos, un apéndice que incluye información del problema en internet y una amplia documentación sobre el problema hasta la actualidad. Los dos primeros capítulos tratan el estado del arte del problema, con atención a las formulaciones, versiones lineales, aplicaciones, problemas relacionados, complejidad y diferentes procedimientos de acotación, algoritmos exactos y heurísticos. En el capítulo tercero se desarrollan los algoritmos heurísticos r-óptimos, y se introducen procedimientos para la selección de permutaciones iniciales que cubran de forma ajustable e inteligente el espacio de soluciones. El capítulo IV presenta tres grupos de algoritmos heurísticos originales que son capaces de modificar el entorno de búsqueda dotando así a los algoritmos de una fuerte componente de memoria adaptiva. En el capítulo V se analizan diferentes variantes originales del algoritmo GRASP, de gran influencia en la literatura. En el capítulo VI se describe la resolución exacta de ejemplos históricos, el comportamiento de metaheurísticas y los resultados obtenidos por los algoritmos que se proponen en la monografía. El capítulo VII analiza las clasificaciones de ejemplos QAP desarrollando dos novedosas clasificaciones en función de las matrices del problema, mostrando el comportamiento estadístico de los algoritmos propuestos en las clases obtenidas. En el capítulo VIII se presentan las conclusiones finales y se plantean, en un estado avanzado, las líneas de investigación futuras.