Parallel iterative hill climbing algorithm to solve TSP on GPU

摘要

Traveling Salesman Problem (TSP) is an NP-hard combinatorial optimization problem. Heuristicalgorithms 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 spaceadequately. Sequential heuristic approaches spend significant CPU time in neighborhood generationfor large input instances. Neighborhood generation time can be reduced by generating inparallel. GPUs have been shown to be effective in exploiting data and memory level parallelism inlarge 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 largeTSPLIB instances in a reasonable amount of time. Multiple construction heuristics approaches,thread mapping strategies, and data structures for TSPLIB instances have been evaluated. Wedemonstrate improved cost quality on symmetric TSPLIB instances up to 85,900 cities. The PIHCGPUimplementation 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 costquality with error rate 0.72% in the best case and 8.06% in the worst case.