INSERÇÃO DE BOUND EXTERNO AO METODO DE RESOLUÇÃO EM ÁRVORE APLICADO AO TSP

Abstract

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.