CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Parallel Approach for Optimized Travelling Salesman Problem using GPU

by Mita A. Landge, K. Rajeswari
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 136 - Number 8
Year of Publication: 2016
Authors: Mita A. Landge, K. Rajeswari
10.5120/ijca2016908151

Mita A. Landge, K. Rajeswari . Parallel Approach for Optimized Travelling Salesman Problem using GPU. International Journal of Computer Applications. 136, 8 ( February 2016), 10-13. DOI=10.5120/ijca2016908151

@article{ 10.5120/ijca2016908151,
author = { Mita A. Landge, K. Rajeswari },
title = { Parallel Approach for Optimized Travelling Salesman Problem using GPU },
journal = { International Journal of Computer Applications },
issue_date = { February 2016 },
volume = { 136 },
number = { 8 },
month = { February },
year = { 2016 },
issn = { 0975-8887 },
pages = { 10-13 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume136/number8/24172-2016908151/ },
doi = { 10.5120/ijca2016908151 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:36:31.673790+05:30
%A Mita A. Landge
%A K. Rajeswari
%T Parallel Approach for Optimized Travelling Salesman Problem using GPU
%J International Journal of Computer Applications
%@ 0975-8887
%V 136
%N 8
%P 10-13
%D 2016
%I 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.
Index Terms

Computer Science
Information Sciences

Keywords

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

Powered by PhDFocusTM