Please use this identifier to cite or link to this item:
Title: Parallel iterative hill climbing algorithm to solve TSP on GPU
Authors: Yelmewad, P.
Talawar, B.
Issue Date: 2019
Citation: Concurrency Computation , 2019, Vol.31, 7, pp.-
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.
Appears in Collections:1. Journal Articles

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.