Please use this identifier to cite or link to this item: https://idr.nitk.ac.in/jspui/handle/123456789/8550
Title: Near Optimal Solution for Traveling Salesman Problem using GPU
Authors: Yelmewad, P.
Talawar, B.
Issue Date: 2018
Citation: 2018 IEEE International Conference on Electronics, Computing and Communication Technologies, CONECCT 2018, 2018, Vol., , pp.-
Abstract: Traveling Salesman Problem (TSP) is an NP-complete, a combinatorial optimization problem. Finding an optimal solution is intractable due to its time complexity. Therefore, approximation approaches have great importance which gives a good quality solution in a reasonable time. This paper presents the importance of constructing the initial solution using construction heuristic rather than setting up arbitrarily. Proposed GPU based Parallel Iterative Hill Climbing (PIHC) algorithm solves large TSPLIB instances. We demonstrate the efficiency of PIHC approach with the state-of-the-art approximation based and GPU based TSP solvers. PIHC produces 181� speedup over its sequential counterpart and 251� over the state-of-the-art GPU based TSP solver. Moreover, PIHC receives a better cost quality than the state-of-the-art GPU based TSP solvers which has gap rate in range of 0.72 % - 8.06%. � 2018 IEEE.
URI: http://idr.nitk.ac.in/jspui/handle/123456789/8550
Appears in Collections:2. Conference Papers

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.