Comparative analysis of Three Metaheuristics for Solving the Travelling Salesman Problem
DOI:
https://doi.org/10.14738/tmlai.54.3211Keywords:
Metaheuristic, Cat Swarm Optimization, Bat-inspired algorithm, Cuckoo Search, Travelling salesman problem, NP-hardAbstract
this research paper aims to do a comparative study of three recent optimization metaheuristic approaches that had been applied to solve the NP-hard optimization problem called the travelling salesman problem. The three recent metaheuristics in study are cuckoo search algorithm, cat swarm optimization algorithm and bat-inspired algorithm. To compare the performances of these methods, the three metaheuristics are applied to solve some benchmark instances of TSPLIB. The obtained results are collected and the error percentage is calculated. The discussion, will present which method is more efficient to solve the real application based on the travelling salesman problem.
References
(1) N. Biggs, E. K. Lloyd and R. J. Wilson, Graph Theory, 1736-1936, Oxford University Press, 1976.
(2) M. Garey and D. S. Johnson, Computers and intractability : a Guide to the Theory of NP-Completeness Freeman San Francisco, San Francisco: Freeman, 1979.
(3) J. R. Allwright and D. Carpenter, "A distributed implementation of simulated annealing for the travelling salesman problem," Parallel Computing, vol. 10, no. 3, pp. 335-338, 1989.
(4) M. Gendreau, G. Laporte and F. Semet, "A tabu search heuristic for the undirected selective travelling salesman problem," European Journal of Operational Research, vol. 106, no. 2, pp. 539-545, 1998.
(5) M. Bouzidi and M. E. Riffi, "ADAPTATION OF THE HARMONY SEARCH ALGORITHM TO SOLVE THE TRAVELLING SALESMAN PROBLEM," Journal of Theoretical & Applied Information Technology, vol. 62, no. 1, 2014.
(6) A. Ouaarab, B. Ahiod and X.-S. Yang, "Discrete cuckoo search algorithm for the travelling salesman problem," Neural Computing and Applications, vol. 24, no. 7-8, pp. 1659-1669, 2014.
(7) Y. Nagata and D. Soler, "A new genetic algorithm for the asymmetric traveling salesman problem," Expert Systems with Applications, vol. 39, no. 10, pp. 8947-8953, 2012.
(8) K. Jun-man and Z. Yi, "Application of an improved ant
colony optimization on generalized traveling salesman problem," Energy Procedia, vol. 17, pp. 319-325, 2012.
(9) X. H. Shi, Y. C. Liang, H. P. Lee, C. Lu and Q. Wang, "Particle swarm optimization-based algorithms for TSP and generalized TSP," Information Processing Letters, vol. 103, no. 5, pp. 169-176, 2007.
(10) L.-P. Wong, M. Y. H. Low and C. S. Chong, "A bee colony optimization algorithm for traveling salesman problem," in Second Asia International Conference on Modelling & Simulation, IEEE, 2008, pp. 818-823.
(11) A. Bouzidi and M. E. Riffi, "Discrete Cat Swarm Optimization to Resolve the Traveling Salesman Problem," Interneational Journal of Advanced Research in Computer Science and Software Engineering, vol. 3, no. 9, pp. 13--18,
(12) Y. Saji and M. E. Riffi, "A novel discrete bat algorithm for solving the travelling salesman problem," Neural Computing and Applications, pp. 1-14, 2015.
(13) K. Katayama, H. Sakamoto and H. Narihisa, "The efficiency of hybrid mutation genetic algorithm for the travelling salesman problem," Mathematical and Computer Modelling, vol. 31, no. 10, pp. 197-203, 2000.
(14) H. Duan and X. Yu, "Hybrid ant colony optimization using memetic algorithm for traveling salesman problem," in Approximate Dynamic Programming and Reinforcement Learning, 2007. ADPRL 2007. IEEE International Symposium on, IEEE, 2007, pp. 92-95.
(15) Y. Marinakis and M. Marinaki, "A hybrid multi-swarm particle swarm optimization algorithm for the probabilistic traveling salesman problem," Computers & Operations Research, vol. 37, no. 3, pp. 432--442, 2010.
(16) L.-P. Wong, M. Y. H. Low and C. S. Chong, "Bee colony optimization with local search for traveling salesman problem," International Journal on Artificial Intelligence Tools, vol. 19, no. 3, pp. 305-334, 2010.
(17) S.-C. Chu, P.-W. Tsai and J.-S. Pan, "Cat swarm optimization," in PRICAI 2006: Trends in artificial intelligence, Springer, 2006, pp. 854--858.
(18) X.-S. Yang, "A new metaheuristic bat-inspired
algorithm," in Nature inspired cooperative strategies for optimization (NICSO 2010), Springer, 2010, pp. 65-74.
(19) X.-S. Yang and S. Deb, "Cuckoo search via Lévy flights," in Nature & Biologically Inspired Computing, 2009. NaBIC 2009. World Congress on, IEEE, 2009, pp. 210-214.
(20) G. Reinelt, "TSPLIB—A traveling salesman problem library," ORSA journal on computing, vol. 3, no. 4, pp. 376-384, 1991.
