Application of the Traveling Salesman Problem in the Optimization of Soil Sample Collection in the Grande Teresina Integrated Development Region

• Maria Eva Clemencia Fonseca de Castro Silva UFPI
• Juan Morysson Viana Marciano UFPI
• Guilherme Amaral Avelino UFPI

DOI: https://doi.org/10.5753/enucompi.2025.9561

Abstract

This paper addresses the traveling salesman problem (TSP) and its application in optimizing soil sample collection routes in the Greater Teresina RIDE. Using the Hamilton cycle concept, the aim is to minimize the time and costs associated with collection, ensuring efficiency. In the adopted model, each of the 15 municipalities is represented by a vertex, and the 27 roads mapped between them are the edges, with the weight corresponding to the distance in km. The resulting graph is non-directional, since the roads can be traveled in any direction. Brute force algorithms and a heuristic algorithm, the nearest neighbor, were implemented to compare the efficiency and accuracy of the solutions. The analysis of the results demonstrated that, although the heuristic algorithm does not guarantee the optimal solution, it offers reasonably good solutions in a feasible time, being a practical alternative for large-scale problems where resource optimization is crucial.

References

Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study. Vol. 17. Princeton University Press.

Bellmore, M., & Nemhauser, G. L. (1968). The Traveling Salesman Problem: A Survey. Operations Research, 16(3).

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2012). Algoritmos. 3ª edição. Rio de Janeiro: Elsevier.

Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numer. Math. 1, 269–271. Disponível em: [link], acessado em 29 de julho de 2024.

Goldbarg, M. C. e Luna, H. P. L. (2005). Otimização combinatória e programação linear: modelos e algoritmos. 2. ed. Rio de Janeiro: Elsevier.

Instituto De Pesquisa Econômica Aplicada. Região Integrada de Desenvolvimento (Ride) da Grande Teresina. Disponível em: [link], acessado em 29 de julho de 2024.

Karp, R. M. (1972). Reducibility among Combinatorial Problems. Complexity of Computer Computations, 85–103. DOI: 10.1007/978-1-4684-2001-2_9.

Papadimitriou, C. H., & Steiglitz, K. (1998). Combinatorial Optimization: Algorithms and Complexity. Dover Publications.