Call for Paper - May 2023 Edition
IJCA solicits original research papers for the May 2023 Edition. Last date of manuscript submission is April 20, 2023. Read More

Parallel Implementation of the Max_Min Ant System for the Travelling Salesman Problem on GPU

International Journal of Computer Applications
© 2014 by IJCA Journal
Volume 99 - Number 16
Year of Publication: 2014
Gaurav Bhardwaj
Manish Pandey

Gaurav Bhardwaj and Manish Pandey. Article: Parallel Implementation of the Max_Min Ant System for the Travelling Salesman Problem on GPU. International Journal of Computer Applications 99(16):9-13, August 2014. Full text available. BibTeX

	author = {Gaurav Bhardwaj and Manish Pandey},
	title = {Article: Parallel Implementation of the Max_Min Ant System for the Travelling Salesman Problem on GPU},
	journal = {International Journal of Computer Applications},
	year = {2014},
	volume = {99},
	number = {16},
	pages = {9-13},
	month = {August},
	note = {Full text available}


In this paper, we have proposed an approach to implement Ant colony optimization algorithm especially Max-Min Ant System for solving Travelling Salesman problem on GPU. GPUs are specially designed microprocessor for graphical operation and can be used for general purpose operations. ACO is a nature based inspired algorithm based on heuristics to find the solution for combinatorial optimization problems such as TSP. In this paper we have discussed many different programming issues of GPUs using OpenCL such synchronized memory access and barriers. We have used a partial solution for the stochastic probability function used in ACO for the tour construction to increase the speed-up. Thus with this implementation we are able to gain a speedup of 4. 01x in CPU parallel and up to 11. 29x speedup in GPU parallel.


  • E. Lawler, J. Lenstra, A. Kan, and D. Shomsys Wiley New York, 1987 The Travelling Salesman Problem
  • M. Dorigo and T. Stizzle : Bradford Company 2004. Ant Colony Optimization.
  • C. Blum. Physics of life reviews, vol. 2, no. 4, pp. 353-373, 2005. Ant colony optimization: Introduction and recent trends.
  • Y-S. You. Genetic and Evolutionary computation, 2009. Parallel ant system for Travelling Salesman Problem.
  • K. D. boese , A. B. Kahng, and S. Muddu . Operations Research letters ,16:101-113,1994. A new adaptive multistart technique for combinatorial global optimization.
  • M. Dorigo. PhD thesis, Politecnico di Milano, 1992. Optimization, Learning, and Natural Algorithms
  • T. Stizzle and H. H. Hoos. Future Generation Computer Systems, vol. 16, no8, pp. 889–914, 2000. MAX–MIN ant system
  • M. Dorigo and T. Stizzle, A Bradford Book,2004. Ant Colony Optimization.
  • Ying Zhang. PHD Thesis 2006. Performance and power comparisons between fermi and cypress GPUs.
  • A. Munshi, B. R. Gaster, T. G. Mattson, J. Fung, D. Ginsburg, Addison-Wesley pub. , 2011. OpenCL Programming Guide.
  • ] G. Reinelt, ORSA Journal on Computing, vol. 3, pp. 376–384, 1991. Tsplib–a traveling salesman problem library.
  • M. Manfrin, M. Birattari, T. Stizzle, and M. Dorigo. 5th International Workshop on Ant Colony Optimization and Swarm Intelligence, vol. LNCS 4150. Springer-Verlag, 2006, pp. 224–234. Parallel ant colony optimization for the traveling salesman problem.
  • T. Stizzle, H. Hoos MAX-MIN ant system and local search for the Travelling salesman problem
  • A. Colorni, M. Dorigo, V. Manniezo. Distributed Optimization by ant colonies. ECAL-91 European conference of Artificial Life.
  • T. Stizzle, H. Hoos. MAX-MIN Ant System. IRIDIA
  • M. Midderndorf, F. rieschle, H. Schmeck . Multi Colony Ant Algorithms. Journal of heuristics, 8:305-320,2002