Problemas de Otimização Combinatória, em especial os da classe NP-Difícil, são os problemas mais complexos de serem abordados dado que não há algoritmo exato capaz de resolvê-los. Nesse tipo de problema há exemplos clássicos como o Problema do Caixeiro Viajante, Problema da Árvore de Steiner, Problema da Mochila, Problema de Roteamento de Veículos, e muito mais. Cada um desses problemas, para além de suas implicações matemáticas, também tem grande interesse prático pois abstraem problemas do mundo real enfrentados em diversos setores, da logística à engenharia, entre outros. Uma forma possível de encontrar boas soluções a esses problemas está na aplicação de métodos metaheurísticos de otimização, como o Algoritmo Genético, GRASP, Busca Tabu, e outros. Entretanto, cada algoritmo desse utiliza uma estratégia de busca própria, que pode ocasionar em diferentes qualidades nos resultados obtidos. Do exposto, este projeto de pesquisa se propõe a realizar estudos comparativos entre diferentes metaheurísticas aplicadas a esses problemas clássicos, tentando compreender os diferentes mecanismos de busca empregados e seus impactos na qualidade dos resultados.
|
2021 |
Análise Comparativa do Reactive GRASP usando Path-Relinking e Variable Neighborhood Search Aplicado ao Problema da Diversidade Máxima
|