Um Algoritmo de Enumeração Implícita Para o Problema do Caixeiro Viajante
Resumo
O do caixeiro viajante é um problema clássico de otimização, amplamente estudado na literatura. Se por um lado há muitos procedimentos exatos e heurísticos para esse problema, por outro pouco foco foi dado a processos de enumeração. Este artigo apresenta um novo procedimento de enumeração implícita de busca de início guloso para o problema do caixeiro viajante. Esse procedimento oferece complexidade quadrática de complexidade em memória em relação ao número de cidades. A enumeração é baseada em um limitante local também aqui descrito. Com o algoritmo, problemas de pequeno tamanho (20 cidades) foram resolvidos em segundos, problemas modestamente maiores (40 cidades) levaram muito mais tempo. Soluções ótimas apresentaram poucas decisões não-gulosas, indicando uma direção para possíveis heurísticas. Se por um lado, o algoritmo pode não ser prático para problemas grandes, por outro ele pode resolver problemas de tamanho prático. Direções para melhora de performance são apresentadas bem como dicas para adaptar a técnica desenvolvida para outros problemas.