Chaves, Antônio AugustoBiajoli, Fabrício LacerdaMine, Otávio MassashiSouza, Marcone Jamilson Freitas2015-01-262015-01-262007CHAVES, A. A. et al. Metaheurísticas híbridas para resolução do problema do caixeiro viajante com coleta de prêmios. Produção, São Paulo, v. 17, n. 2, p. 263-272, mai./ago. 2007. Disponível em: <http://www.scielo.br/pdf/prod/v17n2/a04v17n2.pdf>. Acesso em: 23 jan. 2015.0103-6513http://www.repositorio.ufop.br/handle/123456789/4367O Problema do Caixeiro Viajante com Coleta de Prêmios (PCVCP) pode ser associado a um caixeiro que coleta um prêmio em cada cidade visitada e paga uma penalidade para cada cidade não visitada, com um custo de deslocamento entre as cidades. O problema encontra-se em minimizar o somatório dos custos da viagem e penalidades, enquanto inclui na sua rota um número suficiente de cidades que lhe permita coletar um prêmio mínimo preestabelecido. Este trabalho contribui com o desenvolvimento de metaheurísticas híbridas para o PCVCP, baseadas em GRASP e métodos de busca em vizinhança variável (VNS/VND) para solucionar aproximadamente o PCVCP. De forma a validar as soluções obtidas, propõe-se uma formulação matemática a ser resolvida por um solver comercial, objetivando encontrar a solução ótima para o problema, sendo este solver aplicado a problemas de pequeno porte. Resultados computacionais demonstram a eficiência da abordagem híbrida proposta, tanto em relação à qualidade da solução final obtida quanto em relação ao tempo de execução.pt-BRProblema do caixeiro viajanteMetaheuristicasArtigo publicado em periodicoA Revista Produção autoriza o depósito de cópia de artigos dos professores e alunos da UFOP no Repositório Institucional da UFOP. Contato via e-mail em 26/08/2014.