Título: Evolutionary Algorithms for the Rout Optimization for Cities in Minas Gerais
Autores: Oswaldo Rodrigues de Barros Neto, Milton Pereira Bravo Neto, Marcelle Christine Aquino Silva, Gabriela Nunes Lopes
Resumo: The Traveling Salesman Problem (TSP) is one of the most well-known challenges in combinatorial optimization, extensively studied due to its theoretical and practical relevance. This work addresses a real-world instance of the TSP, applied to the 853 cities of Minas Gerais, using evolutionary algorithms and heuristics to find near-optimal solutions. Three main methods were implemented: Tabu Search, Particle Swarm Optimization (PSO), and Ant Colony Optimization (ACO), along with auxiliary algorithms such as Kruskal’s Algorithm and the Bellmore and Nemhauser Heuristic. The results demonstrated the efficiency of Tabu Search in finding a significantly lower-cost solution (26,482.811 km) compared to the other algorithms. This study also proposes suggestions for improving these approaches, highlighting the potential of evolutionary techniques in solving large-scale combinatorial problems.
Palavras-chave: Traveling Salesman Problem (TSP); Tabu Search; Ant Colony Optimization (ACO); Particle Swarm Optimization (PSO); Kruskal’s Algorithm; Bellmore and Nemhauser Heuristic; Evolutionary Computation; Combinatorial Optimization.
Páginas: 8
Código DOI: 10.21528/CBIC2025-1166532
Artigo em PDF: CBIC_2025_paper1166532.pdf
Arquivo BibTeX:
CBIC_2025_1166532.bib