Repositório contendo o trabalho final desenvolvido na disciplina Heuristicas e Metaheuristicas. UFMG 2021.01
Resumo
Este trabalho apresenta um estudo comparativo entre o algoritmo Tabu Search e duas metaheurísticas(GRASP+Path-Relinking) para solucao do problema de localizacao de instalacoes sem capacidade (UFLP). Foram usadas as instancias fornecidas por Bilde-Krarup para execucao dos testes, em que avaliamos tres metricas: qualidade da solucao, tempo de execucao e robustez das solucoes entre as instancias do conjunto. Concluımos que, apesar do melhor tempo de execucao, o metodo Tabu Search retornou solucoes piores do que o GRASP+Path-Relinking. O metodo GRASP ”puro” nao apresentou uma melhora na qualidade das solucoes, apesar do aumento significativo no tempo de execucao em relacao ao Tabu Search.
Abstract
This work presents a comparative study between the Tabu Search algorithm, and two metaheuristics (GRASP + Path-Relinking) for solving the Uncapacited Locating Facilities Problem (UFLP). The instances provided by Bilde-Krarup were used to perform the tests, in which we evaluated three metrics: quality of the solution, time of execution and robustness of the solutions between the instances of the set. We concluded that, despite the better execution time, the Tabu Search method returned worse solutions than GRASP + Path-Relinking. The ”pure” GRASP method did not show an improvement in the quality of the solutions, despite the significant increase in the execution time in relation to the Tabu Search.