Call for Paper - December 2019 Edition
IJCA solicits original research papers for the December 2019 Edition. Last date of manuscript submission is November 20, 2019. Read More

Parallel Approach for Optimized Travelling Salesman Problem using GPU

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2016
Authors:
Mita A. Landge, K. Rajeswari
10.5120/ijca2016908151

Mita A Landge and K Rajeswari. Article: Parallel Approach for Optimized Travelling Salesman Problem using GPU. International Journal of Computer Applications 136(8):10-13, February 2016. Published by Foundation of Computer Science (FCS), NY, USA. BibTeX

@article{key:article,
	author = {Mita A. Landge and K. Rajeswari},
	title = {Article: Parallel Approach for Optimized Travelling Salesman Problem using GPU},
	journal = {International Journal of Computer Applications},
	year = {2016},
	volume = {136},
	number = {8},
	pages = {10-13},
	month = {February},
	note = {Published by Foundation of Computer Science (FCS), NY, USA}
}

Abstract

The Travelling Salesman Problem (TSP) is the most widely studied optimization problem used in many practical and real time applications. The TSP needs large computational power to be optimally solved by exact algorithms. In recent years, the increased development of general-purpose Graphics Processing Unit (GPUs) has led to huge improvement in decreasing the execution time of algorithm. An Optimization algorithm to solve Graphic TSP instance with parallel approach using GPU is proposed. The new approximation algorithm using GPU can be implemented to optimize the results upto 3/2 - approximation ratio. This paper also enlists different approaches that have been proposed to solve various instances of TSP using GPU.

References

  1. Shayan Oveis Gharan “New Approximation Algorithms for Traveling Salesman Problem”2013.
  2. Nicos Christofides. Worst case analysis of a new heuristic for the traveling salesman problem. Report 388, Graduate School of Industrial Administration, Carnegie-Mellon.
  3. Dorigo, M. 1992. Optimization, Learning and Natural Algorithms, Ph.D. thesis, Politecnico di Milano, Italy, 1992.
  4. Dorigo, M. and Gambardella, L.M. 1997. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation 1, 1 (Apr. 1997),
  5. Bai, H., OuYang, D., Li, X., He, L., and Yu, H. 2009. MAX-MIN,Ant System on GPU with CUDA. Proceedings of the Fourth International Conference on Innovative Computing, Information and Control (Dec. 2009), 801-804.
  6. Cecilia, J.M., García, J.M., Nisbet, A., Amos, M., and Ujaldón, M.2013. Enhancing Data Parallelism for Ant Colony Optimization on GPUs. J. Parallel Distrib. Comput. 73, 1 (Jan. 2013), 42-51.
  7. Chen, S., Davis, S., Jiang, H., and Novobilski, A 2011.CUDABased Genetic Algorithm on Traveling Salesman Problem. Computer and Information Science 2011, R. Lee, Ed. Springer Berlin, Heidelberg.
  8. Fujimoto, N. and Tsutsui, S. 2010. A Highly-Parallel TSP Solver for a GPU Computing Platform. Proceedings of the Seventh International Conference on Numerical Methods and Applications (Aug. 2010), 264-271.
  9. Shayan Oveis Gharan, “A Randomized Rounding Approach to the Traveling Salesman Problem”2013.
  10. Molly A. O’Neil, “Rethinking the Parallelization of Random - Restart Hill Climbing A Case Study in Optimizing a 2- Opt TSP Solver for GPU Execution”, GPGPU-15 , February 07 2015, San Francisco, CA, USA
  11. Molly A. O’Neil, “A Parallel GPU Version of the Traveling Salesman Problem”, February 07 2015, San Francisco, CA, USA.
  12. Murilo Zangari de Souza, A GPU Implementation of MOEA/D-ACO for the Multiobjective Traveling Salesman Problem, 2014 Brazilian Conference on Intelligent Systems.

Keywords

Travelling Salesman Problem (TSP), Optimization Algorithms, Graphics Processing Units GPU, Approximation Algorithms.