Análise de Variantes da Metaheurística Greedy Randomized Adaptive Search Procedure Aplicadas ao Problema do Ladrão Viajante

Este trabalho propõe seis variantes da metaheurística GRASP (Greedy Randomized Adaptive Search Procedure) aplicadas ao Problema do Ladrão Viajante, que integra o Problema do Caixeiro Viajante e o Problema da Mochila. As variantes diferem quanto à parametrização (reativa ou fixa), à intensificação (Path Relinking) e à diversificação (Restart). Experimentos realizados em 18 instâncias, com 30 execuções e dois tempos-limite (600 e 3600 segundos), avaliaram os resultados médios, o desvio padrão, o intervalo de confiança e aplicaram os testes de Friedman e Nemenyi. Os resultados mostram que o tempo de execução impacta significativamente, com ganhos superiores a 10% em instâncias complexas. A variante GRASP reativa com Path Relinking e Restart obteve os melhores resultados, demonstrando que a combinação de reatividade, intensificação e diversificação melhora a qualidade das soluções para o problema abordado, principalmente em instâncias de maior porte.