Analisis Perbandingan Algoritma ACO-TS dan ACO-SMARTER Dalam Menyelesaikan Traveling Salesman Problem

Authors

  • Jimmy Peranginangin STMIK Mikroskil, Medan
  • Ronsen Purba STMIK Mikroskil, Medan
  • Arwin Halim STMIK Mikroskil, Medan

DOI:

https://doi.org/10.30865/mib.v5i4.3283

Keywords:

ACO, ACO-TS, ACO-SMARTER, TSP, Algorithms

Abstract

The research conducted is the Comparative Analysis of the ACO-TS and ACO-SMARTER Algorithms in Solving the Traveling Salesman Problem where the problem to be solved is the traveling salesman problem (TSP). The purpose of this study is to hopefully be able to provide a comparison result of running time and the shortest distance between the ACO-TS algorithm and the ACO-SMARTER algorithm in solving the TSP. The test results show that the combination of the Ant Colony Optimization (ACO) algorithm and the Tabu Search (TS) algorithm is better in terms of achieving the optimum path and running time than the ACO and ACO-SMARTER algorithms in solving the Traveling Salesman Problem. The Tabu Search algorithm in the ACO algorithm acts as a controller for the routes that have been selected so that they are not processed again by the same ant. This will certainly make the ACO-TS algorithm faster in processing data because there is no data on the same route in the next round, where from 200 datasets the running time is obtained at ACO 11.5 seconds and the optimum distance is 76687, ACO SMARTER 8.5 seconds and the optimum distance is 74496 while the ACO-TS only takes 2.9 seconds and the optimum distance is 70558

References

R. N. Hay’s, “Kombinasi Firefly Algorithm-Tabu Search untuk Penyelesaian Traveling Salesman Problem,†Jurnal Online Informatika, vol. 2, no. 1, p. 42, Jul. 2017, doi: 10.15575/join.v2i1.63.

A. Jufri and B. Santoso, “Modifikasi ACO untuk Penentuan Rute Terpendek ke Kabupaten/Kota di Jawa,†Jurnal EECCIS Vol. 8, No. 2, Desember 2014, vol. 8, no. 2, pp. 187–192, 2014.

E. Nurlaelasari, S. Supriyadi, and U. T. Lenggana, “Penerapan Algoritma Ant Colony Optimization Menentukan Nilai Optimal Dalam Memilih Objek Wisata Berbasis Android,†Simetris: Jurnal Teknik Mesin, Elektro dan Ilmu Komputer, vol. 9, no. 1, pp. 287–298, 2018, doi: 10.24176/simet.v9i1.1914.

D. Y. Fallo, “Pencarian Jalur Terpendek Menggunakan Algoritma Ant Colony Optimization,†Jurnal Pendidikan Teknologi Informasi (JUKANTI), vol. 1, no. 1, pp. 28–32, 2018, doi: 10.37792/jukanti.v1i1.8.

W. Deng, J. Xu, and H. Zhao, “An Improved Ant Colony Optimization Algorithm Based on Hybrid Strategies for Scheduling Problem,†IEEE Access, vol. 7, pp. 20281–20292, 2019, doi: 10.1109/ACCESS.2019.2897580.

Z. Swiatnicki, “Application of ant colony optimization algorithms for transportation problems using the example of the travelling salesman problem,†in 2015 4th International Conference on Advanced Logistics and Transport (ICALT), May 2015, pp. 82–87. doi: 10.1109/ICAdLT.2015.7136597.

R. A. S. Mayang Putri Khairunnisa, Bambang Pramono, “Implementasi Algoritma Tabu Search pada Aplikasi Penjadwalan Mata Pelajaran (Studi Kasus: SMA NEGERI 4 Kendari),†Informatics Engineering Department of Halu Oleo University, vol. 2, no. 2, pp. 31–39, 2017.

Y. Yunita, “Implementasi Metode Simple Multi-Attribute Rating Technique Exploiting Rank (SMARTER) Pada Sistem Pendukung Keputusan,†Kntia Unsri, vol. 4, pp. 57–60, 2017.

Miswanto, F. Pernando, and I. Aditya Firmansyah, “Implementasi Algoritma Tabu Search Untuk Mengoptimasi Penjadwalan Preventive Maintenancept Solusi Aplikasi Interaktif,†Sentika, vol. 2018, no. Sentika, pp. 23–24, 2018, [Online]. Available: http://prosiding.uika-bogor.ac.id/index.php/semnati/article/view/93

S. Hafiz, N. Ginting, and E. B. Nababan, “Performance Improvement of Ant Colony Optimization Algorithm Using Multi-Attribute Rating Simple Technique Exploiting Ranks,†International Journal of Research and Review, vol. 7, no. February, pp. 150–154, 2020.

Z. Wang, H. Xing, T. Li, Y. Yang, R. Qu, and Y. Pan, “A Modified Ant Colony Optimization Algorithm for Network Coding Resource Minimization,†IEEE Transactions on Evolutionary Computation, vol. 20, no. 3, pp. 325–342, Jun. 2016, doi: 10.1109/TEVC.2015.2457437.

G. Ping, X. Chunbo, C. Yi, L. Jing, and L. Yanqing, “Adaptive ant colony optimization algorithm,†in 2014 International Conference on Mechatronics and Control (ICMC), Jul. 2014, pp. 95–98. doi: 10.1109/ICMC.2014.7231524.

I. Noviasari, A. Rusli, and S. Hansun, “Penerapan Algoritma ACO untuk Penjadwalan Kuliah Pengganti pada Perguruan Tinggi (Studi Kasus: Program Studi Informatika, Universitas Multimedia Nusantara),†Ultima InfoSys, vol. 9, no. 2, pp. 79–85, Mar. 2019, doi: 10.31937/si.v9i2.1062.

Y. C. Sitanggang, C. Dewi, and R. C. Wihandika, “Pemilihan Rute Optimal Penjemputan Penumpang Travel Menggunakan Ant Colony Optimization Pada Multiple Travelling Salesman Problem (M-TSP),†Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer (J-PTIIK) Universitas Brawijaya, vol. 2, no. 9, pp. 3138–3145, 2018.

V. Rohini and A. M. Natarajan, “Comparison of genetic algorithm with Particle Swarm Optimisation, ant colony optimisation and Tabu search based on university course scheduling system,†Indian Journal of Science and Technology, vol. 9, no. 21, 2016, doi: 10.17485/ijst/2016/v9i21/85379.

Q. Li, W. Tu, and L. Zhuo, “Reliable Rescue Routing Optimization for Urban Emergency Logistics under Travel Time Uncertainty,†Int. J. Geo-Information, 2018.

A. K. Agrawal, R. Kumar, P. Bhardwaj, and S. Sharma, “Particle SWARM optimization for natural grouping in context for group technology application,†in International Conference on Industrial Engineering and Operations Management, 2015, pp. 568–575.

Downloads

Published

2021-10-26

Issue

Vol. 5 No. 4 (2021): Oktober 2021

Section

Articles

License

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

Authors who publish with this journal agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under Creative Commons Attribution 4.0 International License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (Refer to The Effect of Open Access).