Parallelization of Metaheuristics for the Optimization of Travelling Salesman Problem

Abstract

Travelling salesman problem is a combinatorial NP-Hard Problem. It has vast number of applications in many other fields like engineering, transportation and logistics. In the area of combinatorial Optimization Problems, it is one of the most studied problem. This Problem is acting as benchmark for many other NP-Hard Problems. Even for 20 cities CPU’s takes 100’s of years to get the optimal solution. So, for computing NP-Hard problems we require General Purpose Graphical Processing Units. Using them will reduce a drastically decrease in the running time. And at the same time improper usage of GPU’s may cause a great damage. When the problem size increases, the graph edges also increase which will leads to increase of time spent on the problem. The Travelling salesman problem we were considering this, was geometric travelling salesman problem. Solving an NP-Hard problem with actual optimal answer is very difficult. So, we prefer to go with the methods which will give near optimal solution. Heuristics are such methods. There were many heuristics methods which will solve Travelling salesman problem. In this thesis, I am considering Iterative Hill Climbing Algorithm with 2-Opt Local search. Based on some previous work now continuing and trying to improve to improve the solution. In order to find the good solutions 2-opt algorithm will act as one of the simple algorithms and proposing some modifications to this existing algorithm which may improve its efficiency. The presented algorithm is parallel and optimized for GPU based execution.