A Novel Approach to solve Traveling Salesman Problem (TSP) using Metaheursitic Hybrid Algorithms
DOI:
https://doi.org/10.26438/ijcse/v6i2.2538Keywords:
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)Abstract
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.
References
Divya Gupta, “Solving TSP using various Meta-heuristic Algorithms”, International Journal of Engineering Science, Vol. 1, pp. 26-30, 2013
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
Gunther R. Raidl, Jakob Puchinger, “Metaheuristic Hybrids”, International Series in Operations Research and Management Science, Vol. 146, pp. 469-496, 2010
Teodor Gabriel Crainic, Michel Toulouse, “Parallel Meta-Heuristics”, International Series in Operations Research and Management Science, Vol. 146, pp. 497-541, 2010
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
Marcus Randall, Andrew Lewis, “A Parallel Implementation of ACO”, Journal of Parallel and Distributed Computing, Vol. 62, pp. 1421-1432, 2002
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
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
Shu-Chuan Chu, John F. Roddick, “Ant Colony System with communication strategies”, Information Sciences, Vol. 167, pp. 63-76, 2004
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
Chiranjib Patra, Pratyush, “Vector Ant Colony Optimization and Traveling Salesman Problem”, Computer Science and Information Technology, Vol. 4, pp. 31-39, 2014
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
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
Husamettin Bayram, Ramazan Sahin, “A New Simulated Annealing Approach for Traveling Salesman Problem”, Mathematical and Computational Applications, Vol. 18, pp. 313-322, 2013
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
Nitesh M. Sureja, Bharat V. Chawda, “Random Traveling Salesman Problem”, International Journal of Emerging Technology and Advanced Engineering, Vol. 2, pp. 621-624, 2012
David Bookstaber, “Simulated Annealing for Traveling Salesman Problem”, Springer, Vol. 1, pp. 1-9, 1997
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
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
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
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
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
Mateusz Borowski, Rafal Machon, “A Modified Traveling Salesman Problem: Algorithms and Experimentation System”, Journal of Intelligent Computing, Vol. 6, pp. 59-67, 2015
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
M. Fikret Ercan, Xiang Li, “Particle Swarm Optimization and its Hybrid”, International Journal of Computer and Communication Engineering, Vol. 2, pp. 52-55, 2013
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
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
Huiling Bao, “A Two-Phase Hybrid Optimization Algorithm for solving complex optimization problem”, International Journal of Smart Home, Vol. 9, pp. 27-36, 2015
Elena Simona, Nicoara, “Population Based Metaheuristics : A Comparative Analysis”, International Journal of Science and Engineering Investigations, Vol. 1, pp. 84-88, 2012
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
Ivan Brezina Jr., Zuzana Cickova, “Solving the Traveling Salesman Problem Using Ant Colony Optimization”, Management Information Systems, Vol. 6, pp. 010-014, 2011
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
Marco Dorigo, “Ant Algorithms Solve Difficult Optimization Problems”, Springer, Vol. 1, pp. 11-22, 2001
V. Cerny, “Thermodynamical Approach to Traveling Salesman Problem: An Efficient Simulated Annealing”, Journal of Optimization Theory and Applications, Vol. 45, pp. 41-51, 1985
S. Kirkpatrick, C.D. Gelatt, M.P. Vecchi, “Optimization by Simulated Annealing”, Science, Vol. 220, pp. 671-680, 1983
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.
