Parallel iterative hill climbing algorithm to solve TSP on GPU

Abstract

Traveling Salesman Problem (TSP) is an NP-hard combinatorial optimization problem. Heuristic algorithms provide satisfactory solutions to large instance TSP in a reasonable amount of time. However, heuristic methods result in suboptimal solutions as they do not cover the search space adequately. Sequential heuristic approaches spend significant CPU time in neighborhood generation for large input instances. Neighborhood generation time can be reduced by generating in parallel. GPUs have been shown to be effective in exploiting data and memory level parallelism in large complex problems. This work presents a GPU-based Parallel Iterative Hill Climbing (PIHC) algorithm using the nearest neighborhood heuristic to arrive at near-optimal solutions of large TSPLIB instances in a reasonable amount of time. Multiple construction heuristics approaches, thread mapping strategies, and data structures for TSPLIB instances have been evaluated. We demonstrate improved cost quality on symmetric TSPLIB instances up to 85,900 cities. The PIHC GPU implementation gives up to 193 speedup over its sequential counterpart and up to 979.96 speedup over a state-of-the-art GPU-based TSP solver. The PIHC implementation gives a cost quality with error rate 0.72% in the best case and 8.06% in the worst case. 2018 John Wiley & Sons, Ltd.