Metaheurísticas híbridas para resolução do problema do caixeiro viajante com coleta de prêmios.
Nenhuma Miniatura disponível
Data
2007
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
O 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.
Descrição
Palavras-chave
Problema do caixeiro viajante, Metaheuristicas
Citação
CHAVES, 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.