Aplicação do Problema do Caixeiro Viajante numa empresa de distribuição: A Heurística de Lin Kernighan

Abstract

O presente relatório diz respeito ao meu estágio curricular integrado no plano de estudos do Mestrado em Gestão da Faculdade de Economia da Universidade de Coimbra (FEUC). O estágio, que se enquadrou na área de Logística, decorreu de 1 de setembro de 2016 a 24 de janeiro de 2017 na Fozpost, Lda.O problema do caixeiro viajante (TSP) tem como principal objetivo determinar a ordem pela qual devem ser percorridos os diversos clientes, por um veículo que sai do ponto inicial, o armazém, e regressa a este no final, de modo a minimizar a distância total percorrida. Um dos algoritmos melhor sucedidos para a resolução deste problema é o algoritmo de Lin Kernighan, que consiste num procedimento heurístico. Esta heurística foi publicada em 1973 por Lin e Kernighan, sendo considerada um dos métodos mais eficazes para obter soluções ótimas ou quase ótimas. Atendendo a estes factos, este é o algoritmo utilizado para a obtenção de rotas ótimas ou quase ótimas neste relatório.Os objetivos gerais do trabalho são apresentar o TSP, apresentar a entidade de acolhimento e dar conta da minha experiência enquanto estagiária da Fozpost, Lda. Este trabalho tem ainda o objetivo de analisar o contributo que o TSP pode dar para o quotidiano das organizações que necessitam de definir rotas para veículos e aplicar a resolução deste problema a um caso real. Fica a expectativa de que este relatório de estágio possa contribuir para incentivar as PME portuguesas deste sector a recorrer ao TSP para alcançarem melhores desempenhos. A obtenção de rotas ótimas ou próximas do ótimo poderá permitir às empresas uma poupança, no que diz respeito a: distâncias percorridas; ao consumo de gasóleo; a perdas de tempo; desgaste de carros; entre outras coisas, conduzindo a melhores desempenhos no que concerne a entregas e recolhas de encomendas bem como dos próprios estafetas uma vez que conseguem atender da melhor forma a todos os pedidos.No estudo de caso presente neste relatório verificam-se algumas diferenças entre a rota utilizada pelo estafeta e a rota obtida pela aplicação. É de realçar que as diferenças se verificam, essencialmente, pelo facto do estafeta optar pela lógica de efetuar todas as entregas e recolhas de determinada cidade e, apenas após o cumprimento dessa lógica, mudar de cidade.

This report concerns my curricular internship integrated in the study program of the Master of Management of the Faculty of Economics of the University of Coimbra (FEUC). The internship took place in the Logistics area of Fozpost, Lda, from September 1, 2016 to January 24, 2017.The Traveling Salesman Problem (TSP) has as main objective to determine the order in which various customers are to be visited, by a vehicle that leaves the initial point, the warehouse, and returns to this point in the end, in order to minimize the total distance traveled. One of the best algorithms to solve this problem is the Lin Kernighan algorithm, which consists of a heuristic procedure. This heuristic was published in 1973 by Lin and Kernighan and is considered one of the most effective methods to obtain optimal or near optimal solutions for this problem. Given these facts, this is the algorithm used to obtain optimal or near optimal routes in this report.The general objectives of the work are to present the TSP, present the host entity and report my experience as a trainee of Fozpost, Lda. This work also has the objective of analyzing the contributions that the TSP can give to the daily life of the organizations that need to define routes for vehicles and to apply the resolution of this problem to a real case. I hope that this traineeship report may help to encourage Portuguese SMEs in this sector to use the TSP to achieve better performance. Obtaining routes that are optimal or close to optimal can allow companies to achieve savings in terms of: distances traveled; fuel consumption; loss of time; car wear; among other things, leading to better performance regarding delivery and collection of orders, and also help the couriers, since they may be able to attend all requests more easily.In the case study presented in this report there are some differences between the route used by the courier and the route obtained by the application. It should be noted that the differences are essentially due to the fact that the courier opts for the logic of visiting all clients in each city and, only after this, to travel to the next city.