Combination of Ant Colony Tabu Search Algorithm with Firefly Tabu Search Algorithm (ACTS-FATS) in Solving the Traveling Salesman Problem (TSP)

Authors

  • Siti Sarah Harahap Universitas Sumatera Utara, Medan, Indonesia
  • Poltak Sihombing Universitas Sumatera Utara, Medan, Indonesia
  • Muhammad Zarlis Department of Information Systems, Bina Nusantara University

DOI:

10.33395/sinkron.v8i1.12016

Keywords:

ACTS-FATS, Traveling Salesman Problem

Abstract

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%.

GS Cited Analysis

Downloads

Download data is not yet available.

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


Crossmark Updates

How to Cite

Harahap, S. S., Sihombing, P. . ., & Zarlis, M. . (2023). Combination of Ant Colony Tabu Search Algorithm with Firefly Tabu Search Algorithm (ACTS-FATS) in Solving the Traveling Salesman Problem (TSP). Sinkron : Jurnal Dan Penelitian Teknik Informatika, 7(1), 212-221. https://doi.org/10.33395/sinkron.v8i1.12016

Issue

Vol. 7 No. 1 (2023): Articles Research Volume 7 Issue 1, 2023

Section

Articles

License

Copyright (c) 2023 Siti Sarah Harahap, Poltak Sihombing, Muhammad Zarlis

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Crossref
Scopus
Google Scholar
Europe PMC

Most read articles by the same author(s)

1 2 > >>