Aplicação do problema do caixeiro viajante na roteirização de entregas de uma fábrica de alumínio do Alto Sertão alagoano

Abstract

The Traveling Salesman Problem (PCV) is an important ally in the construction of routes and managerial decision making. Classified as a classic problem of combinatorial optimization, its application and development of efficient algorithms resolution is widely used to this day. The present study aims to objective to explore the application of the problem (PCV) in the context of small businesses, Taking as a case study a company from the high backlands of Alagoas. The model mathematics was implemented in the Julia language, using the Miller Tucker-Zemlin formulation to avoid the formation of subroutes, and executed for real scenarios provided by the company. As a result, the mathematical model demonstrated the possibility of carrying out more efficient routes, compared to those currently carried out by the company, in addition to efficiency in the total processing required. For route 1, the travel time, km traveled and fuel costs were reduced by 32 minutes, 18.3 km and 13.05 reais, respectively. For route 2, the travel time, Km traveled and fuel costs were reduced by 1 hour, 34.9 km and 24.89 real, respectively. However, the approach had limitations, being High execution time is required for scenarios with many clients. For In these cases, advance planning can mitigate this limitation and allow for use of the tool in any scenario. It is concluded that the result by the PCV with exact application was efficient for the two routes analyzed, resulting in a reduction of time, km and costs related to deliveries.