Comparison of New and Old Optimization Algorithms for Traveling Salesman Problem on Small, Medium, and Large-scale Benchmark Instances

Year 2024, Volume: 13 Issue: 1, 216 - 231, 24.03.2024

Md Al Amin Hossain , Züleyha Yılmaz Acar

https://doi.org/10.17798/bitlisfen.1380086

Abstract

The Traveling Salesman Problem (TSP), a prominent combinatorial optimization issue, is the subject of this study's evaluation of the performance of new and old optimization techniques. This paper seeks to expand knowledge of optimization techniques and how they might be applied to solve TSP challenges. The goal of the research is to compare various algorithms' scalability, convergence, and computation times on benchmark instances of several sizes. To achieve this goal, this paper carried out extensive testing using the Artificial Bee Colony (ABC), Grey Wolf Optimization (GWO), and Salp Swarm Algorithm (SSA) as new optimization algorithms and the Genetic Algorithm (GA), Ant Colony Optimization (ACO), and Simulated Annealing (SA) as old optimization algorithms. On small, medium, and large-scale benchmark cases, these algorithms were examined. The findings of this investigation show that the new optimization techniques are more convergent and scalable than the old ones, especially for medium-scale scenarios. They perform better performance in terms of solution quality by applying objective function values. The new methods also exhibit improved scalability, successfully adjusting to medium-scale instances. However, there were no discernible changes between the smaller and larger instances. This study makes an impact by offering insightful information about how well optimization methods perform while solving the TSP. Each algorithm's strengths and downsides have been reported, and these details offer useful guidance for choosing an algorithm for a certain scenario. The results also show the practical ramifications of applying novel optimization techniques, especially in medium-scale instances..

Keywords

Artificial Bee Colony, Benchmark Instances, Optimization, Traveling Salesman Problem

References

• [1] H. Cheng, H. Zheng, Y. Cong, W. Jiang, and S. Pu, “Select and Optimize : Learning to Solve Large-Scale Traveling Salesman Problem,” in Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, 2022, vol. 206, pp. 1219–1231.
• [2] Y. Wu, T. Weise, and R. Chiong, “Local Search for the Traveling Salesman Problem: A Comparative Study,” in Proceedings of 2015 IEEE 14th International Conference on Cognitive Informatics and Cognitive Computing, ICCI*CC 2015, 2015, pp. 213–220. doi: 10.1109/ICCI-CC.2015.7259388.
• [3] M. DİRİK, “Optimization: A comparison of recent meta-heuristic optimization algorithms using benchmark function,” J. Math. Sci. Model., vol. 5, no. 3, pp. 113–124, 2022, doi: 10.33187/jmsm.1115792.
• [4] M. ŞAHİN, “Improvement of the Bees Algorithm for Solving the Traveling Salesman Problems,” Bilişim Teknol. Derg., vol. 15, no. 1, pp. 65–74, 2022, doi: 10.17671/gazibtd.991866.
• [5] W. Li, C. Wang, Y. Huang, and Y. ming Cheung, “Heuristic smoothing ant colony optimization with differential information for the traveling salesman problem,” Appl. Soft Comput., vol. 133, p. 109943, 2023, doi: 10.1016/j.asoc.2022.109943.
• [6] B. A. Ajayi, M. A. Magaji, S. Musa, R. F. Olanrewaju, and A. A. Salihu, “A Comparative Analysis of Optimization Heuristics Algorithms as Optimal Solution for Travelling Salesman Problem,” in Proceedings of the 5th International Conference on Information Technology for Education and Development (ITED) 2022, 2022, pp. 3–10. doi: 10.1109/ITED56637.2022.10051627.
• [7] M. Mondal and D. Srivastava, “A Genetic Algorithm-Based Approach to Solve a New Time-Limited Travelling Salesman Problem,” Int. J. Distrib. Syst. Technol., vol. 14, no. 2, pp. 1–14, 2023, doi: 10.4018/IJDST.317377.
• [8] L. S. Hasan, “Artificial Bee Colony Algorithm and Bat Algorithm for Solving Travel Salesman Problem,” Webology, vol. 19, no. 1, pp. 4185–4193, 2022, doi: 10.14704/web/v19i1/web19276.
• [9] M. Khajehzadeh, A. Iraji, A. Majdi, S. Keawsawasvong, and M. L. Nehdi, “Adaptive Salp Swarm Algorithm for Optimization of Geotechnical Structures,” Appl. Sci., vol. 12, no. 13, 2022, doi: 10.3390/app12136749.
• [10] Y. Liu, L. Xu, Y. Han, X. Zeng, G. G. Yen, and H. Ishibuchi, “Evolutionary Multimodal Multiobjective Optimization for Traveling Salesman Problems,” IEEE Trans. Evol. Comput., pp. 1–1, 2023, doi: 10.1109/tevc.2023.3239546.
• [11] I. Khan, K. Basuli, and M. K. Maiti, “Multi-objective covering salesman problem: a decomposition approach using grey wolf optimization,” Knowl. Inf. Syst., vol. 65, no. 1, pp. 281–339, 2023, doi: 10.1007/s10115-022-01752-y.
• [12] K. Panwar and K. Deep, “Discrete Salp Swarm Algorithm for Euclidean Travelling Salesman Problem,” Appl. Intell., 2022, doi: 10.1007/s10489-022-03976-5.
• [13] I. Khan and M. K. Maiti, “A swap sequence based Artificial Bee Colony algorithm for Traveling Salesman Problem,” Swarm Evol. Comput., vol. 44, no. November 2016, pp. 428–438, 2019, doi: 10.1016/j.swevo.2018.05.006.
• [14] S. Sobti and P. Singla, “Solving Travelling Salesman Problem Using Artificial Bee Colony Based Approach,” Int. J. Eng. Res. Technol., vol. 2, no. 6, pp. 186–189, 2013, [Online]. Available: http://www.ijert.org/browse/volume-2-2013/june-2013-edition?download=3722:solving-travelling-salesman-problem-using-artificial-bee-colony-based-approach&start=20
• [15] S. Sharma and V. Jain, “A Novel Approach for Solving TSP Problem Using Genetic Algorithm Problem,” IOP Conf. Ser. Mater. Sci. Eng., vol. 1116, no. 1, p. 012194, 2021, doi: 10.1088/1757-899x/1116/1/012194.
• [16] W. Li, L. Xia, Y. Huang, and S. Mahmoodi, “An ant colony optimization algorithm with adaptive greedy strategy to optimize path problems,” J. Ambient Intell. Humaniz. Comput., vol. 13, no. 3, pp. 1557–1571, 2022, doi: 10.1007/s12652-021-03120-0.
• [17] E. Chandomi-Castellanos et al., “Modified Simulated Annealing Hybrid Algorithm to Solve the Traveling Salesman Problem,” in 2022 8th International Conference on Control, Decision and Information Technologies, CoDIT 2022, 2022, pp. 1536–1541. doi: 10.1109/CoDIT55151.2022.9804145.
• [18] T. Tlili and S. Krichen, “A simulated annealing-based recommender system for solving the tourist trip design problem,” Expert Syst. Appl., vol. 186, no. October 2020, p. 115723, 2021, doi: 10.1016/j.eswa.2021.115723.
• [19] T. Ye, H. Wang, W. Wang, T. Zeng, L. Zhang, and Z. Huang, “Artificial bee colony algorithm with an adaptive search manner and dimension perturbation,” Neural Comput. Appl., vol. 34, no. 19, pp. 16239–16253, 2022, doi: 10.1007/s00521-022-06981-4.
• [20] A. Ebrahimnejad, M. Enayattabr, H. Motameni, and H. Garg, “Modified artificial bee colony algorithm for solving mixed interval-valued fuzzy shortest path problem,” Complex Intell. Syst., vol. 7, no. 3, pp. 1527–1545, 2021, doi: 10.1007/s40747-021-00278-0.
• [21] P. Chen, M. Liu, and S. Zhou, “Discrete Salp Swarm Algorithm for symmetric traveling salesman problem,” Math. Biosci. Eng., vol. 20, no. 5, pp. 8856–8874, 2023, doi: 10.3934/mbe.2023389.
• [22] S. Kassaymeh, S. Abdullah, M. A. Al-Betar, M. Alweshah, M. Al-Laham, and Z. Othman, “Self-adaptive salp swarm algorithm for optimization problems,” Soft Comput., vol. 26, no. 18, pp. 9349–9368, 2022, doi: 10.1007/s00500-022-07280-9.
• [23] F. Boualem, S.M., Meftah, B., Debbat, “Solving Travelling Salesman Problem Using a Modified Grey Wolf Optimizer,” in International Conference on Artificial Intelligence in Renewable Energetic Systems, 2022, pp. 708–716. doi: https://doi.org/10.1007/978-3-030-92038-8_71.
• [24] H. Liu, B. Lei, W. Wang, G. Zhong, and H. Chai, “An improved grey wolf optimization for solving TSP,” in International Conference on Computer Science and Communication Technology (ICCSCT 2022), 2022, no. December 2022, p. 29. doi: 10.1117/12.2661782.
• [25] R. G. Revision, “TSPLIB 95 — TSPLIB 95 0.7.1 documentation,” Sphinx, 2018. https://tsplib95.readthedocs.io/en/stable/pages/readme.html (accessed Feb. 24, 2023).
• [26] N. Sultana, J. Chan, T. Sarwar, and A. K. Qin, “Learning to Optimise General TSP Instances,” Int. J. Mach. Learn. Cybern. Vol., vol. 13, pp. 2213–2228, 2022, doi: https://doi.org/10.1007/s13042-022-01516-8.