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

Jimmy Peranginangin, Ronsen Purba, Arwin Halim

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


Keywords


ACO; ACO-TS; ACO-SMARTER; TSP; Algorithms

Full Text:

PDF

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.




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

Refbacks

  • There are currently no refbacks.


Copyright (c) 2021 JURNAL MEDIA INFORMATIKA BUDIDARMA

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


JURNAL MEDIA INFORMATIKA BUDIDARMA
Universitas Budi Darma
Secretariat: Sisingamangaraja No. 338 Telp 061-7875998
Email: mib.stmikbd@gmail.com

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