Combination of Ant Colony Tabu Search Algorithm with Firefly Tabu Search Algorithm (ACTS-FATS) in Solving the Traveling Salesman Problem (TSP)
DOI:
10.33395/sinkron.v8i1.12016Keywords:
ACTS-FATS, Traveling Salesman ProblemAbstract
Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem, one of the optimization problems that can be applied to various activities such as finding the shortest path. The optimization problem in TSP is the most widely discussed and has become the standard for testing computational algorithms. TSP is a good object to test optimization performance. With scientific developments in the field of informatics, many researchers have optimized the application of algorithms to solve the Traveling Salesman Problem (TSP). In this study, researchers used a combination of Ant Colony Tabu Search – Firefly Algorithm Tabu Search (ACTS-FATS). The combination is doneto overcome Premature Convergence (trapped local optimum) which is a shortcoming of the ant colony algorithm, get the best running time by looking at the process of each point movement with the ant colony and firefly methods. After testing, getting the best running time results of 27.79%, and getting an accuracy rate of 17%.
Downloads
References
Alaidi, A. H. M., & Mahmood, A. (2018). Distributed hybrid method to solve multiple traveling salesman problems. International Conference on Advances in Sustainable Engineering and Applications, ICASEA 2018 - Proceedings, 74–78. https://doi.org/10.1109/ICASEA.2018.8370959
Alobaedy, M. M., Khalaf, A. A., & Muraina, I. D. (2017). Analysis of the number of ants in ant colony system algorithm. 2017 5th International Conference on Information and Communication Technology, ICoIC7 2017, 0(c), 3–7. https://doi.org/10.1109/ICoICT.2017.8074653
Deng, W., Xu, J., & Zhao, H. (2019). An Improved Ant Colony Optimization Algorithm Based on Hybrid Strategies for Scheduling Problem. IEEE Access, 7, 20281–20292. https://doi.org/10.1109/ACCESS.2019.2897580
Dewantoro, R. W., Sihombing, P., & Sutarman. (2019). The Combination of Ant Colony Optimization (ACO) and Tabu Search (TS) Algorithm to Solve the Traveling Salesman Problem (TSP). 2019 3rd International Conference on Electrical, Telecommunication and Computer Engineering, ELTICOM 2019 - Proceedings, 160–164. https://doi.org/10.1109/ELTICOM47379.2019.8943832
Gadioli, D., Nobre, R., Pinto, P., Vitali, E., Ashouri, A. H., Palermo, G., Cardoso, J., & Silvano, C. (2018). SOCRATES - A seamless online compiler and system runtime autotuning framework for energy-aware applications. Proceedings of the 2018 Design, Automation and Test in Europe Conference and Exhibition, DATE 2018, 2018-Janua, 1143–1146. https://doi.org/10.23919/DATE.2018.8342183
Hartono, Mhd. Furqan, Tulus, E. B. N. (2015). Determining Membership Function of Fuzzy Logic Using Genetic Algorithm based on Max-Min Composition. November, 1–5.
Hay’s, R. N. (2017a). Implementasi Firefly Algorithm-Tabu Search Untuk Penyelesaian Traveling Salesman Problem. Jurnal Online Informatika, 2(1), 42. https://doi.org/10.15575/join.v2i1.63
Hay’s, R. N. (2017b). Kombinasi Firefly Algorithm-Tabu Search untuk Penyelesaian Traveling Salesman Problem. Jurnal Online Informatika, 2(1), 42. https://doi.org/10.15575/join.v2i1.63
Meng, L., Lin, Y., Qing, S., & Wenjing, F. (2019). Research on Generalized Traveling Salesman Problem based on Modified Ant Colony Optimization. Proceedings of the 31st Chinese Control and Decision Conference, CCDC 2019, 4570–4574. https://doi.org/10.1109/CCDC.2019.8833167
Min, B., Shipin, Y., Xu, Y., & Lijuan, L. (2019). An Improved Ant Colony Algorithm for Traveling Salesman Problem. Proceedings of 2019 IEEE 4th Advanced Information Technology, Electronic and Automation Control Conference, IAEAC 2019, Iaeac, 1046–1050. https://doi.org/10.1109/IAEAC47372.2019.8997589
Septiyafi, I., Suprajitno, H., & Pratiwi, A. B. (2019). Penerapan Algoritma Kunang-Kunang pada Open Vehicle Routing Problem (OVRP). Contemporary Mathematics and Applications (ConMathA), 1(1), 46. https://doi.org/10.20473/conmatha.v1i1.14774
Yang, X. S. (2010). Firefly algorithm, stochastic test functions and design optimization. International Journal of Bio-Inspired Computation, 2(2), 78–84. https://doi.org/10.1504/IJBIC.2010.032124
Yang, X., & Wang, J. S. (2016). Application of improved ant colony optimization algorithm on traveling salesman problem. Proceedings of the 28th Chinese Control and Decision Conference, CCDC 2016, 2156–2160. https://doi.org/10.1109/CCDC.2016.7531342
Downloads
How to Cite
Issue
Section
License
Copyright (c) 2023 Siti Sarah Harahap, Poltak Sihombing, Muhammad Zarlis
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.