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

Abstract

This paper presents the implementation and evaluation of a sequential and a parallel metaheuristic algorithm, the Iterated Local Search (ILS), to solve the Traveling Salesman Problem (TSP). The algorithm iteratively applies a local search strategy to improve solutions. The study compares accuracy, efficiency, and speedup on TSP benchmarks, demonstrating that the algorithm produces reasonable quality solutions with faster computational speed in the parallel version. This scalability indicates that this approach may be suitable for real-world TSP applications.

References

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.