Parallel Approach for Optimized Travelling Salesman Problem using GPU

The Travelling Salesman Problem (TSP) is the most widely studied optimization problem used in many practical and real time applications. The TSP needs large computational power to be optimally solved by exact algorithms. In recent years, the increased development of general-purpose Graphics Processing Unit (GPUs) has led to huge improvement in decreasing the execution time of algorithm. An Optimization algorithm to solve Graphic TSP instance with parallel approach using GPU is proposed. The new approximation algorithm using GPU can be implemented to optimize the results upto 3/2- approximation ratio. This paper also enlists different approaches that have been proposed to solve various instances of TSP using GPU