Metaheurísticas híbridas para resolução do problema do caixeiro viajante com coleta de prêmios
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.
| Main Authors: | , , , |
|---|---|
| Format: | Digital revista |
| Language: | Portuguese |
| Published: |
Associação Brasileira de Engenharia de Produção
2007
|
| Online Access: | http://old.scielo.br/scielo.php?script=sci_arttext&pid=S0103-65132007000200004 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|