Aplicação e análise de alguns procedimentos de contrução de rota para o problema do caixeiro viajante

espanolO transporte, em geral, absorve em media a porcentagem mais elevada de custos do que qualquer outra atividade logistica. Por isso, muitas empresas estao repensando seus processos para reducao dos mesmos. A otimizacao da distribuicao de produtos e um problema estudado ha muito tempo por pesquisadores de diversas areas. Este tipo de problema e classificado como de otimizacao combinatoria. Dentre as modelagens podem ser citados o Problema do Caixeiro Viajante (PCV) e o Problema de Roteamento de Veiculos (PRV). Estes tem por objetivo encontrar o menor caminho conectando-seNlugares de destino. O presente trabalho visa analisar e comparar, em termos de desempenho computacional e qualidade das solucoes obtidas, as principais heuristicas de construcao de rotas, alem de um Algoritmo Genetico para o PCV. Tambem aplicou-se o algoritmo 2-opt para melhoria das rotas geradas. Foram utilizados dados reais de uma distribuidora de produtos em uma determinada regiao da cidade de Curitiba (PR), Brasil. As coordenadas geograficas dos pontos de visitacao foram extraidas do aplicativo online Google Earth, as quais foramconvertidas em coordenadas cartesianas, para posterior aplicacao dos algoritmos utilizados. Os resultados obtidos foram comparados com as rotas reais que estao sendo utilizadas por um determinado representante da referida distribuidora. EnglishThe transport in general, absorb on average the highest percentage of costs than any other logistics activities. Therefore,many companies are rethinking their processes to reduce them. The optimization of product distribution is a much studied problem time by researchers from several areas. This type of problem is classified as combinatorial optimization. Among the modeling can be cited the Traveling Salesman Problem (TSP) and the problem of Vehicle Routing (PRV). These, aims to find the lowest path connecting N places of destination. The present work analyze and compare, in terms of computational performance and quality of solutions, the main route construction heuristics, and a genetic algorithm for the TSP. We also applied the algorithm 2-opt to improve the routes generated. We used real data a distributor of products in a certain region of the city of Curitiba (PR), Brazil. The geographical coordinates of places to visit were taken from the online application Google Earth, which were converted to Cartesian coordinates for application of algorithms used. The results were compared with the actual routes being used by a particular representative distributor of that.