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

Ano: 2013 | Volume: 5 | Número: 2

Autores: Gabriel Altafini Neves da Silva¹, Francisco Assis da Silva, Daniela Tereza Ascencio Russi, Mário Augusto Pazoti, Robson Augusto Siscoutto

Palavras-chave: problema do caixeiro viajante, algoritmos heurísticos construtivos, otimização de rotas

Resumo Português:

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.

Resumo Inglês:

Define a optimized route, for example, to transport cargo to various delivery points to be covered
without prior planning, can lead to high cost and time. This problem can be named as the
Traveling Salesman Problem, which is establish a single route that passes at each vertex of a route
once, returning to the initial vertex at the end of the route so that the cost is minimal. This work is
focused on analyzing the constructive heuristic algorithms to solve the Traveling Salesman
Problem, building a route through an initial set of vertex, together and change this using a
criterion of choice at each iteration. The heuristic algorithms used for the optimization of routes
and evaluated were: nearest neighbor, furthest insertion, insertion of the fastest, closest insertion.
Through a mobile application defined and implemented in this work were obtained geographic
coordinates for the vertices of the routes used in the experiments. The results of each algorithm
were compared to obtain the best algorithm for determining the optimal route. From the results,
it was noted the advantage of using the insertion algorithm the most distant.