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

O Problema do Caixeiro Viajante (PCV) trata da ordenacao/sequenciamento de um dado conjunto de pontos de tal forma que um caminho passando por todos os pontos, uma unica vez em cada ponto, e voltando ao ponto inicial seja minimo. Embora exista uma vasta literatura a respeito do PCV, uma pequena parte desta trata da relacao do PCV com o Problema de designacao PD junto a estrutura de resolucao exata de adicao de restricoes de sub-rotas por meio de arvore de decisao. O objetivo deste trabalho e verificar a eficiencia de se realizar uma insercao de um Bound para o problema, posteriormente ao seu inicio, 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 a arvore, em relacao aqueles produzidos pela propria arvore.