Traveling Salesman Problem (TSP) is an NP-hard combinatorial optimization problem. Approximation algorithms have been used to reduce the worst-case factorial time complexity of TSP to non-deterministic polynomial time successfully. However, approximation methods result in a sub-optimal solution as they do not cover the search space adequately. Further, CPU implementations of approximation methods are too time consuming for large input instances. On the other hand, GPUs have been shown to be effective in exploiting data and memory level parallelism in large, complex problems.

This chapter presents a time-efficient parallel implementation of Iterative Hill Climbing algorithm (PIHC) that solves TSP on the GPU in a near-optimal manner. Performance evaluation has been carried out on symmetric TSPLIB instances ranging from 105 to 85,900 cities. The PIHC implementation gives 181× speedup over its sequential counterpart and 251× speedup over the existing GPU based TSP solver using hill climbing approach. The PIHC implementation gives a quality cost with error rate 0.72% in the best case and 8.06% in the worst case – this is better than existing GPU based TSP solvers using hill climbing approach.