A Multi-Core Iterated Local Search for the Traveling Salesman Problem using OpenMP

• Isaac Kosloski Oliveira UFMS
• Bianca de Almeida Dantas UFMS
• Graziela Santos Araújo UFMS

DOI: https://doi.org/10.5753/eradco.2024.4527

Resumo

Este artigo implementa e avalia versões sequenciais e paralelas de um algoritmo meta-heurístico, o Iterated Local Search (ILS), para resolver o Problema do Caixeiro Viajante (TSP). O algoritmo aplica iterativamente busca local para melhorar as soluções. O estudo compara a precisão, eficiência e aceleração em benchmarks do TSP, demonstrando que o algoritmo produz soluções de boa qualidade com maior velocidade computacional na versão paralela. Essa escalabilidade indica que essa abordagem pode ser adequada para aplicações do TSP no mundo real.

Referências

Helena R. Lourenço, O. M. and Stutzel, T. (2001). A beginner’s introduction to iterated local search. 4th Metaheuristics International Conference.

Reinelt, G. (1994). The Traveling Salesman: Computational Solutions for TSP Applications. Springer-Verlag Berlin Heidelberg, 1st edition.

Thomas H. Cormen, Charles E. Leiserson, R. L. R. and Stein, C. (2009). Introduction to Algorithms. The MIT Press, 3rd edition.

TspLib. Available at: [link]. Acessed on: 11/11/2023.