Produção Nacional
Revisado por pares
Metaheurísticas híbridas para resolução do problema do caixeiro viajante com coleta de prêmios
2007; Associação Brasileira de Engenharia de Produção; Volume: 17; Issue: 2 Linguagem: Português
10.1590/s0103-65132007000200004
ISSN1980-5411
AutoresAntônio Augusto Chaves, Fabrício Lacerda Biajoli, Otávio Massashi Mine, Marcone Jamilson Freitas Souza,
Tópico(s)Transportation and Mobility Innovations
ResumoO 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.
Referência(s)