Um estudo empírico dos métodos de solução do problema do caixeiro viajante
Resumo
Resumo: A logística, atualmente, é uma das áreas que vem tendo grande relevância global. Isso se dá, principalmente, pela necessidade em encontrar soluções imediatas para a redução de custos organizacionais. Em se tratando do transporte, especificamente, seja ele de matéria-prima e/ou produtos finais, tem-se que o seu planejamento, quando elaborado incorretamente, acarreta em gastos excessivos que poderiam ser facilmente evitados. Seja no transporte ou em qualquer outro ramo, muitos problemas da atualidade podem ser solucionados por meio dos problemas de otimização combinatória. O Problema do Caixeiro Viajante (PCV), objeto de estudo deste trabalho, é um deles. Na literatura, pode-se encontrar diversos trabalhos, artigos e abordagens que utilizam formulações exatas e métodos heurísticos para a resolução desses problemas. O objetivo deste trabalho foi realizar um estudo empírico dos métodos de solução do PCV. Visou-se, especialmente, analisar e comparar, em termos de desempenho computacional e qualidade das soluções obtidas, quatro heurísticas de construção, sendo elas o vizin ho mais próximo, a inserção do mais próximo, a inserção do mais distante e a inserção mais rápida; e uma heurística de melhoria, a 2-opt. Além disso, houve a criação de uma ferramenta computacional para resolução de qualquer problema PCV. Para implementação, definiram-se diferentes estratégias envolvendo essas heurísticas distribuídas em nove procedimentos. Os dados utilizados foram extraídos de quatro problemas teste da TSPLIB, biblioteca com diversos exemplos de instâncias para o PCV. Os resultados obtidos foram comparados entre si, com base nos dois aspectos elencados, e os roteiros encontrados por cada um dos procedimentos, aplicados nos quatro problemas teste, plotados em forma gráfica Abstract: Logistics is currently one of the areas that has been having great global relevance. This is mainly due to the need to find immediate solutions to reduce organizational costs. In the case of transport, specifically, whether raw material and/or final products, when elaborated incorrectly, its planning results in excessive expenses that could be easily avoided. Whether in transport or any other field, many current problems can be solved through combinatorial optimization problems. The Traveling Salesman Problem (TSP), object of study of this work, is one of them. In the literature there are several works, articles and approaches that use exact formulations and heuristic methods to solve these problems. The purpose of this thesis was to conduct an empirical study of TSP solution methods. The focus was principal to analyze and compare, in terms of computational performance and quality of the solution obtained, four construction heuristics, namely the nearest neighbor, nearest insertion, farthest insertion and fastest insertion; and an improvement heuristic, the 2-opt. Furthermore, there was the creation of a computational tool to solve any TSP problem. For implementation, different strategies were defined involving these heuristics distributed into nine procedures. The data used were extracted from four test problems of TSPLIB, a library with several examples of TSP instances. The results obtained were compared with each other, based on the two listed aspects, and the tours found by each of the procedures, applied on the four test problems, plotted in graphical form