Metaheurísticas híbridas para resolução do problema do caixeiro viajante com coleta de prêmios
AUTOR(ES)
Chaves, Antonio Augusto, Biajoli, Fabrício Lacerda, Mine, Otávio Massashi, Souza, Marcone Jamilson Freitas
FONTE
Production
DATA DE PUBLICAÇÃO
2007-08
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.
ASSUNTO(S)
problema do caixeiro viajante metaheurísticas grasp vns vnd
Documentos Relacionados
- Plasticidade sináptica e o problema do caixeiro viajante
- Algoritmo treansgenético na solução do problema do Caixeiro Viajante
- Algoritmos Evolucionários Aplicados ao Problema do Caixeiro Viajante Multiobjetivo.
- O problema do caixeiro viajante alugador : um estudo algorítmico
- Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante