Algorítmos heurísticos para el problema del Set Covering: mejora mediante aleatorización

Abstract

Los métodos heurísticos pretenden resolver problemas de optimización proporcionando soluciones factibles que, aunque no optimicen la función objetivo, se acercan mucho al valor óptimo empleando un tiempo más que razonable. En esta memoria se va a resolver el problema del Set Covering y para conseguirlo usamos algoritmos heurísticos que consisten en la combinación de un método greedy y un algoritmo de mejora, basados en dos ideas principalmente, la diversificación y la intensificación, la primera se lleva a cabo mediante la aleatorización y la segunda mediante la búsqueda local. Se estudia cómo la introducción de aleatorización, de diferentes formas, en los métodos greedy hace que mejore sustancialmente los resultados y se emplee un menor tiempo que el de los algoritmos exactos.