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

Página do item simplificado
dc.contributor.authorChaves, Antônio Augusto
dc.contributor.authorBiajoli, Fabrício Lacerda
dc.contributor.authorMine, Otávio Massashi
dc.contributor.authorSouza, Marcone Jamilson Freitas
dc.date.accessioned2015-01-26T11:17:27Z
dc.date.available2015-01-26T11:17:27Z
dc.date.issued2007
dc.description.abstractO 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.pt_BR
dc.description.abstractenThe Prize Collecting Traveling Salesman Problem (PCTSP) can be associated to a salesman who collects a prize in each city visited and pays a penalty for each city not visited, with travel costs among the cities. The objective is to minimize the sum of the travel costs and penalties, including in the tour enough number of cities that allow collecting a minimum prize. This paper contributes with the development of a hybrid metaheuristic to PCTSP, based on GRASP and search methods in variable neighborhood (VNS/VND) to solve PCTSP approximately. In order to validate the obtained solutions, we proposed a mathematical formulation to be solved by a commercial solver to find the best solution to the problem, being this solver applied to small problems. Computational results demonstrate the efficiency of the proposed method, as much in relation to the quality of the obtained final solution as in relation to the time of execution.
dc.identifier.citationCHAVES, 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.pt_BR
dc.identifier.issn0103-6513
dc.identifier.urihttp://www.repositorio.ufop.br/handle/123456789/4367
dc.language.isopt_BRpt_BR
dc.rights.licenseA Revista Produção autoriza o depósito de cópia de artigos dos professores e alunos da UFOP no Repositório Institucional da UFOP. Contato via e-mail em 26/08/2014.pt_BR
dc.subjectProblema do caixeiro viajantept_BR
dc.subjectMetaheuristicaspt_BR
dc.titleMetaheurísticas híbridas para resolução do problema do caixeiro viajante com coleta de prêmios.pt_BR
dc.title.alternativeHybrid metaheuristics for solve the prize collecting traveling salesman problem.pt_BR
dc.typeArtigo publicado em periodicopt_BR
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
ARTIGO_MetaheurísticasHíbridasResolução.pdf
Tamanho:
263.2 KB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
2.57 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar
Coleções
DECOM - Artigos publicados em periódicos