Biblioteca Digital de Eventos Científicos da UFPR, II Simpósio de Métodos Numéricos em Engenharia

Tamanho da fonte: 
INSERÇÃO DE BOUND EXTERNO AO METODO DE RESOLUÇÃO EM ÁRVORE APLICADO AO TSP
Alexandre Checoli Choueiri, Cassius Tadeu Scarpin, Gustavo Valentim Loch, Nathalia Cristina Ortiz, Cleder Marcos Schenekemberg, Deidson Vitorio Kurpel

Última alteração: 20-10-2017

Resumo


O Problema do Caixeiro Viajante (PCV) trata da ordenação/sequenciamento de um dado conjunto de pontos de tal forma que um caminho passando por todos os pontos, uma única vez em cada ponto, e voltando ao ponto inicial seja mínimo. Embora exista uma vasta literatura a respeito do PCV, uma pequena parte desta trata da relação do PCV com o Problema de designação PD junto a estrutura de resolução exata de adição de restrições de sub-rotas por meio de arvore de decisão. O objetivo deste trabalho é verificar a eficiência de se realizar uma inserção de um Bound para o problema, posteriormente ao seu início, dessa forma, eliminado ramos da arvore a serem exploradas pelo algoritmo. Os resultados mostraram que de fato existe uma melhora ao se partir de um Bound externo à arvore, em relação aqueles produzidos pela própria arvore.

Palavras-chave


Problema do caixeiro viajante; rBusc em arvores; Problema de designação; Metodo exato;

Texto completo: PDF