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

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.