Conference Papers

Browse

Now showing 1 - 1 of 1

Near Optimal Solution for Traveling Salesman Problem using GPU
(Institute of Electrical and Electronics Engineers Inc., 2018) Yelmewad, P.; Talawar, B.
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.