Traveling Salesman Problem (TSP) is an NP-hard combinatorial optimization problem. Approximation algorithms have been used to reduce the worst-case factorial time complexity of TSP to non-deterministic polynomial time successfully. However, approximation methods result in a sub-optimal solution as they do not cover the search space adequately. Further, CPU implementations of approximation methods are too time consuming for large input instances. On the other hand, GPUs have been shown to be effective in exploiting data and memory level parallelism in large, complex problems.
This chapter presents a time-efficient parallel implementation of Iterative Hill Climbing algorithm (PIHC) that solves TSP on the GPU in a near-optimal manner. Performance evaluation has been carried out on symmetric TSPLIB instances ranging from 105 to 85,900 cities. The PIHC implementation gives 181× speedup over its sequential counterpart and 251× speedup over the existing GPU based TSP solver using hill climbing approach. The PIHC implementation gives a quality cost with error rate 0.72% in the best case and 8.06% in the worst case – this is better than existing GPU based TSP solvers using hill climbing approach.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com