METAHEURÍSTICA HÍBRIDA GRASP COM BUSCA TABU PARA RESOLUÇÃO DO PROBLEMA DO CAIXEIRO VIAJANTE COM COLETA DE PRÊMIOS

O problema do caixeiro viajante com coleta de prêmios (PCVCP) é uma variação do problema do caixeiro viajante na qual cada cidade visitada pelo viajante fornece um prêmio e o objetivo então é minimizar o custo de deslocamento entre as cidades ao passo em que se coleta uma quantidade mínima de prêmio. O problema tem muitas aplicações práticas em diferentes setores, como logística, roteamento de veículos e transporte de cargas, o que o torna bastante interessante de ser explorado. Este trabalho buscou solucionar aproximadamente o PCVCP através de um algoritmo codificado em C++ que combinou procedimentos das metaheurísticas GRASP e Busca Tabu. O algoritmo foi testado sobre 32 instâncias geradas com dados reais dos municípios e rodovias do Estado de São Paulo. Os resultados obtidos demonstraram que o algoritmo é capaz de encontrar boas soluções em tempo hábil para problemas semelhantes.