Near Optimal Solution for Traveling Salesman Problem using GPU

dc.contributor.authorYelmewad, P.
dc.contributor.authorTalawar, B.
dc.date.accessioned2020-03-30T10:22:25Z
dc.date.available2020-03-30T10:22:25Z
dc.date.issued2018
dc.description.abstractTraveling 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.en_US
dc.identifier.citation2018 IEEE International Conference on Electronics, Computing and Communication Technologies, CONECCT 2018, 2018, Vol., , pp.-en_US
dc.identifier.urihttps://idr.nitk.ac.in/handle/123456789/8550
dc.titleNear Optimal Solution for Traveling Salesman Problem using GPUen_US
dc.typeBook chapteren_US

Files