ALGORITMOS HEURÍSTICOS CONSTRUTIVOS APLICADOS AO PROBLEMA DO CAIXEIRO VIAJANTE PARA A DEFINIÇÃO DE ROTAS OTIMIZADAS

Resumo

Definir uma rota otimizada, por exemplo, para transporte de cargas com vários pontos de entrega a serem percorridos sem planejamento prévio, pode acarretar um alto custo e tempo demasiado. Este problema pode ser abordado como o Problema do Caixeiro Viajante, que consiste em estabelecer uma única rota que passe em cada vértice de um percurso uma única vez, retornando ao vértice inicial no final do percurso de maneira que o custo seja mínimo. Este trabalho está focado em analisar os algoritmos heurísticos construtivos para resolver o Problema do Caixeiro Viajante, que constroem uma rota através de um conjunto inicial de vértices e modificam esse conjunto utilizando um critério de escolha a cada iteração. Os algoritmos heurísticos utilizados para a otimização de rotas e avaliados foram: vizinho mais próximo, inserção do mais distante, inserção do mais rápido, inserção do mais próximo. Através de um aplicativo móvel definido e implementado neste trabalho, foram obtidas as coordenadas geográficas para os vértices das rotas utilizadas nos experimentos realizados. Os resultados obtidos de cada algoritmo foram comparados entre si para a obtenção do melhor algoritmo na determinação de rota otimizada. A partir dos resultados, observou-se a vantagem do uso do algoritmo de inserção do mais distante.