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

Abstract

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.

Keywords

• traveling salesman problem
• constructive heuristic algorithms
• optimization of routes