Parallel Computing for Iterative Hill Climbing Algorithm to solve TSP

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

Our novel Parallel Iterative Hill Climbing (PIHC) algorithm using the Variable-Nearest Neighborhood initial route gives near-optimal solution of large instance TSP problem on the GPU in a reasonable amount of time. We demonstrate improved cost quality on symmetric TSPLIB instances ranging from 200 to 85,900 cities. Our GPU implementation achieves a speedup of up to 279× over its sequential counterpart and 373× over the state-of-the-art GPU based TSP solver. The implementation gives a quality cost with error rate 0.71% in best case and 8.06% in worst case which is better than the state-of-the-art GPU based TSP solvers.