There is a great need for Artificial Intelligence and Nature Inspired Metaheuristic Algorithms for real world problems like Traveling Salesman Problem (TSP) belonging to NP-Hard Optimization problems which are hard to solve using mathematical formulation models. They are also a requirement for fast and accurate algorithms, specifically those that find out a node from start to the goal with the minimum cost, distance, time, money, energy etc. The Traveling Salesman Problem (TSP) is a combinatorial optimization problem which in it’s the purest form has a respective application for instance planning, logistics, and manufacture of microchips, military and traffic and so on. Metaheuristic techniques are general algorithmic frameworks including nature-inspired designs to solve complex optimization problems and they are a fast-growing research domain since a few decades. This paper proposes to solve this problem using hybridization of ACO (Ant Colony Optimization) and SA (Simulated Annealing). Ant Colony Optimization (ACO) is a population-based metaheuristic that can be used to find out appropriate approximate solutions to understand difficult NP-Hard optimization problems. Simulated Annealing (SA) is also a population-based metaheuristic that is inspired by annealing process proceeded with higher level temperature rate; it starts position on a first solution to maximum temperature, where the exchange states are accepted with a desired global extreme point is out of sight among many, poor temperature and probability density function, local update extrema. Moreover, MATLAB programming is used to implement the algorithms using solved TSP are three benchmarks on the same platform conditions for ACO, SA and Hybrid ACO-SA.

Metaheuristic Hybrids, Ant Colony Optimization (ACO), Simulated Annealing (SA), Traveling Salesman Problem (TSP), NP-Hard Optimization Problems, Global Pheromone Update (GPU), Local Pheromone Update (LPU)

[1] Divya Gupta, “Solving TSP using various Meta-heuristic Algorithms”, International Journal of Engineering Science, Vol. 1, pp. 26-30, 2013
[2] Anas Arram, Masri Ayob, “Comparative Study of Metaheuristic Approaches for solving Traveling Salesman Problems”, Asian Journal of Applied Sciences, Vol. 7, pp. 662-670, 2014
[3] Gunther R. Raidl, Jakob Puchinger, “Metaheuristic Hybrids”, International Series in Operations Research and Management Science, Vol. 146, pp. 469-496, 2010
[4] Teodor Gabriel Crainic, Michel Toulouse, “Parallel Meta-Heuristics”, International Series in Operations Research and Management Science, Vol. 146, pp. 497-541, 2010
[5] Marco Dorigo, Luca Maria Gambardella, “Ant Colony System: A cooperative learning approach to the Traveling Salesman Problem”, IEEE Transactions on Evolutionary Computation, Vol. 1, pp. 53-66, 1997
[6] Marcus Randall, Andrew Lewis, “A Parallel Implementation of ACO”, Journal of Parallel and Distributed Computing, Vol. 62, pp. 1421-1432, 2002
[7] Musa Peker, Baha Sen, “An efficient solving of the TSP: The Ant Colony System having parameters optimized by the Taguchi Method”, Turkish Journal of Electrical Engineering and Computer Sciences, Vol. 21, pp. 2015-2036, 2013
[8] Pan Junjie, Wang Dingwei, “An ACO Algorithm for Multiple Traveling Salesman Problem”, Proceedings of the First International Conference on Innovative Computing, Information and Control, Vol. 1, pp. 210-213, 2006
[9] Shu-Chuan Chu, John F. Roddick, “Ant Colony System with communication strategies”, Information Sciences, Vol. 167, pp. 63-76, 2004
[10] Zar Chi Su Su Hlaing, May Aye Khine, “Solving Traveling Salesman Problem by using Improved ACO Algorithm”, International Journal of Information and Education Technology, Vol. 1, pp. 404-409, 2011
[11] Chiranjib Patra, Pratyush, “Vector Ant Colony Optimization and Traveling Salesman Problem”, Computer Science and Information Technology, Vol. 4, pp. 31-39, 2014
[12] Luca Maria Gambardella, Macro Dorigo, “Solving Symmetric and Asymmetric Traveling Salesman Problems by Ant Colonies”, IEEE Conference on Evolutionary Computation, Vol. 6, pp. 622-627, 1996
[13] Dasaradh R. Mallampati, Pooja P. Mutalik, “A Parallel Multi-Phase Implementation of Simulated Annealing for the Traveling Salesman Problem”, Proceedings of the Sixth Distributed Memory Computing Conference, Vol. 6, pp. 488-491, 1991
[14] Husamettin Bayram, Ramazan Sahin, “A New Simulated Annealing Approach for Traveling Salesman Problem”, Mathematical and Computational Applications, Vol. 18, pp. 313-322, 2013
[15] Parham Azimi, Ramtin Rooeinfar, “A New Hybrid Parallel Simulated Annealing Algorithm for Traveling Salesman Problem with Transporters”, Journal of Optimization in Industrial Engineering, Vol. 15, pp. 1-13, 2014
[16] Nitesh M. Sureja, Bharat V. Chawda, “Random Traveling Salesman Problem”, International Journal of Emerging Technology and Advanced Engineering, Vol. 2, pp. 621-624, 2012
[17] David Bookstaber, “Simulated Annealing for Traveling Salesman Problem”, Springer, Vol. 1, pp. 1-9, 1997
[18] M.A. Rufai, R.M. Alabison, “Solution to the Traveling Salesperson Problem using Simulated Annealing Algorithm”, Electronic Journal of Mathematical Analysis and Applications, Vol. 5, pp. 135-142, 2017
[19] Lin Xiong, Shunxin Li, “Solving Traveling Salesman Problem Based on the Improved SA Algorithm with Sequential Access Restrictions”, Advances in Intelligent Systems Research, Vol. 130, pp. 610-616, 2016
[20] Zicheng Wang, Xuitang Geng, “An Effective Simulated Annealing Algorithm for solving the Traveling Salesman Problem”, Journal of Computational and Theoretical Nanoscience, Vol. 6, pp. 1680-1686, 2009
[21] Seyed Ahmad Sheibat Alhamdy, Mohammad Majdara, “Solving Traveling Salesman Problem using Ant Colony Optimization Algorithm and comparing with Tabu Search, Simulated Annealing and Genetic Algorithm”, Journal of Applied Sciences Research, Vol. 8, pp. 434-440, 2012
[22] Adewole A.P., Otubamowo K., “A Comparative Study of Simulated Annealing and Genetic Algorithm for solving the Traveling Salesman Problem”, International Journal of Applied Information Systems, Vol. 4, pp. 6-12, 2012
[23] Mateusz Borowski, Rafal Machon, “A Modified Traveling Salesman Problem: Algorithms and Experimentation System”, Journal of Intelligent Computing, Vol. 6, pp. 59-67, 2015
[24] Hashim Ali, Yasir Shah, “Solving Traveling Salesman Problem through Optimization Techniques using Genetic Algorithm and Ant Colony Optimization”, Journal of Applied Environmental and Biological Sciences, Vol. 6, pp. 55-62, 2016
[25] M. Fikret Ercan, Xiang Li, “Particle Swarm Optimization and its Hybrid”, International Journal of Computer and Communication Engineering, Vol. 2, pp. 52-55, 2013
[26] Muhammed Basheer Jasser, Mohamad Sarmini, “Ant Colony Optimization and a variation of Bee Colony Optimization (BCO) in solving Traveling Salesman Problem, a comparative study”, International Journal of Computer Applications, Vol. 96, pp. 1-8, 2014
[27] Younis Elhaddad, Omar Sallabi, “A New Hybrid Genetic and Simulated Annealing Algorithm to solve the Traveling Salesman Problem”, Proceedings of the world congress on Engineering, Vol. 1, pp. 11-14, 2010
[28] Huiling Bao, “A Two-Phase Hybrid Optimization Algorithm for solving complex optimization problem”, International Journal of Smart Home, Vol. 9, pp. 27-36, 2015
[29] Elena Simona, Nicoara, “Population Based Metaheuristics : A Comparative Analysis”, International Journal of Science and Engineering Investigations, Vol. 1, pp. 84-88, 2012
[30] Rajesh Matai, Surya Prakash Singh, Murari Lal Mittal, “Traveling Salesman Problem: An Overview of Applications, Formulations, and Solution Approaches”, Traveling Salesman Problem, Theory and Applications, pp. 1-24, 2010
[31] Ivan Brezina Jr., Zuzana Cickova, “Solving the Traveling Salesman Problem Using Ant Colony Optimization”, Management Information Systems, Vol. 6, pp. 010-014, 2011
[32] Zar Chi Su Su Hlaing, May Aye Khine, “An Ant Colony Optimization Algorithm for Solving Traveling Salesman Problem”, International Conference on Information Communication and Management, Vol. 16, pp. 54-59, 2011
[33] Marco Dorigo, “Ant Algorithms Solve Difficult Optimization Problems”, Springer, Vol. 1, pp. 11-22, 2001
[34] V. Cerny, “Thermodynamical Approach to Traveling Salesman Problem: An Efficient Simulated Annealing”, Journal of Optimization Theory and Applications, Vol. 45, pp. 41-51, 1985
[35] S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, “Optimization by Simulated Annealing”, Science, Vol. 220, pp. 671-680, 1983