Aplicação do Problema do Caixeiro Viajante na Otimização de Coleta de Amostras de Solo na Ride da Grande Teresina
Resumo
Este trabalho aborda o problema do caixeiro viajante (PCV) e sua aplicação na otimização de rotas de coleta de amostras de solo na Ride da Grande Teresina. Utilizando o conceito do ciclo de Hamilton, busca-se minimizar o tempo e os custos associados à coleta, garantindo eficiência. No modelo adotado, cada um dos 15 municípios é representado por um vértice, e as 27 estradas mapeadas entre eles são as arestas, com o peso correspondente à distância em km. O grafo resultante é não direcional, pois as estradas podem ser percorridas em qualquer sentido. Foram implementados algoritmos de força bruta e um algoritmo heurístico, o do vizinho mais próximo, para comparar a eficiência e a precisão das soluções. A análise dos resultados demonstrou que, embora o algoritmo heurístico não garante a solução ótima, ele oferece soluções razoavelmente boas em tempo viável, sendo alternativa prática para problemas de grande escala onde a otimização de recursos é crucial.Referências
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.
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.
Publicado
28/05/2025
Como Citar
SILVA, Maria Eva Clemencia Fonseca de Castro; MARCIANO, Juan Morysson Viana; AVELINO, Guilherme Amaral.
Aplicação do Problema do Caixeiro Viajante na Otimização de Coleta de Amostras de Solo na Ride da Grande Teresina. In: ENCONTRO UNIFICADO DE COMPUTAÇÃO DO PIAUÍ (ENUCOMPI), 17. , 2025, Teresina/PI.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 9-18.
DOI: https://doi.org/10.5753/enucompi.2025.9561.
