Otimização de rotas de entrega de uma empresa de serviço postal de Londrina

Abstract

The Postal Service Company that was analyzed makes daily deliveries to multiple addresses and the ordering of the points served by each route is done manually and intuitively in advance by the couriers, which often causes delays, idleness, decreased productivity and perhaps an increase of costs for the company. Therefore, the objective of the present work is to present a study of solution strategies for the optimization of routes using the OR-TOOLS library, considering the addresses of deliveries, seeking to improve the route taken by the couriers. The methodology consisted in the elaboration of a data set, from a matrix of distances by latitude and longitude and application of three solution strategies: considering the problem as a Traveling Salesman Problem; another solving a VRP problem considering all delivery points of the studied scripts; and the other solving the VRP problem considering all the delivery points of the routes and using the k-Means clustering method. The results obtained showed reductions in distances traveled in relation to the actual distance traveled previously of approximately 27.12% for the first route with 113 service points and approximately 28.44% for the second route analyzed with 85 service points, based on the first strategy. Already through the second strategy, it was reduced by about 21.38% and 26.79%, respectively, for the first and second script. Finally, in Strategy 3, the reduction was approximately 25.01% for the first script and 30.21% for the second; showing that the routing strategies used here optimized the total distances covered in deliveries, which is a strong indication of an improvement in the service provided, despite the average computational times for executing the codes still being high, about 2.01 minutes for the Strategy 1, 34.76 minutes for Strategy 2 and 4.78 minutes for Strategy 3.