## IMPLEMENTASI ALGORITMA KOLONI SEMUT PADA TRAVELING SALESMAN PROBLEM MENGGUNAKAN MATLAB 7.8
MOLINA O. ODJA 1 , WENEFRIDA TULIT INA 2
1,2) Program Studi Teknik Elektro, Fakultas Sains dan Teknik, Universitas Nusa Cendana Jln.Adisucipto – Penfui, Telp. 03080-881597, Fax. 0380-881557 Email: molina.odja@staf.undana.ac.id, wenefrida_ina@staf.undana.ac.id
Info Artikel

## ABSTRACT
Histori Artikel: Diterima Mar 15, 2022 Direvisi Mar 20, 2022 Disetujui Mar 29,2022 Ant algorithm is a methodology generated through the observation of the ants. In the Ant algorithm, ants serve as an agent assigned to solve a problem in the shortest route. Ant algorithm has been applied in many fields, one of which is to see a solution in the search for the shortest route to the traveling Salesman Problem (TSP).
Research conducted Ant algorithm is to make an application to the determination of the shortest distances the coding Matlab program in the selection of the shortest route to help determine the shortest distance from a trajectory.
The test results showed Shortest Route Program applications using ant algorithm with alarge  value  of  Alpha=1.0;  Beta=1.0;  Rho=0.5andT-Beginning  =0:01with  city coordinates[10  0;  300;  15,20;  25,20;  1030;  30,30]  withthe  number  of  iterations  or 10cycles  to  obtain  the  path  length  of  the  shortest  path  length=1-3-5-6-4-2so  that  the shortest path is: 103.5917cm.
Effects of changes in the variation of the experiment Rho. Rho's smallest value obtained for 10 cycles or iterations with the shortest path length is103.5917. At Rho: 12:50 with a large average value of 3 times, the trial time calculation is: 3.815sec. Keywords: Ant Colony, Shortest Distance, Traveling Salesman Problem.

## ABSTRAK
Algoritma  semut  adalah  sebuah  metodologi  yang  dihasilkan  melalui  pengamatan terhadap semut. Pada Ant algorithm, semut berfungsi sebagai agen yang ditugaskan untuk  mencari  solusi  terhadap  suatu  masalah  rute  terpendek.  Ant  algorithm  telah diterapkan dalam berbagai bidang, salah satunya adalah untuk mencari solusi dalam pencarian rute terpendek pada Traveling Salesman Problem (TSP).
Penelitian ini bertujuan menentukan rute terpendek pada Traveling Salesman Problem (TSP) dengan program Matlab 7.8. Data yang digunakan berupa data koordinat kota yang dilalui Salesman yang terdiri dari 3 lintasan yaitu lintasan dengan  6 koordinat kota, lintasan dengan 10  koordinat kota dan lintasan dengan 15 koordinat kota. Hasil  pengujian  menunjukkan  aplikasi  Program  Rute  Terpendek  menggunakan Algoritma Semut dengan besar nilai Alfa = 1.0; Beta= 1.0; Rho=0.5 dan T-Awal=0.01 dengan Koordinat kota [10 0; 30 0; 15 20; 25 20; 10 30; 30 30] dengan jumlah iterasi atau siklus 10 didapat jalur untuk panjang jalur terpendeknya = 1-3-5-6-4-2 sehingga panjang  jalur terpendek adalah : 103.5917 cm. Pengaruh perubahan nilai Rho pada variasi percobaan didapat nilai Rho terkecil untuk total 10 siklus atau iterasi dengan panjang jalur terpendek 103.5917 adalah Pada  Rho: 0.50 dengan besar nilai  rerata dari 3 kali percobaan waktu perhitungan adalah : 3.815 detik.
Kata Kunci: Koloni Semut, Jarak terpendek, Traveling Salesman Problem.

## Penulis Korespondensi:
Wenefrida Tulit Ina, Program Studi Teknik Elektro Fakultas Sains dan Teknik, Universitas Nusa Cendana, Jl. Adi Sucipto Penfui - Kupang. Email: wenefrida_ina@staf.undana.ac.id

## 1. PENDAHULUAN
Algoritma  semut  telah  banyak  diterapkan  dalam permasalahan Traveling  Salesman  Problem (TSP) dan Graph Coloring (GC). Jika mengamati semut  dalam  dunia  nyata, semut  bergerak  secara acak  mencari  makanan  untuk  dibawa  pulang  ke sarang. Ketika pulang ke sarang dengan membawa makanan,  semut  menandai  jalur  pulanhgnya dengan hormone pheromone . Jika semut tersebut dapat  menemukan  jalur  terpendek  maka  semut- semut  yang  lain  akan  mengikuti  jalur  semut sebelumnya  karena  kadar pheromone yang diuapkan  oleh  semut  sebelumnya  lebih  tinggi, sebaliknya  jalur  yang  lebih  panjang  akan ditinggalkan, karena semut-semut berikutnya akan mengikuti  jalur  terpendek  yang  dilalui  semut sebelumnya.
Permasalahann Traveling  Salesman  Problem (TSP)  adalah  permasalahan  yang  dialami  oleh seorang salesman dalam mengunjungi semua kota tujuan dimana tiap kota hanya dikunjungi satu kali saja, dan memulai dari kota asal dan harus kembali lagi ke kota asal tersebut. Salesman tersebut harus meminimalkan jarak tempuh untuk perjalanannya. Penelitian  ini  lebih  difokuskan  pada  analisis pengaruh perubahan nilai jejak semut (Rho)
terhadap  efektivitas  pencarian  rute  terpendek. Untuk  mempermudah  analisis  tersebut  maka dibuat  suatu  aplikasi  sederhana  menggunakan program Matlab 7.8.

## 2. METODE PENELITIAN
Dalam  melaksanakan  penelitian  ini,  penulis menggunakan  beberapa  metode  yaitu  studi pustaka dan pembuatan aplikasi.
Metode-metode ini dilaksanakan dalam beberapa tahapan penelitian sebagai berikut:
1. Tahapan awal Pada  tahapan  ini  dilakukan  studi  pustaka untuk mengumpulkan referensi yang berhubungan  dengan Traveling  Salesman Problem (TSP) , algoritma  koloni  semut  dan materi mengenai matlab.
2. Tahapan pelaksanaan penelitian
a. Perhitungan manual terhadap jalur terpendek menggunakan algoritma koloni semut,  sebagai  bahan  patokan  untuk membuat aplikasi.
b. Pembuatan aplikasi
3. Tahapan akhir
Pada  tahapan  ini  dilakukan  pengujian  terhadap aplikasi yang telah dibuat. Rancangan Aplikasi Rute Terpendek diperlihatkan pada gambar 1 berikut.
Program Rute Terpendek M enggunakan Algoritma Semut Output SET Jalankan Input Alfa Beta Rho T Awal Koordinat Kota Hasil Jalur Panjang Jalur Iterasi Input Matriks dengan format [x y ; x y ; … ] Koordinat Kota
Gambar 1 Rancangan Aplikasi Rute Terpendek
Adapun  aplikasi  rute  terpendek  dimulai  dengan memasukan alamat tujuan kemudian menentukan parameter-parameter  berupa  jumlah  node,  jarak dan pheromone kemudian  memulai  tahapan- tahapan tiap semut berupa pemberian tanda jejak pheromone .  Alamat  yang  dipilih  adalah  alamat yang  berdasarkan  inputan  yang  telah  ditentukan. Pada  proses  selanjutnya  tiap-tiap  alamat  tujuan akan dikunjungi oleh semut apabila alamat tujuan yang  dikunjungi  belum  ditandai  maka  setiap
semut  akan  kembali  memilih  alamat  tujuan masing-masing, sehingga dari hasil pilihan alamat yang  dikunjungi  tersebut  dapat  dihitung  panjang perjalanan tiap-tiap semut  menuju alamat tempat tujuan (Alamat Tujuan), selanjutnya memperbaharui jejak pheromone atau tanda sesuai perjalanan  terbaik.  Apabila  jumlah  maksimum dari iterasi yang diberikan semut untuk melakukan tahapan  penentuan  rute  tercapai,  maka  akan ditampilkan  hasil  sesuai  rancangan,  dan  apabila
pada  iterasi  belum  mendapatkan  rute  tercepat, maka  iterasi  akan  dimulai  kembali  ke  tahapan awal  untuk  setiap  semut  sampai  rute  tercepat  di
dapatkan  sesuai  dengan  tujuan  alamat  yang dimaksud.
Algoritma Koloni Semut dapat digambarkan pada Diagram Alir berikut:
Ya Mulai Input Alamat Inisialisasi Parameter ( α), (β), (ρ), (t ij ) Jalankan Tahap Setiap Semut Pilih Alamat Berikutnya Untuk Setiap Semut Semua Dikunjungi Hitung Panjang Perjalanan Setiap Semut Iterasi Maksimum Tampilkan Hasil Selesai Ya Tidak Tidak
Gambar 2. Flow Chart Algoritma Koloni Semut

## 3. HASIL DAN PEMBAHASAN

## 3.1. Simulasi Aplikasi Rute Terpendek
Hasil pembuatan  Aplikasi Rute  Terpendek  dapat dilihat pada gambar 3 berikut:
Gambar 3. Aplikasi Rute Terpendek
Pada Aplikasi rute terpendek ini, dimasukkan nilai pada Alfa (α), Beta (β), Rho (ρ) dan nilai koordinat  pada  sumbu  X  dan  sumbu  Y  dimana pada kolom inputan koordinat yang di input
adalah  koordinat  antara  suatu  titik  ke  titik  yang lainnya
Aplikasi  ini  akan  mencari  rute  terpendek berdasarkan titik koordinat. Sedangkan untuk jalur  diketahui  titik  awal  sampai  pada  titik  akhir jalur yang di hasilkan.
Tampilan  Inputan  Data    seperti  pada  gambar  4 berikut:
Gambar 4. Tampilan Inputan Data pada Aplikasi
Ketika  Aplikasi  dijalankan,  maka  akan  tampak rute  yang  menghubungkan  koordinat-koordinat masukan, seperti pada gambar 5 berikut:
Gambar 5. Tampilan Semua Rute
Hasil  akhir  dari  pencarian  rute  terpendek berdasarkan masukan pada gambar 3 dapat dilihat pada gambar 6 berikut:
Gambar 6. hasil Inputan 6 koordinat.
• Perhitungan Jarak Terpendek.
Pada perhitungan jarak terpendek yang dilakukan berdasarkan koordinat-koordinat inputan dan hasil running aplikasi maka dapat dihitung menggunakan  rumus  panjang  jarak  antar  kota dengan Euclidean sehingga dengan hasil perhitungan tersebut dapat diketahui panjang jalur terpendek. Perhitungan panjang jalur menggunakan rumus sebagai berikut:
) ( 2 2 1 2 2 1 ) y y x x d rs − + − =
Besar  nilai  dari  titik-titik  di  atas  di  hitung  jarak antara koordinat antara titik 1 ke titik 3, titik 3 ke titik 5, titik 5 ke titik 6, titik 6 ke titik 4, titik 4 ke titik 2, titik 2 ke titik 1.
• L1=Titik 1 ke titik 3:
615 . 20 425 400 25 20 0 ( ) 15 10 ( ) 2 2
13 = = + = − + − = d
• L2=Titik 3 ke titik 5:
180 . 11 125 100 25 30 20 ( ) 10 5 ( ) 2 2
35 = = + = − + − = d
• L3=Titik 5 ke titik 6:
20 400 0 400 30 30 ( ) 30 10 ( ) 2 2 56 = = + = − + − = d
• L4=Titik 6 ke titik 4: 180 . 11 125 100 25 20 30 ( ) 25 30 ( ) 2 2 64 = = + = − + − = d • L5=Titik 4 ke titik 2: 615 . 20 425 400 25 0 20 ( ) 30 25 ( ) 2 2 42 = = + = − + − = d • L6=Titik 2 ke titik 1: 20 400 0 20 0 0 ( ) 10 30 ( ) 2 2 21 = = + = − + − = d Dari nilai Eucleadian diatas dapat dihitung jarak : L1 + L2 + L3 + L4 + L5 + L6  20.615 + 11.180 + 20 + 11.180 + 20.615 + 20 = 103.59 cm.
3.2.  Analisis Pengaruh Besar Nilai Rho ( ρ) Nilai  input  nilai  Alfa  (α)  dan  Beta  (β) menggunakan  nilai  input  sebesar  1  sedangkan variasi dilakukan pada input nilai Rho (ρ).

## • Percobaan Terhadap 6 Koordinat Kota
Hasil  percobaan  yang  dilakukan  terhadap  6 koordinat kota dapat dilihat pada tabel 1.

## Tabel 1 Percobaan Variasi Nilai Rho (ρ) Terhadap 6 Koordinat
Berdasarkan  Tabel  1  diketahui  bahwa dengan  variasi  nilai  Rho  (ρ)  dari  Rho  (ρ)  0.1 sampai pada nilai Rho (ρ) 1.0 di dapat nilai rerata dari  5  kali  percobaan  dengan  besar  rerata    nilai Rho  (ρ)  terendah  adalah  :  3.823  sampai    3.954 detik,  sehingga  dilihat  hasil  besar  nilai  Rho  (ρ) rerata terendah adalah pada Rho (ρ) = 0.5 dan nilai rerata Rho (ρ) tertinggi pada Rho (ρ) = 1.0. Dari rerata nilai yang didapat maka diambil nilai Rho (ρ) dengan waktu tercepat yakni pada Rho (ρ) = 0.5.
Perbandingan Rho (ρ) dengan perhitungan waktu adalah  :  3.823  detik  dengan  panjang  jalur terpendek adalah 103.5917 cm.
3.3.  Pengaruh  Perubahan  Parameter  Nilai Alfa, Beta dan Kombinasi Alfa dan Beta (-15) Pengaruh perubahan nilai parameter Alfa (α), Beta (β) dan kombinasi Alfa (α) Beta (β) dapat dilihat berdasarkan  hasil  rerata  dari  3  kali  percobaan running aplikasi Program rute terpendek Untuk 10 Koordinat Kota.
Prc. 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 3.863 3.846 3.818 3.929 3.827 3.866 3.863 4.284 3.834 4.052 2 3.86 3.862 3.826 3.83 3.806 3.823 4.045 3.833 3.824 4.108 3 3.818 3.831 3.83 3.815 3.841 3.797 3.849 3.821 4.205 3.83 4 3.846 4.006 3.948 3.856 3.83 3.858 3.873 3.842 3.837 3.892 5 3.911 3.863 3.865 3.865 3.812 3.891 3.888 3.857 3.893 3.891 Time 3.859 3.881 3.857 3.859 3.823 3.847 3.903 3.927 3.918 3.954 Jarak 103.5917 103.5917 103.592 103.5917 103.592 103.592 103.592 103.592 103.592 103.592
Tabel 2 Perubahan Parameter Nilai Alfa, Beta, dan Kombinasi Alfa dan Beta terhadap 10 Koordinat (Nilai Input Parameter = -15)
Tabel  2  adalah tabel  perubahan  parameter  dari 3 kali percobaan untuk melihat besar nilai panjang jalur ketika perubahan nilai Alfa (α) sebesar -15, begitupun nilai Beta (β) dan kombinasi nilai Alfa (α) dan Beta (β) sebesar -15.
Gambar 7. Grafik Percobaan Variasi Nilai Rho (ρ)

## Terhadap Waktu untuk 6 Koordinat
Berdasarkan  analisis  Tabel  2  maka  di  buatkan hasil perubahan nilai Rho (ρ)  dalam bentuk grafik Variasi  Nilai  Rho  (ρ)  sesuai  dengan  Gambar  7 Perbandingan Rho (ρ) dengan perhitungan waktu adalah  :  3.823  detik  dengan  panjang  jalur terpendek adalah 103.5917 cm.
Gambar 8. Grafik Perbandingan Panjang Terhadap Variasi Nilai Parameter (Nilai Input Parameter = -15) untuk 10 Koordinat
Perbandingan  panjang  jalur  terpendek  dengan variasi nilai parameter -15 sesuai dengan Gambar 8 dapat diketahui bahwa besar ketika inputan nilai Alfa (α) = -15 didapat nilai panjang jalur sebesar: 138.46  cm.  Untuk  inputan  nilai  Beta  (β)  =  -15 didapat  panjang  jalur  sebesar  234.49  cm sedangkan  kombinasi  Alfa  (α)  dan  Beta  (β) didapatkan hasil: 172.99 cm.

## 4. KESIMPULAN
1. Hasil  aplikasi  Program  Rute  Terpendek Menggunakan  Algoritma  Semut  pada  6 titik koordinat dengan perhitungan waktu tercepat  yaitu  pada  Rho  =  0.5  adalah  : 3.815  detik  sedangkan  pada  10  titik koordinat  Perhitungan  waktu  tercepat pada Rho = 0.2 dengan besar nilai waktu adalah  4.3265  detik  dan  untuk  15 koordinat  didapat  waktu  tercepat  adalah 5.6027 detik.
2. Nilai  Input  Alfa  dan  Beta  <  0  dan  >1 berpengaruh pada Jarak, panjang jalur dan waktu perhitungan.
3. Aplikasi Program Rute Terpendek Menggunakan  Algoritma  Semut  berjalan dengan baik

## DAFTAR PUSTAKA
[1] Diana  Fallo,  “Pencarian  Jalur  Terpendek Menggunakan  Algoritma  Colony  Optimi- zation”, Jurnal JUKANTI, Vol.1 No.1, Maret 2018
[2] Guardio Eraniola, Endang Suhen- dar,”Menentukan Rute Kendaraan PT. Sarana Cahaya  Makmur  Dengan  Metode  Algoritma Ant  Colony  Optimization ”,Jurnal  IKRA-ITH TEKNOLOGI, Vol.5. No.1, Maret 2021 .
[3] Karjono, Moedjiono, Denni Kurniawan," Ant Colony  Optimization ",  Jurnal  TICOM,  Vol.4 No.3, mei 2016.
[4]  Sugiarto Cokrowibowo, Ismail, Indra, “Multi- ple  Teaveling  Salesman  Problem  Meng- gunakan  Algoritma  Ant  Colony  Optimization dengan  Operasi  Elitism”,  Jurnal  JCIS,  Vol1 Issue  2,  Okrober  2019,  Hal  :  23-28.  ISSN (print)  :  2622-5859,  ISSN  (online)  ;  2622- 0881.
[5] WenefridaT. Ina, Sarlince Manu, Thomas M,” Penerapan Algoritma Genetika Pada Traveling Salesman  Problem  (Studi  Kasus  Pedagang Perabot keliling”, Jurnal Media Elektro, Vol. 8 No.1. April 2019. ISSN : 2252-6692.
[6]  Euis  Nurlaelasari,  Supriyadi,  U.T.  lengga- na,”Penerapan Algoritma Ant Colony
Optimization  Menentukan  Nilai  Optimal  Da- lam memilih Objek Wisata berbasis Android”, Jurnal  SIMETRIS,  Vol.9  No.1,  April  2018. ISSN : 2252-4983, Hal : 287- 298
[7] Lutfi E. Prasetyo, Istiadi, Fitri Marisa, “Sistem Optimasi Pendistribusian Bahan Makanan dan Snack dengan Algoritma Ant Colony Optimization  (ACO)”,  Jurnal  AITI  ,  Vol.  18
Percobaan Panjang Jalur Waktu (detik) Panjang Jalur Waktu (detik) Panjang Jalur Waktu (detik) 1 141.635 4.4471 238.2304 4.7413 167.6134 4.3545 2 144.685 4.3454 223.0764 4.3055 170.6081 4.6746 3 129.069 4.3646 242.1758 4.374 180.7712 4.6525 138.462 4.3857 234.4942 4.4736 172.9975 4.5605
Alfa (-15) Beta (-15) Alfa dan Beta (-15)
0. 1 0. 2 0. 3 0. 4 0. 5 0. 6 0. 7 0. 8 0. 9 1 waktu 3.9 3.9 3.9 3.9 3.8 3.8 3.9 3.9 3.9 4 3.6 3.8 4 Waktu Perbandingan Rho Terhadap Perhitungan Waktu
No.1,  Februari  2021.  ISSN  :  1693-8348.  E- ISSN : 2615-7128
[8] Kristiawan Nugroho, “Penggunaan Algoritma semut  untuk  penentuan  Optimisasi  Jalur  TIM Marketing”,  Jurnal  INFOKAM,  No.  II, September 2015. Hal: 92 – 95.
[9] Deny W. Nugraha, Albecht Y.E. Dodu, Stevi Septiana,  “Sistem  Penentuan  Rute  Pendistri- busian Produk air mineral menggunakan Algo-
ritma ant Colont System”, Jurnal Terakreditasi ILKOM, Vol.11 No.2, Agustus 2019, p-ISSN : 2087-1716, e-ISSN : 2548-7779. Hal : 86-94
[10]  Rini  Amalia,  “  Pencarian  Jalur  Terpendek Menggunakan  Ant  Colony  System  (Kasus: Pariwisata Kota Bogor)”, Jurnal Faktor Exacta vol.8 No.4, 2015. Hal : 290-304. ISSN : 1979- 276X.