Using OR-Tools in Generating Optimized Routes at Post Offices Using Traveling Salesman Problem Algorithms

• Eolo Charles da Silva IFCE
• Diego Rocha Lima IFCE
• Luan Cosme dos Santos IFCE
• Fred Daniel Varelo da Silva IFCE

DOI: https://doi.org/10.5753/ercemapi.2023.236384

Abstract

The Brazilian Post and Telegraph Company is the largest logistics operator in Brazil and the main provider of delivery services for products purchased through e-commerce. They use the Traffic Management System to develop optimized routes in the largest operational units, but in the smaller ones it is up to the experience of the postmen. This work addressed postal deliveries in Russas-CE as a Traveling Salesman Problem and used Google OR-Tools to prepare the routes. We show its viability in developing optimized routes compared to currently used methods, minimizing costs in the delivery of objects. We conclude that the use of Google OR-Tools can increase the operational efficiency of deliveries.

References

Capterra (2022). Quick commerce: 95% dos consumidores gostariam de reduzir os prazos de entrega. [link].

Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group.

Clarke, G. and Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 12(4):568–581.

cnt (2021). Pesquisa de impacto no transporte – covid-19, 6ª rodada.

Correios (2022). relatorio-integrado-correios-2021.

ebit (2021). 44ª ed.webshoppers. Realizado pela Ebit desde 2001, o Webshoppers é o relatório de maior credibilidade sobre o comércio eletrônico brasileiro e é considerado a principal referência para os profissionais do segmento.

Ferreira, M. F., Dias, T. D. d. M. T., Ferreira, J. B. F. J. B., da Silva, F. H. B., da Silveira Santos, I. A., Ribeiro, L. C., et al. (2017). Otimização do percurso de distribuição de encomendas dos correios na cidade de coromandel-mg. Revista Agroveterinária, Negócios e Tecnologias, 2(2):42–55.

Filip, E. and Otakar, M. (2011). The travelling salesman problem and its application in logistic practice. WSEAS Transactions on Business and Economics, 8(4):163–173.

Ji, P. and Chen, K. (2007). The vehicle routing problem: the case of the hong kong postal service. Transportation Planning and Technology, 30(2-3):167–182.

Matis, P. (2008). Decision support system for solving the street routing problem. Transport, 23(3):230–235.

Oliveira, A. F. M. d. A. (2015). Extensões do problema do caixeiro viajante. PhD thesis, Universidade d Coimbra.

Perron, L. and Furnon, V. Or-tools.

Poot, A., Kant, G., and Wagelmans, A. P. M. (2002). A savings based method for real-life vehicle routing problems. Journal of the Operational Research Society, 53(1):57–68.

Rocha, D., Aloise, D., Aloise, D. J., and Contardo, C. (2022). Visual attractiveness in vehicle routing via bi-objective optimization. Computers & Operations Research, 137:105507.

Rossit, D. G., Vigo, D., Tohmé, F., and Frutos, M. (2019). Visual attractiveness in routing problems: A review. Computers & Operations Research, 103:13–34.

Sanguansat, P. (2019). Developing applications for vehicle routing problems with real time data acquisition. origins, 13(100.532713&destinations):13–847881.

Shi, K., Zhang, H., Zhang, Z., and Zhou, X. (2020). The algorithm of terminal logistics path planning based on tsp problem. In 2020 International Conference on Artificial Intelligence and Computer Engineering (ICAICE), pages 130–133.