## JURNAL MEDIA INFORMATIKA BUDIDARMA
ISSN 2614-5278 (media cetak), ISSN 2548-8368 (media online) Available Online at https://ejurnal.stmik-budidarma.ac.id/index.php/mib DOI 10.30865/mib.v5i4.3283

## Analisis Perbandingan Algoritma ACO-TS dan ACO-SMARTER Dalam Menyelesaikan Traveling Salesman Problem
Jimmy Peranginangin * , Ronsen Purba, Arwin Halim
Program Studi Magister Teknologi Informasi, STMIK Mikroskil, Medan, Indonesia Email: 1,* jimmyalvanrey43@gmail.com, 2 ronsen@mikroskil.ac.id, 3 arwin@mikroskil.ac.id Penulis Email Korespondensi: jimmyalvanrey43@gmail.com
Abstrak −Penelitian  yang  dilakukan  ialah  Analisis  Perbandingan  Algoritma  ACO-TS  dan  ACO-SMARTER  dalam Menyelesaikan  Traveling  Salesman  Problem  dimana  masalah  yang  hendak  diselesaikan  adalah  masalah  pedagang  keliling (Travelling Salesman Problem, TSP). Tujuan penelitian ini adalah diharapkan mampu memberikan hasil perbandingan running time  dan  jarak  terpendek  antara  algoritma  ACO-TS  dan  algoritma  ACO-SMARTER  dalam  menyelesaikan  TSP.  Hasil pengujian diperoleh bahwa kombinasi algoritma Ant Colony Optimization (ACO) dan Tabu Search (TS) lebih baik dalam segi pencapaian  jalur  optimum  serta  running  time  dibandingkan  algoritma  ACO  dan  ACO-SMARTER  dalam  menyelesaikan permasalahan Traveling Salesman Problem. Algoritma Tabu Search pada algoritma ACO berperan sebagai pengontrol rute- rute yang sudah terpilih agar tidak diproses lagi pada semut yang sama. Hal ini tentu akan membuat algoritma ACO-TS lebih cepat dalam  memproses data karena tidak terdapat data  rute  yang  sama  pada  putaran selanjutnya,  dimana dari  200  dataset diperoleh running time pada ACO 11,5 detik dan jarak optimum 76687, ACO SMARTER 8,5 detik dan jarak optimum74496 sedangkan ACO-TS hanya membutuhkan waktu 2,9 detik dan jarak optimum 70558.
Kata Kunci : ACO; ACO-TS; ACO-SMARTER; TSP; Algoritma
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

## 1. PENDAHULUAN
Traveling Salesman Problem (TSP) merupakan permasalahan optimasi kombinatorial klasik serta memiliki peran dalam perencanaan, penjadwalan serta mencari pada bidang rekayasa dan pengetahuan[1]  Pencarian nilai yang optimal dapat dijumpai pada permasalahan di kehidupan sehari – hari, yaitu seperti: menentukan rute terpendek [2]menentukan jumlah optimal untuk persediaan hasil produksi  dan lain-lain. Permasalahan yang terdapat  pada TSP  yaitu  mengenai  seseorang  yang  harus  mengunjungi  semua  kota  tepat  satu  kali  dan  kembali  ke  kota  asal. Beberapa  contoh  penerapan  TSP  yang  muncul  dalam  kehidupan  sehari-hari,  misalnya  efisiensi  penjadwalan pengiriman koran, produksi barang, pemasangan jaringan komunikasi, dan masalah transportasi [3]
Terdapat beberapa algoritma yang dapat digunakan dalam menyelesaikan permasalahan TSP, salah satunya yaitu  algoritma  Ant  Colony  Optimization  (ACO).    Algoritma  ACO  dikenal  sebagai  algoritma  dengan  metode metaheuristik yang terinspirasi dari kecerdasan semut dalam pencarian jalur terpendek menuju sumber makanan [4] yang sering  digunakan dalam menyelesaikan  permasalahan TSP. Namun  dikarenakan algoritma ACO yang sangat kompleks, maka computation time yang dibutuhkan juga semakin tinggi [5]. Langkah kerja pada algoritma ACO yaitu semut akan berkeliling secara acak. Lalu ketika semut – semut menemukan jalur yang berbeda seperti menemukan persimpangan, semut – semut tersebut akan mulai menentukan arah jalan secara acak. Sebagian semut akan  memilih  berjalan  ke  arah  atas  lalu  sebagiannya  lagi  akan  berjalan  ke  arah  bawah.  Ketika  menemukan makanan, semut  –  semut tersebut  akan kembali ke koloninya sambal memberikan tanda dengan jejak feromon. Karena jalur yang ditempuh lewat jalur bawah lebih, maka semut yang berada di jalur bawah akan tiba lebih dahulu dengan asumsi kecepatan semua semut adalah sama. Jejak pheromone yang ditinggalkan oleh semut di jalur yang lebih pendek aromanya akan lebih kuat dibandingkan pheromone di jalur yang lebih panjang. Semut – semut lain akan lebih tertarik mengikuti jalur bawah karena aroma pheromone yang lebih kuat [6]. Salah satu algoritma yang memiliki kelebihan pada running time yang lebih singkat ialah Tabu Search (TS) . Algoritma ini dikemukakan pertama kali oleh Glover pada tahun 1986 [7] . Keunikan dari metode TS adalah adanya Tabu  List yang  fleksibel  sehingga  membedakan  algoritma  ini  dari  Algoritma Branch  and  Bound yang menggunakan struktur memori yang kaku dan simulated annealing yang tidak menggunakan struktur memori [8] . Menurut  penelitian  [7]  algoritma  Tabu  Search  dapat  mengoptimalkan  proses  pembelajaran  dengan menekan adanya bentrok jadwal, seperti adanya guru yang mengajar di kelas yang berbeda, tetapi di waktu yang

## JURNAL MEDIA INFORMATIKA BUDIDARMA
ISSN 2614-5278 (media cetak), ISSN 2548-8368 (media online) Available Online at https://ejurnal.stmik-budidarma.ac.id/index.php/mib DOI 10.30865/mib.v5i4.3283
sama, demikiab juga dengan penelitian [2] modifikasi Algoritma ACO dengan memberikan nilai secara otomatis terhadap  parameter  jumlah  semut  sebesar  35%  dari  ukuran  masalah,  terbukti  mampu  meningkatkan  kecepatan pencarian rute terpendek sebesar 3 kali dari kecepatan algoritma ACO yang asli. Sedangkan dari sisi pemakaian memori, modifikasi  ACO  terbukti  lebih  efisien  dengan  rata-rata  pemakaian  memori  93%  dari  Algoritma  ACO yang  asli,  dan  penelitian  [6]  menghasilkan    eksperimen  yang  menunjukkan  bahwa  ada  perubahan  heuristik menyebabkan  perubahan  efisiensi  algoritma  dan  kualitas  solusi  yang  diidentifikasi.  Heuristik  Ull  ternyata universal. Algoritma menggunakan heuristik tersebut telah memberikan hasil yang sangat baik terlepas dari ukuran masalah (organisasi kota). Algoritma yang menggunakan kombinasi dari dua heuristik pembaruan feromon global - BSF (rute terbaik-sejauh ini) dan IB (rute terbaik-iterasi) menunjukkan efektivitas tinggi. Saat mengoperasikan tidak  ada  metode  pembaruan  feromon  yang  memberikan  hasil  yang  memuaskan  serta  [9] Penelitian  terhadap Peningkatan  kinerja  ACO  yang  dipadukan  dengan  algoritma  SMARTER  dimana pembobotan  pada  metode SMARTER menggunakan range antara 0 sampai 1, sehingga mempermudah perhitungan dan perbandingan nilai pada masing-masing  alternative [10] , menyimpulkan bahwa ACO-SMARTER terbukti mengalami peningkatan sebesar 26.17%
Pada penelitian ini dilakukan perbandingan antara algoritma ACO- SMARTER dengan algoritma ACO dan algoritmaa  TS  untuk  mendapatkan running  time dan  jarak  yang  optimal,  dan  menentukan  kualitas  dari  suatu algoritma,  semakin  singkat running  time ,  maka  akan  semakin  baik,  namun  tetap  memperhatikan  kualitas  jalur optimal yang dihasilkan dari algoritma tersebut.

## 2. METODOLOGI PENELITIAN
Penelitian ini dilakukan agar dapat  melakukan analisa pada algoritma ACO yang telah dikombinasikan dengan algoritma lain yaitu ACO-TS dan ACO-SMARTER. Masalah yang hendak diselesaikan adalah masalah pencarian rute yang paling optimal pada perjalanan pedagang keliling ( Travelling Salesman Problem , TSP). Pada penelitian ini  diharapkan  akan  mendapatkan  kesimpulan  dari  analisa  algoritma  yang  terbaik  dalam  menyelesaikan  TSP. Dalam  hal  ini  yang  akan  dibandingkan  yaitu  running  time  dan  rute  optimal  yang  didapatkan  kedua  algoritma kombinasi tersebut
Data yang diolah pada penelitian ini berupa dataset TSP kota-kota yang diambil dari TSP dataset kroA200 yang  terdiri  dari  200  kota-kota    berupa  angka-angka  kordinat.  Langkah-langkah  dalam  menganalisa  optimasi algoritma Ant Colony Optimization (ACO) adalah sebagai berikut [11]: 1. Melakukan pencarian jarak terdekat dengan algoritma ACO.
2. Melakukan pencarian jarak terdekat dengan algoritma ACO-Tabu Search.
3. Melakukan pencarian jarak terdekat dengan algoritma ACO-SMARTER.
4. Melakukan  analisa  running  time  dan  jarak  optimal  antara  kedua  algoritma  kombinasi  agar  mendapatkan kesimpulan dari analisa algoritma yang terbaik dalam menyelesaikan TSP.
Hal pertama yang akan dilakukan yaitu mengumpulkan dataset sebanyak 200 kota. Lalu dataset tersebut akan  dilakukan  pengujian  menggunakan  algoritma  ACO-TS  dan  ACO-SMARTER.  Setelah  mendapatkan  hasil

## JURNAL MEDIA INFORMATIKA BUDIDARMA
ISSN 2614-5278 (media cetak), ISSN 2548-8368 (media online) Available Online at https://ejurnal.stmik-budidarma.ac.id/index.php/mib DOI 10.30865/mib.v5i4.3283
dari  masing-masing  algoritma  kombinasi,  maka  langkah  selanjutnya  ialah  membandingkan  hasil  yang  telah didapatkan dari algoritma kombinasi ACO-TS dan ACO-SMARTER. Lalu langkah terakhir yang akan dilakukan ialah menarik kesimpulan dari hasil yang telah dibandingkan.

## 2.1 Ant Colony Optimization (ACO)
Ant  colony  optimization  (ACO)  adalah  algoritme  yang  mengadopsi  kecerdasan  dari  sekelompok  semut  dalam pencarian  makanan  yang  mampu  meyelesaikan  permasalahan  M-TSP  [12],  ACO  menerapkan  metode penyelesaian masalah optimasi berdasarkan prinsip komunikasi antar koloni semut [13]. Adapun langkah-langkah dalam penyelesaian pencarian jarak yang optimal dengan menggunakan algoritma ACO yaitu [14]: 1. Input dataset rute TSP
2. Mengkonstruksikan  masalah  ke  dalam  sebuah  graph  G  =  (V,  E)  dengan  V  himpunan  verteks  yang merepresentasikan  himpunan  titik  –  titik,  dan  E  adalah  himpunan  dari  edge  yang  merepresentasikan  jarak antara dua titik.
3. Inisialisasi parameter awal yaitu α, β, ρ, τ0 = τij, Q, Ncmax.
4. Mengisi node pertama ke dalam tabu list.
5. Penyusunan rute kunjungan setiap semut ke setiap titik yang dilewati.
6. Mengunjungi  node  lain  yang  belum  ada  pada  tabu  list  berdasarkan  aturan  random  proportional  rule.  Node dengan probabilitas terbesar merupakan node yang akan dikunjungi. Kemudian mengisikan kunjungan tersebut pada tabu list.
7. Hitung probabilitas dan pheromone pada tabu list
8. Melakukan proses pembaharuan pheromone pada tiap jalur dan mengosongkan tabu list masing-masing semut.
9. Mengulang proses kelima sampai proses keenam dengan menggunakan pheromone hasil pembaharuan sebagai pheromone awal tiap ruas atau menghentikan proses jika NCmax sudah terpenuhi.
10. Kemudian tentukan tabu list dengan nilai terbaik yaitu tabu list dengan nilai probabilitas tertinggi.

## 2.2 Algoritma ACO-TS
Algoritma Tabu Search merupakan salah satu algoritma yang berada dalam  ruang lingkup metode heuristic [15]- [17]. Algoritma ini menggunakan short-term memory untuk menjaga agar proses pencarian tidak terjebak pada nilai optimum lokal. Algoritma ini menggunakan tabu  list untuk menyimpan sekumpulan solusi yang  baru saja dievaluasi. Perhitungan algoritma ACO-TS dalam pencarian rute terpendek pada persoalan TSP dari rute-rute pada dataset 1. Menghitung jarak antar kota sesuai dengan kordinat dataset dengan rumus:
d rs = √(𝑥 𝑟 − 𝑥 𝑠 ) 2 + (𝑦 𝑟 − 𝑦 𝑠 ) 2 (1)
2. Menghitung visibilitas antar node dengan rumus
Visibilitas ( Ƞ rs ) = 1 𝑑 𝑟𝑠
(2)
3. Menginisialisasi nilai parameter-parameter ACO : τij=0,01
q0=0,1 α (intensitas jejak semut) =1 β (visibilitas jejak semut) =1 m=4 ρ=0,5 Ncmax=1 4. Mencari probabilitas tertinggi dengan rumus [𝑇 𝑖𝑗 (𝑡)] 𝛼 [𝑛 𝑖𝑗 ] 𝛽 Ʃ[𝑇 𝑖𝑗 (𝑡)] 𝛼 [𝑛 𝑖𝑗 ] 𝛽 (3)

## 3. HASIL DAN PEMBAHASAN

## 3.1 Percarian Jarak Yang Optimum Dengan Algoritma ACO
Hasil yang diperoleh pada pencarian jarak yang optimum dengan menggunakan algoritma ACO pada persoalan TSP dengan dataset 200 kota menggunakan parameter yang digunakan oleh peneliti sebelumnya
a. Percobaan 1
Percobaan dilakukan dengan penambahan parameter semut yaitu Tetapan pengendali intensitas visibilitas (β) = 4 dan Tetapan pengendali pheromone (α) = 1. Hasil pencarian jarak antar kota dari Dataset 200 kota didapat dengan menggunakan persamaan no (1) hasil jarak antar kota dilihat pada matriks Jarak seperti pada Tabel

## JURNAL MEDIA INFORMATIKA BUDIDARMA
ISSN 2614-5278 (media cetak), ISSN 2548-8368 (media online) Available Online at https://ejurnal.stmik-budidarma.ac.id/index.php/mib DOI 10.30865/mib.v5i4.3283
Tabel 1 . Matriks Jarak Antar Kota
1         2           3            4            5            6             7            8             9            10           11         12         13 1      0      11.18      36.21    38.91      52.06     48.84      46.50     4 9.75     62.48      64.08      80.09    78.03    85.00 2   11.18         0      29.26    33.60      45.56     40.49      36.84    39.50       53.93      56.40      72.04    68.94    75.17 3   36.21    29.26         0      7.00        16.29     13.68      16.28    21.93       27.00      27.89      43.98    43.07    51.68 4   38.91    33.60     7.00         0         13.69     16.28      21.63    27.46       27.89      27.00      43.08    43.97     53.61 5   52.06    45.56    16.29    13.69        0          11.15      20.14    25.12       16.24      13.63      29.50    31.53     42.07 6   48.84    40.49    13.68    16.28      11.15       0           09.06    14.01       13.64      16.25      31.55    29.50     38.04 7   46.50    36.84    16.28    21.63      20.14      09.06        0         5.83        18.60      23.43      36.97    32.28     38.50 8   49.75    39.50    21.93    27.46      25.12      14.01      5.83         0          20.00      25.94      37.63    31.29     35.85 9   62.48    53.93    27.00    27.89      16.24      13.64     18.60      2.00         0             7.00      18.43    16.15     25.95 10   64.08   56.40     27.89    27.00      13.63      16.25      23.43    25.94       7.00          0          16.17    18.41    29.60 11   80.09   72.04     43.98    43.08      29.50      31.55      36.97    37.63      18.43      16.17       0          11.18    21.44 12   78.03   68.94     43.07    43.97      31.53      29.50      32.28    31.29      16.15      18.41      11.18       0        11.64 ……..   ……..   ……..  ……..    ………       …..        ……..   ……..     …….     ……..     ……..    ……   ..........
13  85.00    75.17    51.68    53.61       42.07     38.04      38.50     35.85      25.95      29.60      21.44     11.64         0

## Hasil matriks nilai visibilitas antar kota dapat dilihat pada tabel
Tabel 2 . Matriks Nilai Visibilitas Antar Kota
1           2           3           4             5            6           7            8            9           10          11        12          13 1      ∞ 0.09      0.03       0.03       0.02       0.02      0.02      0.02       0.02       0.02       0.01      0.01      0.01 2   0.09 ∞        0.03       0.03       0.02       0.02      0.03      0.03       0.02       0.02       0.01      0.01      0.01 3   0.03 0.03       ∞          0.14       0.06       0.07      0.06      0.05       0.04       0.04       0.02      0.02      0.02 4   0.03 0.03      0.14        ∞          0.07       0.06      0.05      0.04       0.04       0.04       0.02      0.02      0.02 5   0.02       0.02      0.06        0.07       ∞          0.09      0.05      0.04       0.06       0.07       0.03      0.03      0.02 6   0.02       0.02      0.07        0.06      0.09        ∞         0.11      0.07       0.07       0.06       0.03      0.03      0.03 7   0.02       0.03      0.06        0.05      0.05       0.11       ∞         0.17       0.05       0.04       0.03      0.03      0.03 8   0.02       0.03      0.05        0.04      0.04       0.07      0.17       ∞          0.05       0.04       0.03      0.03      0.03 9   0.02       0.02      0.04        0.04      0.06       0.07      0.05      0.05         ∞         0.14       0.05      0.06      0.04 10  0.02       0.02      0.04        0.04      0.07       0.06      0.04      0.04       0.14         ∞         0.06      0.05      0.03 11  0.01       0.01      0.02        0.02      0.03       0.03      0.03      0.03       0.05       0.06         ∞        0.09      0.05 12  0.01       0.01      0.02        0.02      0.03       0.03      0.03      0.03       0.06       0.05       0.09        ∞        0.09 ……..    ……..  ……..        ……..   ……       …..     ……..    ……..   …….     ……..    ……..    .......    ........ 13  0.01        0.01    0.02         0.02      0.02       0.03      0.03      0.03       0.04       0.03       0.05       0.09       ∞ Tabel 3 . Hasil Jarak Optimum ACO Percobaan-1 Siklus Jarak Optimum 1 88317 2 86028 3 82212 4 81084 5 76201 6 88156 7 75092 8 80129 9 86021 10 87435 11 86087 12 96619 13 95728 14 78270 15 86688 16 87062 17 89349 18 88547

## JURNAL MEDIA INFORMATIKA BUDIDARMA
ISSN 2614-5278 (media cetak), ISSN 2548-8368 (media online) Available Online at https://ejurnal.stmik-budidarma.ac.id/index.php/mib DOI 10.30865/mib.v5i4.3283
Siklus Jarak Optimum 19 80479 20 79127 21 92245 22 90788 23 95129 24 93807 25 89799 26 97704 27 87118 28 86684 29 85579 30 96132 Rata-rata 87120.53 Running Time 11.5 detik
b. Percobaan-2
Percobaan dilakukan dengan penambahan parameter semut yaitu Tetapan pengendali intensitas visibilitas (β) = 3 dan Tetapan pengendali pheromone (α) = 1. Hasil pencarian jarak antar kota dari Dataset 200-kota
Tabel 4. Hasil Jarak Optimum ACO Percobaan-2 Siklus Jarak Optimum 1 88317 2 86028 3 85212 4 78282 5 88201 6 88156 7 89092 8 88129 9 89021 10 91435 11 86087 12 90019 13 87728 14 86270 15 85688 16 87062 17 89349 18 90547 19 91479 20 92127 21 92245 22 92788 23 92129 24 87807 25 89799 26 91704 27 89118 28 86684 29 90579 30 86132 Rata-rata 88573.8 Running Time 11.5 detik
Dari tabel di atas diperoleh jarak yang paling optimum adalah pada Siklus ke 4 dengan jarak 78282 serta running  time  program  dari  pemrosesan  dataset  hingga  iterasi  30  dan  mendapatkan  jalur  optimum  selama  11.5 detik.

## 3.2. Hasil Pencarian Jarak Terdekat Algoritma ACO-TS
Pada percobaan 1, parameter semut yang digunakan adalah tetapan pengendali intensitas visibilitas (β) = 1 dan tetapan pengendali pheromone (α) = 1, jumlah Semut = 30, minimum error 0.15.

## JURNAL MEDIA INFORMATIKA BUDIDARMA
ISSN 2614-5278 (media cetak), ISSN 2548-8368 (media online) Available Online at https://ejurnal.stmik-budidarma.ac.id/index.php/mib DOI 10.30865/mib.v5i4.3283
Percobaan-1 Pada percobaan 1, parameter semut yang digunakan adalah tetapan pengendali intensitas visibilitas (β) = 1 dan tetapan pengendali pheromone (α) = 1, jumlah Semut = 30, minimum error 0.15. Hasil percobaan-1 algoritma ACO-TS diperoleh jarak optimum serta running time semua siklus
Tabel 5. Hasil Percobaan-1 ACO-TS 30 Siklus Siklus Jarak Optimum 1 195594 2 141305 3 114445 4 103522 5 92776 6 86884 7 87117 8 88974 9 81869 10 76773 11 83086 12 79222 13 81835 14 78836 15 78427 16 79982 17 79315 18 79071 19 77546 20 77977 21 77878 22 78802 23 71142 24 84254 25 76686 26 78071 27 80736 28 78508 29 80009 30 80267 Rata – Rata 88363.63 Running Time 2.9 detik
Percobaan-2
Pada percobaan ini dilakukan dengan penambahan parameter semut yaitu Tetapan pengendali intensitas visibilitas (β) = 3 dan Tetapan pengendali pheromone (α) = 3, jumlah Semut = 30, minimum error 0.15. Hasil percobaan-1 diperoleh jarak optimum serta running time semua siklus
Tabel 6. Hasil Percobaan-2 ACO-TS 30 Siklus Siklus Jarak Optimum 1 196702 2 115026 3 110501 4 106725 5 98825 6 87800 7 87029 8 88602 9 81652 10 77552 11 82828 12 76551 13 80581 14 76295

## JURNAL MEDIA INFORMATIKA BUDIDARMA
ISSN 2614-5278 (media cetak), ISSN 2548-8368 (media online) Available Online at https://ejurnal.stmik-budidarma.ac.id/index.php/mib DOI 10.30865/mib.v5i4.3283
Siklus Jarak Optimum 15 76282 16 79875 17 79890 18 79152 19 77192 20 69975 21 77108 22 78201 23 72717 24 84110 25 76401 26 78718 27 80905 28 78291 29 80031 30 81289 Rata-Rata 87226.87 Running Time 2.9 detik
Dari tabel diatas diperoleh jarak rata-rata yang paling optimum adalah sebesar 69975. Jarak yang paling optimum  adalah  pada  Siklus  20  ke  serta  running  time  program  dari  pemrosesan  dataset  hingga  iterasi  30  dan mendapatkan jalur optimum selama 2.9 detik. Adapun hasil percobaan untuk kedua algoritma dapat dilihat seperti pada tabel 7.
Tabel 7. Hasil Percobaan ACO No Algoritma Jarak Rata-rata Running Time Jarak Optimum 1 Percobaan-1 87120.53 11.5 75092 2 Percobaan-2 88573.8 11.5 78282 Rata-rata total 87847.17 76687 Tabel 8. Hasil Percobaan ACO-TABU SEARCH No Algoritma Jarak Rata-rata Running Time Jarak Optimum 1 Percobaan-1 88363.63 2.9 71142 2 Percobaan-2 87226.87 2.9 69975 Rata-rata total 87795.25 70558.5
Dari  data pada Tabel  diatas diperoleh jarak yang paling optimum dengan algoritma ACO sebesar 75092 dan jarak rata-rata total yang didapatkan ialah 87847.17 serta Running time sebesar [1] 15.5 detik pada percobaan 1. Hal ini membuktikan bahwa percobaan 1 pada algoritma ACO lebih baik  dibandingkan percobaan 2. Lalu pada algoritma Kombinasi (ACO-TABU SEARCH) , jarak optimum yang didapatkan ialah 69975  dan jarak rata-rata total 87795.25 serta rata-rata running time 2.9 detik pada percobaan 2. Hal ini membuktikan bahwa percobaan 2 pada algoritma ACO-TS lebih baik dibandingkan percobaan 1. Dikarenakan hasil jarak optimum yang didapatkan pada percobaan pertama dan kedua tidak sama, maka penulis mengambil nilai rata – rata jarak optimum sebagai acuan dari jarak optimum yang didapatkan .
3.3. Hasil PerbandinganAlgoritma Kombinasi ACO-TS dan ACO-SMARTER
Tabel 9. Hasil Penelitian Jarak Optimum Algoritma ACO, ACO-TS dan ACO-SMARTER
ACO ACO-SMARTER ACO-TS Dataset Jumlah Kota Jarak Optimum Rata – rata jarak optimum Jarak Optimum Rata – rata jarak optimum Jarak Optimum Rata –rata jarak optimum kroA200 200 75092 76687 72284 74496 69975 70558.5
Tabel 10. Hasil Penelitian Running Time Algoritma ACO, ACO-SMARTER dan ACO-TS ACO ACO-SMARTER ACO-TS Dataset Jumlah Kota Running Time Running Time Running Time kroA200 200 11.5 Detik 8.6 Detik 2.9 Detik
Berdasarkan  informasi  hasil  percobaan  diatas,  dibandingkan  dengan  algoritma  ACO-SMARTER  yang diteliti oleh Hafis (2020) maka dapat disimpulkan bahwa algoritma ACO-TS lebih baik dibandingkan ACO dan ACO-SMARTER  dari  segi  pencapaian  jalur  optimum  serta  running  time.  Hal  ini  disebabkan  karena  algoritma

## JURNAL MEDIA INFORMATIKA BUDIDARMA
ISSN 2614-5278 (media cetak), ISSN 2548-8368 (media online) Available Online at https://ejurnal.stmik-budidarma.ac.id/index.php/mib DOI 10.30865/mib.v5i4.3283
ACO-TS lebih cepat dalam memproses data karena tidak terdapat data rute yang sama pada tabu list di putaran selanjutnya.

## 4. KESIMPULAN
Dari  hasil  percobaan  yang  dilakukan  penulis  dengan  dataset  dan  spesifikasi  perangkat  keras  yang sama  bahwa kombinasi  algoritma Ant  Colony Optimization (ACO) dan Tabu Search (TS) lebih baik  dalam segi  pencapaian jalur  optimum  serta running  time dibandingkan  algoritma  ACO  dan  ACO-SMARTER  dalam  menyelesaikan permasalahan Traveling  Salesman  Problem .  Algoritma Tabu  Search pada  algoritma  ACO  berperan  sebagai pengontrol rute-rute yang sudah terpilih agar tidak diproses lagi pada semut yang sama. Hal ini tentu akan membuat algoritma ACO-TS lebih cepat dalam memproses data dengan running time 2.9 detik karena tidak terdapat data rute yang sama pada putaran selanjutnya.

## REFERENCES
[1]  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.
[2]  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.
[3]  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.
[4]  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.
[5]  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.
[6]  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.
[7]  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.
[8]  Y. Yunita, “Implementasi Metode Simple Multi-Attribute Rating Technique Exploiting Rank (SMARTER) Pada Sistem Pendukung Keputusan,” Kntia Unsri , vol. 4, pp. 57–60, 2017.
[9]  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
[10] 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.
[11] 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.
[12] 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.
[13] 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.
[14] 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.
[15] 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.
[16] Q. Li, W. Tu, and L. Zhuo, “Reliable Rescue Routing Optimization for Urban Emergency Logistics under Travel Time Uncertainty,” Int. J. Geo-Information , 2018.
[17] 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.