Metaheurísticas híbridas para resolução do problema do caixeiro viajante com coleta de prêmios

Production

Antonio Augusto Chaves²  Fabrício Lacerda Biajoli²  Otávio Massashi Mine¹  Marcone Jamilson Freitas Souza¹ 

[1] ,Instituto Nacional de Pesquisas Espaciais

关键词: Problema do caixeiro viajante;    metaheurísticas;    GRASP;    VNS;    VND;    Traveling salesman problem;    metaheuristic;    GRASP;    VNS;    VND;   

DOI  :  10.1590/S0103-65132007000200004

来源: SciELO

【 摘 要 】

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.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License