On Embarrassingly Parallel Max- Min Ant Colony Optimization for Traveling Salesperson Problem

Abstract: Ant Colony Optimization (ACO) is a technique which can be used to find approximate Hamilton cycles for the Traveling Salesperson Problem (TSP). OpenMP is a framework which suites well for building multithreaded applications. Reimplementation of the Max- Min ACO algorithm with OpenMP was made in order to investigate whether there were any speedup and efficiency improvements when solving TSP problem instances of different node sizes for increasing number of threads. The algorithm runs showed a speedup improvement for the smallest TSP problem set with four threads. For all other problem sets the speedup was near 1.0 and the efficiency decreased with increasing number of threads. The average best number of iterations decreased for the two largest TSP problem sets as the number of thread increased. The performance results were unexpected and therefore more research of parallel enhancement and correctness verification of the reimplementation needs to be done.