## Penerapan Algoritma Ant Colony Optimization (ACO) Rute Jalur Terpendek (Studi Kasus Distribusi Barang JNE Wilayah Bumi Tamalanrea Permai (BTP))

## Siti Nurhalisa Jumaedi
Mahasiswa Program Studi Matematika, Universitas Islam Negeri Alauddin Makassar, snurhalisajumaedi@gmail.com

## Wahyuni Abidin
Program Studi Matematika, FST, Universitas Islam Negeri Alauddin Makassar, wahyuniabidin@uin-alauddin.ac.id

## Try Azisah Nurman
Program Studi Matematika, FST, Universitas Islam Negeri Alauddin Makassar, try.azisah@uin-alauddin.ac.id
ABSTRAK ,  Pendistribusian  barang  dari  produsen  ke konsumen  dilakukan  oleh  jasa  kurir.  Seorang  kurir diharapkan  mampu  mengantarkan  paket  kiriman  dengan mempertimbangkan  estimasi  penghematan  waktu  dan jarak  tempuh,  sehingga  mendukung  pekerjaannya  lebih efektif  dan  cepat  tentunya  menghemat  biaya  perjalanan. Pada  umumnya  pencarian  jalur  terpendek  menjadi  solusi yang  diberikan.  Pencarian  lintasan  terpendek  dibagi menjadi  dua  metode,  yaitu  metode  konvensional  dan metode heuristik. Pada metode heuristik terdapat beberapa algoritma,  salah  satunya  adalah  algoritma Ant  Colony Optimization .  Algoritma  ini  didasarkan  pada  perilaku semut.  Secara  alamiah,  koloni  semut  dapat  menemukan rute  terpendek  dalam  perjalanan  dari  sarang  ke  tempat sumber  makanan.  Koloni  semut  dapat  menemukan  rute terpendek antara sarang dan sumber makanan berdasarkan jejak kaki pada jalur yang dilalui. Semakin banyak semut yang melewati sebuah jalur, semakin jelas jejak kaki yang ada.  Algoritma  ini  sangat  cocok  digunakan  untuk menyelesaikan  masalah  optimasi,  salah  satunya  adalah menentukan jalur terpendek. Penelitian ini bertujuan untuk memudahkan  kurir  untuk  mengambil  keputusan  dalam menentukan lokasi jalur yang akan dilalui. Terdapat enam jumlah  lokasi  yang  digunakan.  Pada  situasi  ini, penggunaan  algoritma ant  colony  optimization terbatas pada  satu  siklus  atau  satu  iterasi  (NC=1),  sehingga  rute terbaik diperoleh sementara siklus pertama yaitu GOR Prof Tahir Djide ( 𝑣 3 ) menuju Panti Asuhan Al Muhtadina ( 𝑣 2 ) menuju  Rumah  Yatim  Makassar  ( 𝑣 1 )  menuju  Lapangan Tala  BTP/GLT  ( 𝑣 4 )  menuju  Rusunawa  Kodam  XIV/Hsn ( 𝑣 5 )  menuju  Pabrik  Produksi  Roti  Tawar  Bandung Makassar ( 𝑣 6 ) lalu kembali pada titik pertama GOR Prof Tahir Djide ( 𝑣 3 ) dengan jarak tempuh sepanjang 10,6 km. ( 𝑣 3 → 𝑣 2 → 𝑣 1 → 𝑣 4 → 𝑣 5 → 𝑣 6 → 𝑣 3 ).
Kata  Kunci: Teori  Graf,  Algoritma Ant  Colony Optimization, Rute Jalur Terpendek

## 1. PENDAHULUAN
Sebuah  proses  distribusi  barang  dari produsen ke konsumen yang dilakukan oleh jasa kurir  merupakan  salah  satu  bentuk  pelayanan publik  yang  memfasilitasi  pengangkutan  suatu barang dari satu daerah ke daerah lain dan dapat dikenakan  biaya  oleh  pihak  jasa.  Pengiriman
barang  dapat  berupa  dokumen,  logistik,  produk elektronik, dan lain-lain.
Setiap  pengiriman  jasa  ekspedisi  dinilai berdasarkan  ketepatan  waktu  dan  jarak  tempuh yang harus dilalui oleh kurir. Masalah pada jasa kurir terkait dengan kemungkinan urutan alamat dalam  pengiriman  paket.  Ketika  seorang  kurir mengirimkan  paket,  pengirim  harus  memenuhi waktu  yang  sangat  singkat,  sehingga  seorang kurir  akan  menentukan  rute  terpendek  dengan mempertimbangkan estimasi penghematan waktu  dalam  mendukung  pekerjaannya  lebih efektif  dan  cepat  yang  tentunya  menghemat biaya perjalanan [8].
Rute jalur terpendek bisa dikatakan sebagai nilai minimum dari suatu lintasan. Permasalahan yang dihadapi dalam menentukan jalur terpendek yakni banyaknya rute yang mungkin dipilih dari tempat  keberangkatan  menuju  tempat  tujuan akhir  [4].  Dalam  ilmu  matematika  diskrit,  graf dapat digunakan untuk menunjukkan jarak antar kota atau tempat.
Sekumpulan  dari  objek  titik  ( vertex atau node ) kemudian dihubungkan dengan sisi ( edge ) atau  busur  ( arc )  yang  disebut  graf.  Setiap  sisi yang  berkaitan  dalam  satu  atau  dua  titik merupakan titik ujung dari sisi tersebut. Struktur graf  dapat  dikembangkan  dengan  memberikan bobot  dalam  tiap  sisinya.  Dalam  hal  ini  dapat membantu menghitung panjang sisi atau lintasan.
Menentukan rute jalur terpendek memiliki beberapa cara untuk menyelesaikannya. Menurut I’ing mutakhiro, dkk pada tahun 2007 di dalam papernya  bahwa  dalam  menentukan  rute  jalur terpendek  menggunakan  algoritma ant  colony optimization tepat  digunakan  untuk  diterapkan dalam  penyelesaian  masalah  optimasi.  Prinsip algoritma didasarkan pada perilaku koloni semut dalam  menentukan  jarak  perjalanan  paling
pendek [7]. Salah satunya dengan menggunakan metode  heuristik.  Metode  heuristik  salah  satu metode  untuk  mencari  rute  jalur  terpendek. Metode heuristik diaplikasikan dengan memperhitungkan dan menentukan dasar pengetahuan.  Pemanfaatan  metode  heuristik diharapkan  dapat  menyelesaikan  permasalahan pencarian rute jalur terpendek dengan hasil yang lebih beragam dan waktu perhitungan yang lebih singkat.
Pada  algoritma ant  colony  optimization adaptasi dari hewan semut, dimana semut dapat beradaptasi  dengan  perubahan  lingkungan. Sehingga pada kondisi situasi dimana jalan atau permintaan  pelanggan  dapat  berubah  seiring waktu,  hal  ini  dapat  menjadi  solusi  dari permasalahan  distribusi  barang  jasa  ekspedisi JNE. Setiap semut akan ditempatkan pada semua titik yang kemudian akan bergerak mengunjungi semua  titik-titik  yang  telah  ditentukan.  Tujuan dari penggunaan algoritma ant colony optimization untuk meminimalisir waktu, tenaga, dan biaya yang akan digunakan. Penentuan jarak antar lokasi akan menggunakan bantuan aplikasi google  maps, sedangkan  penentuan  rute  jalur terpendek  akan  memberikan  nilai  solusi  yang mendekati  optimum,  yaitu  nilai  yang  diperoleh melalui  suatu  proses  dan  dipertimbangkan sebagai  solusi  jawaban  terbaik  dari  semua  titik lokasi yang ada. Titik-titik lokasi yang digunakan sebagai  titik  kunjungan  akan  menghasilkan sebuah graf yang lengkap.

## 2. TINJAUAN PUSTAKA

## Teori Graf
Graf  adalah  sepasang  himpunan  dimana titik-titik dari graf tersebut dapat mempresentasikan  berbagai  objek  seperti  kota, atom-atom  dari  suatu  zat,  komponen  perangkat elektronik,  nama-nama  objek  dan  sebagainya [10].  Sebuah graf G berisi dua bentuk himpunan [3]:
a. Himpunan 𝑉(𝐺) =   {𝑣 1 , 𝑣 2 , … , 𝑣 𝑛 } adalah mempunyai  elemen-elemen  yang  disebut titik . b. Himpunan 𝐸(𝐺) = {𝑒 1 , 𝑒 2 , … , 𝑒 𝑛 } adalah pasangan terurut dari titik-titik yang berbeda yang disebut sisi.
Rute Jalur Terpendek (Shortest Path Problem) Rute  jalur  terpendek  adalah  sebuah jaringan  arah  perjalanan  di  mana  seorang pengarah  jalan  memilih  jalur  terpendek  antara dua  kota,  berdasarkan  jumlah  jalur  alternatif yang  tersedia.  Jalur  terpendek  adalah  rute perjalanan di mana rute yang dilalui adalah rute yang  memiliki  jarak  terpendek  dibandingkan dengan rute-rute lainnya [9].
Secara umum, ada dua metode yang dapat digunakan untuk menyelesaikan masalah pencarian  rute  jalur  terpendek  yaitu  metode algoritma konvensional dan metode heuristik [6]. a. Metode  konvensional  adalah  algoritma  yang menggunakan  perhitungan  matematika  biasa dan  cenderung  menghasilkan  solusi  optimal dengan  mengikuti  langkah  yang  telah terdefinisi. Algoritma seperti Djikstra, Floyd- Warshall, dan Bellman-Ford adalah beberapa metode  konvensional  yang  biasa  digunakan untuk mencari jalur terpendek.
b. Metode  heuristik  adalah  perhitungan  yang menghasilkan solusi alternatif untuk menemukan  jalur  terpendek  dan  berfokus dalam menemukan solusi yang memadai atau mendekati  solusi  optimal.  Ada  beberapa algoritma  dalam  heuristik  yang  biasa digunakan  dalam  mencari  jalur  terpendek. Salah  satunya  adalah  algoritma ant  colony optimization .

## Ant Colony Optimization (ACO)
Ant  Colony  Optimization (ACO)  adalah metode  penyelesaian  masalah  optimasi  yang terdiri  dari  berbagai  algoritma  yang  bekerja berdasarkan  prinsip  komunikasi  koloni  semut dan teknik probabilistik untuk mencari makanan. Koloni  semut  menggunakan  sistem  komunikasi untuk  menemukan  sumber  makanan  dan meninggalkan  bahan  kimia  yang  disebut pheromone di  jalan  mereka.  Semut  yang menemuukan sumber makanan akan meninggalkan pheromone di  jalan  mereka kembali ke koloni mereka, dan semut lain yang menemukan  bau pheromone di  suatu  rute cenderung mengikuti rute tersebut jika kandungan pheromone cukup pekat [5]. Seiring berjalannya  waktu, pheromone akan  menguap [1].  Rute  yang  pendek  hanya  membutuhkan waktu  singkat  (semut  selalu  meninggalkan
pheromone setiap  kali  mereka  kembali  ke koloninya)  untuk  pergi  dari  koloni  ke  sumber makanan, pheromone lebih  cepat  menguap. Banyak  semut  akan  melewati  rute  dengan kepadatan  semut  yang  lebih  tinggi,  jika  tidak semua semut melewatinya [2].
Gambar 2.1 Jalur lintasan dua kelompok semut
Gambar  2.1  menunjukkan  dua  kelompok semut  bergerak.  Satu  kelompok  dinamakan  L berada  di  sebelah  kiri  untuk  sarang  semut,  dan kelompok  lain  dinamakan  R  berada  di  sebelah kanan untuk sumber makanan. Setiap kelompok semut  dari  titik  awal  dapat  memilih  sisi  jalan mana  yang  akan  diambil.  Kelompok  semut  L terbagi  menjadi  dua  kelompok  lagi.  Sebagian semut memilih jalan bawah, sedangkan yang lain memilih  jalan  atas.  Karena  jumlah  semut  yang bergerak  ke  atas  lebih  sedikit  daripada  yang bergerak  ke  bawah,  kelompok  semut  yang bergerak ke atas bergerak dengan kecepatan yang sama  dan  meninggalkan  jejak  kaki  atau pheromone di  tanah  yang  mereka  lalui. Pheromone yang  ditinggalkan  kelompok  semut ini  menguap  secara  signifikan  seperti  yang ditunjukkan  pada  Gambar  2.1  Ini  disebabkan oleh  jarak  yang  ditempuh  lebih  jauh  daripada jalur  yang  lebih  pendek.  Sementara  itu,  karena lebih  banyak  semut  berjalan  di  jalur  bawah daripada  di  jalur  atas, pheromone di  jalur  yang lebih rendah menguap membutuhkan waktu lebih lama, seperti yang ditunjukkan pada Gambar 2.1 Semut-semut  lain  pada  akhirnya  memutuskan untuk mengambil jalur yang lebih rendah karena lebih  banyak pheromone yang  tersisa  di  jalur atas,  tetapi pheromone di  jalur  atas  telah menguap,  sehingga  semut  tidak  memilih  jalur atas.  Oleh  karena  itu,  rute  terpendek  antara sarang dan sumber makanan dipilih.
Untuk  dapat  mengetahui  implementasi algoritma  semut  dalam  menentukan  rute terpendek,  diperlukan  variabel  dan  langkah- langkah, yaitu:
Langkah 1 a. Menginisialisasi nilai awal parameter algoritma Adapun parameter-patameter yang diinisialisasikan sebagai berikut: 1. Intensitas  jalur  semut  antar  kota  serta perubahannya ( 𝜏 𝑖𝑗 ).
2. Termasuk dalam jumlah kota ( n ) termasuk koordinat  ( x,y )  atau  jarak  antar  kota i ke kota lainnya ( 𝑑 𝑖𝑗 ).
3. Kota berangkat dan kota tujuan.
4. Laju siklus semut ( Q ).
5. Setel pengontrol intensitas jalur semut (α), nilai α ≥ 0.
6. Atur pengontrol visibilitas (β), nilai β ≥ 0.
7. Visibilitas antar kota = 1 𝑑 𝑖𝑗 𝜂 𝑖𝑗 . 8. Jumlah semut ( k ).
9. Atur  penguapan  jalur  semut  ( ρ ),  nilai ρ harus > 0 dan < 1 untuk menghindar jalur semut yang tak terbatas.
10. Jumlah  siklus  maksimum  ( NCmax )  tetap selama  algoritma  berjalan,  sedangkan 𝑑 𝑖𝑗 akan  selalu  diperbaharui  setiap  siklus algoritma,  mulai  dari  siklus  pertama  ( NC = 1)  sampai  jumlah  maksimum  siklus tercapai  ( NC  =  NCmax )  atau  sampai algoritma konvergensi.
b. Inisialisasi kota pertama dari setiap semut. Setelah inisialisasi 𝜏 𝑖𝑗 dilakukan, kemudian k semut ditempatkan secara acak pada kota pertama yang diberikan.

## Langkah 2
Masukkan  kota  pertama  ke  dalam  daftar tab  atau tabu  list .  Kota  yang  diinisialisasikan pertama  kali  oleh  setiap  semut  pada  langkah pertama  harus  dimasukkan  sebagai  elemen pertama  dari  daftar  tab  atau tabu  list . Selanjutnya, langkah ini mengisi elemen pertama dari  daftar  tab  setiap  semut  dengan  indeks  kota tertentu, yang berarti bahwa setiap tabu k dapat berisi indeks kota antara 1 sampai n , seperti yang diinisialisasikan pada langkah 1.

## Langkah 3
Setiap semut harus dibawa ke setiap kota. Koloni semut yang terbagi dalam beberapa kota. Koloni semut memulai dari kota pertama sebagai kota  lainnya  sebagai  kota  tujuan.  Dari  kota kedua,  koloni  semut  memilih  salah  satu  kota yang tidak dituju sebagai kota tujuan berikutnya. Begitu  pun  untuk  selanjutnya,  koloni  semut melakukan  perjalanan  terus  menerus  hingga semua kota dikunjungi satu per satu atau k kota tabu ditempati. Dalam kasus di mana N sebagai seluruh rute perjalanan dan 𝑡𝑎𝑏𝑢 𝑘 sebagai daftar perjalanan  yang sudah dilewati agar para semut tidak  melewati  jalan  yang  berulang,  sehingga 𝐾 ′ adalah indeks urutan kunjungan dan kota asal disebut  sebagai  {N- 𝑡𝑎𝑏𝑢 𝑘 },  maka  untuk menentukan  kota  tujuan  digunakan  persamaan probabilitas  sebuah  kota  yang  akan  dikunjungi adalah sebagai berikut:
𝑃 𝑖𝑗 𝑘 = { [𝜏 𝑖𝑗 ] 𝛼 [𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏 𝑖𝐾′ ] 𝛼 [𝜏 𝑖𝐾′ ] 𝛽 , untuk 𝑗  ∈ {𝑁 − 𝑡𝑎𝑏𝑢 𝑘 }
0                     , untuk 𝑗 lainnya (2.1)
Langkah 4 a. Menghitung panjang rute jalur setiap semut Menghitung  berapa  panjang  jalur  rute tertutup  atau 𝐿 𝑘 untuk  setiap  semut  dilakukan setelah  semua  menyelesaikan  satu  siklus. Perhitungan  ini  dilakukan  untuk  setiap  semut dengan menggunakan persamaan berikut:
𝐿 𝑘 =   𝑑 𝑡𝑎𝑏𝑢 𝑘 (𝑛),𝑡𝑎𝑏𝑢 𝑘 (1) + ∑ 𝑑 𝑡𝑎𝑏𝑢 𝑘 (𝑠),𝑡𝑎𝑏𝑢 𝑘 (𝑠+1) 𝑛−1 𝑠=1 (2.2)
b. Pencarian rute terpendek.
Setelah menghitung 𝐿 𝑘 untuk setiap semut, harga  minimum  dari  panjang  rute  setiap  siklus, atau 𝐿 𝑚𝑖𝑛𝑁𝐶 akan  diperoleh,  dan 𝐿 𝑚𝑖𝑛 adalah harga minimum tertutup secara keseluruhan.
c. Menghitung perubahan biaya intensitas jejak kaki semut antara kota-kota.
Koloni  semut  akan  meninggalkan  jejak kaki  di  jalur  antar  kota.  Harga  intensitas  jejak kaki antar kota dapat berubah karena penguapan dan perbedaan jumlah semut yang melewatinya. Persamaan  yang  terkait  dengan  perubahan  ini adalah sebagai berikut:
∆𝜏 𝑖𝑗 =   ∑ ∆𝜏 𝑖𝑗 𝑘 𝑚 𝑘=1 (2.3)
dengan ∆𝜏 𝑖𝑗 adalah perubahan harga intensitas jejak kaki semut antar kota untuk setiap semut yang dihitung dengan persamaan berikut:
∆𝜏 𝑖𝑗 = { 𝑄 𝐿 𝑘 , jika (𝑖, 𝑗) ∈  kota asal dan kota tujuan dalam 𝑡𝑎𝑏𝑢 𝑘 0,  jika (𝑖, 𝑗) lainnya (2.4)

## Langkah 5
a. Menghitung  harga  intensitas  jejak  kaki semut  antar  kota  untuk  per  siklus.  Karena penguapan  dan  perbedaan 𝑚 jumlah  semut yang melewati jalur tertentu, harga intensitas jejak kaki semut antar kota mungkin berubah untuk  setiap  jalur  antar  kota.  Untuk mengetahui  harga  intensitas  jalur  semut antar  kota  ( 𝜏 𝑖𝑗 )  untuk  siklus  berikutnya, persamaan berikut digunakan:
𝜏 𝑖𝑗 =   𝜌. 𝜏 𝑖𝑗 +   ∆𝜏 𝑖𝑗 (2.5) b. Mengatur  ulang  setiap  siklus,  harga perubahan intensitas jejak kaki semut antar kota diatur ulang k nol.

## Langkah 6
Kosongkan  daftar  tabulasi  dan  ulangi langkah 2. Jika jumlah maksimum siklus belum tercapai,  pada  siklus  berikutnya,  daftar  tabulasi harus diisi ulang dengan urutan kota yang baru. Jika  konvergensi  tidak  terjadi  atau  jumlah maksimum  siklus  belum  tercapai.  Algoritma diulangi dari langkah 2 dengan harga parameter intensitas jalur semut kota yang diperbarui.

## 3. METODOLOGI
Penelitian ini menggunakan metode kuantitatif,  dengan  memanfaatkan  data  primer dan  sekunder.  Data  primer  diperoleh  dari  hasil penelitian melalui Google Maps dan wawancara, sedangkan data sekunder diperoleh dari berbagai literatur seperti internet,  jurnal online, dan lain- lain.  Pada  praktiknya,  sistem  ini  tidak mempertimbangkan kondisi jalan seperti kepadatan  kendaraan  lalu  lintas,  atau  masalah lain  yang  mungkin  ada  pada  jalur  tersebut. Semua  jalur  dianggap  dalam  kondisi  normal tanpa hambatan.
Variabel  yang  digunakan  pada  penelitian ini  meliputi  Titik  ( 𝑉 )  merepresentasikan  lokasi tujuan dan Sisi ( 𝐸 ) merepresentasikan jarak dari
lintasan  yang  ditempuh  antar  lokasi  atau  titik tujuan.
4. PEMBAHASAN
1) Inisialisasi
parameter-parameter algoritma dan penentuan tiap titik lokasi. Tabel 4.1 Parameter Algoritma Parameter Nilai α 1,0 β 1,0 ρ 0,1 𝑘 6
Gambar 4.1 Peta 6 Titik lokasi tujuan
Penginisialisasian tempat antara lain: 𝑣 1 ∶ Rumah Yatim Makassar 𝑣 2 ∶ Panti Asuhan Al Muhtadina 𝑣 3 ∶ GOR Prof Tahir Djide 𝑣 4 ∶ Lapangan Tala BTP/GLT 𝑣 5 ∶ Rusunawa Kodam XIV/Hsn 𝑣 6 ∶ Pabrik  Produksi  Roti  Tawar  Bandung Makassar

## 2) Menentukan  jarak  awal  yang  akan ditempuh masing-masing titik
Berdasarkan  data  yang  diperoleh  dalam pengambilan dari hasil pencarian dengan bantuan alat penunjuk arah pada google maps, maka jarak tempuh  (km)  dari  masing-masing  titik  dapat disusun dalam tabel sebagai berikut:
Tabel 4.2 Jarak tempuh masing-masing lokasi Titik 𝑣 1 𝑣 2 𝑣 3 𝑣 4 𝑣 5 𝑣 6 𝑣 1 0 2,2 1,9 1,4 2,4 3,3
𝑣 2 2,2 0 1,1 2,2 2,1 3,8 𝑣 3 1,9 1,1 0 1,9 2,1 2,7 𝑣 4 1,4 2,2 1,9 0 1,3 2,1 𝑣 5 2,4 2,1 2,1 1,3 0 1,9 𝑣 6 3,3 3,8 2,7 2,1 1,9 0 3) Penyusunan  jalur  kunjungan  ke  setiap titik
Memilih  titik  awal  yaitu  titik 𝑣 1 ,  hingga memilih  langkah  selanjutnya  yang  memilliki jarak  yang  terpendek  maka  didapatkan  hasil 𝑣 1 → 𝑣 4 →   𝑣 5 → 𝑣 6 →   𝑣 3 →   𝑣 2 diperoleh jarak minimal 𝐶 𝑔𝑟𝑒𝑑𝑑𝑦 = 1,4 + 1,3 + 1,9 + +2,7 + 1,1 = 8,4
4) Perhitungan algoritma ant colony optimization
Nilai untuk Pheromone awal, yaitu:
𝜏 0 = 6 8,4 = 0,714285714
Langkah  selanjutnya  yaitu  mencari  nilai visibilitas. Sehingga didapatkan:
𝜂 1.2 = 1 𝑑 1,2 = 1 2,2 = 0,455 𝜂 1.3 = 1 𝑑 1,3 = 1 1,9 = 0,526 𝜂 1.4 = 1 𝑑 1,4 = 1 1,4 = 0,714 𝜂 1.5 = 1 𝑑 1,5 = 1 2,4 = 0,417 𝜂 1.6 = 1 𝑑 1,6 = 1 3,3 = 0,303
diperoleh  nilai  visibilitas  antara  titik  sebagai berikut:
Tabel 4.3 Nilai Visibilitas Antar Titik
𝑣 1 𝑣 2 𝑣 3 𝑣 4 𝑣 5 𝑣 6 𝑣 1 0 0,455 0,526 0,714 0,417 0,303 𝑣 2 0,455 0 0,909 0,455 0,476 0,263 𝑣 3 0,526 0,909 0 0,526 0,476 0,370 𝑣 4 0,714 0,455 0,526 0 0,769 0,476 𝑣 5 0,417 0,476 0,476 0,769 0 0,526 𝑣 6 0,303 0,263 0,370 0,476 0,526 0
Perhitungan  probabilitas  untuk  siklus  pertama ditunjukkan di sini ( NC=1 ).
Rumah Yatim Makassar
Rusunawa Kodam XIV/Hsn Pabrik Produksi Roti Tawar Bandung Makassar Panti Asuhan Al Muhtadina GOR Prof Tahir Djide Lapangan Tala BTP/GLT
Siklus ke-1 (NC=1) Semut ke-1 (k=1) Tabu list = 𝑣 1 = ∑ [𝜏 𝑖𝑗 ] 𝛼 [𝜂 𝑖𝑗 ] 𝛽 𝑲 ′ ∈{𝑁−𝑡 𝑎 𝑏 𝑢 𝑘 } = (0,714285714) 1 . (0,455) 1 +
(0,714285714) 1 . (0,526) 1 +
(0,714285714) 1 . (0,714) 1 + (0,714285714) 1 . (0,417) 1 + (0,714285714) 1 . (0,303) 1
Titik 𝑣 1 𝑝 11 1 = 0
Titik 𝑣 2 𝑝 12 1 = [𝜏 𝑖𝑗 ] 𝛼 [𝜂 𝑖𝑗 ] 𝛽 ∑ [𝜏 𝑖𝑗 ] 𝛼 [𝜂 𝑖𝑗 ] 𝛽 𝑲′∈{𝑁−𝑡 𝑎 𝑏 𝑢𝑘} = (0,455) 1 .(0,714285714) 1 1,72488852 = 0,188
Titik 𝑣 3 𝑝 13 1 = [𝜏 𝑖𝑗 ] 𝛼 [𝜂 𝑖𝑗 ] 𝛽 ∑ [𝜏 𝑖𝑗 ] 𝛼 [𝜂 𝑖𝑗 ] 𝛽 𝑲′∈{𝑁−𝑡 𝑎 𝑏 𝑢𝑘}
= (0,526) 1 .(0,714285714) 1 1,72488852 = 0,218
Titik 𝑣 4 𝑝 14 1 = [𝜏 𝑖𝑗 ] 𝛼 [𝜂 𝑖𝑗 ] 𝛽 ∑ [𝜏 𝑖𝑗 ] 𝛼 [𝜂 𝑖𝑗 ] 𝛽 𝑲′∈{𝑁−𝑡 𝑎 𝑏 𝑢𝑘}
= (0,714) 1 .(0,714285714) 1
1,72488852 = 0,296 Titik 𝑣 5 𝑝 15 1 = [𝜏 𝑖𝑗 ] 𝛼 [𝜂 𝑖𝑗 ] 𝛽 ∑ [𝜏 𝑖𝑗 ] 𝛼 [𝜂 𝑖𝑗 ] 𝛽 𝑲′∈{𝑁−𝑡 𝑎 𝑏 𝑢𝑘}
= (0,417) 1 .(0,714285714) 1
1,72488852
= 0,173
Titik 𝑣 6 𝑝 16 1 = [𝜏 𝑖𝑗 ] 𝛼 [𝜂 𝑖𝑗 ] 𝛽 ∑ [𝜏 𝑖𝑗 ] 𝛼 [𝜂 𝑖𝑗 ] 𝛽 𝑲′∈{𝑁−𝑡 𝑎 𝑏 𝑢𝑘}
= (0,303) 1 .(0,714285714) 1 1,72488852

## = 0,125
Setelah  nilai  perjalanan  semut  telah ditentukan  maka  selanjutnya  dapat  disusun  6 tabel sebagai berikut:
Tabel 4.4 Perjalanan Pertama Semut Semut Titik Awal PROBABILITAS Titik Terpilih TABU LIST 𝒗 𝟏 𝒗 𝟐 𝒗 𝟑 𝒗 𝟒 𝒗 𝟓 𝒗 𝟔 k 1 𝑣 1 0 0,188 0,218 0,296 0,173 0,125 𝑣 6 𝑣 1 → 𝑣 6
k 2 𝑣 2 0,178 0 0,355 0,178 0,186 0,103 𝑣 3 𝑣 2 → 𝑣 3 k 3 𝑣 3 0,187 0,324 0 0,187 0,170 0,132 𝑣 2 𝑣 3 → 𝑣 2 k 4 𝑣 4 0,243 0,155 0,179 0 0,262 0,162 𝑣 2 𝑣 4 → 𝑣 2 k 5 𝑣 5 0,156 0,179 0,179 0,289 0 0,198 𝑣 1 𝑣 5 → 𝑣 1 k 6 𝑣 6 0,156 0,136 0,191 0,246 0,271 0 𝑣 5 𝑣 6 → 𝑣 5

## Tabel 4.5 Perjalanan Kedua Semut
Semut Titik Awal PROBABILITAS Titik Terpilih TABU LIST 𝒗 𝟏 𝒗 𝟐 𝒗 𝟑 𝒗 𝟒 𝒗 𝟓 𝒗 𝟔
k 1 𝑣 6 0 0,188 0,218 0,296 0,173 0 𝑣 5 𝑣 1 → 𝑣 6 → 𝑣 5
k 2 𝑣 3 0,178 0 0 0,178 0,186 0,103 𝑣 5 𝑣 2 → 𝑣 3 → 𝑣 5
k 3 𝑣 2 0,187 0 0 0,187 0,170 0,132 𝑣 1 𝑣 3 → 𝑣 2 → 𝑣 1
k 4 𝑣 2 0,243 0 0,179 0 0,262 0,162 𝑣 6 𝑣 4 → 𝑣 2 → 𝑣 6 k 5 𝑣 1 0 0,179 0,179 0,289 0 0,198 𝑣 2 𝑣 5 → 𝑣 1 → 𝑣 2 k 6 𝑣 5 0,156 0,136 0,191 0,246 0 0 𝑣 4 𝑣 6 → 𝑣 5 → 𝑣 4

## Tabel 4.6 Perjalanan Ketiga Semut
Semut Titik Awal VISIBILITAS ANTAR LOKASI Titik Terpilih TABU LIST 𝒗 𝟏 𝒗 𝟐 𝒗 𝟑 𝒗 𝟒 𝒗 𝟓 𝒗 𝟔 k 1 𝑣 5 0 0,215 0,249 0,338 0 0 𝑣 2 𝑣 1 → 𝑣 6 → 𝑣 5 → 𝑣 2
k 2 𝑣 5 0,276 0 0 0,276 0 0,160 𝑣 4 𝑣 2 → 𝑣 3 → 𝑣 5 → 𝑣 4
k 3 𝑣 1 0 0 0 0,277 0,251 0,195 𝑣 4 𝑣 3 → 𝑣 2 → 𝑣 1 → 𝑣 4
k 4 𝑣 6 0,287 0 0,212 0 0,309 0 𝑣 3 𝑣 4 → 𝑣 2 → 𝑣 6 → 𝑣 3
k 5 𝑣 2 0 0 0,212 0,342 0 0,234 𝑣 3 𝑣 5 → 𝑣 1 → 𝑣 2 → 𝑣 3
k 6 𝑣 4 0,214 0,186 0,262 0 0 0 𝑣 3 𝑣 6 → 𝑣 5 → 𝑣 4 → 𝑣 3

## Tabel 4.7 Perjalanan Keempat Semut
Semut Titik Awal VISIBILITAS ANTAR LOKASI Titik Terpilih TABU LIST 𝒗 𝟏 𝒗 𝟐 𝒗 𝟑 𝒗 𝟒 𝒗 𝟓 𝒗 𝟔 k 1 𝑣 2 0 0 0,310 0,421 0 0 𝑣 3 𝑣 1 → 𝑣 6 → 𝑣 5 → 𝑣 2 → 𝑣 3
k 2 𝑣 4 0,388 0 0 0 0 0,224 𝑣 1 𝑣 2 → 𝑣 3 → 𝑣 5 → 𝑣 4 → 𝑣 1
k 3 𝑣 4 0 0 0 0 0,347 0,270 𝑣 5 𝑣 3 → 𝑣 2 → 𝑣 1 → 𝑣 4 → 𝑣 5
k 4 𝑣 3 0,355 0 0 0 0,383 0 𝑣 1 𝑣 4 → 𝑣 2 → 𝑣 6 → 𝑣 3 → 𝑣 1
k 5 𝑣 3 0 0 0 0,434 0 0,297 𝑣 6 𝑣 5 → 𝑣 1 → 𝑣 2 → 𝑣 3 → 𝑣 6
k 6 𝑣 3 0,324 0,281 0 0 0 0 𝑣 1 𝑣 6 → 𝑣 5 → 𝑣 4 → 𝑣 3 → 𝑣 1 Tabel 4.8 Perjalanan Kelima Semut Semut VISIBILITAS ANTAR LOKASI TABU LIST 𝒗 𝟏 𝒗 𝟐 𝒗 𝟑 𝒗 𝟒 𝒗 𝟓 𝒗 𝟔 k 1 0 0 0 1 0 0
𝑣 1 → 𝑣 6 → 𝑣 5 → 𝑣 2 → 𝑣 3 → 𝑣 4
k 2 0 0 0 0 0 1
𝑣 2 → 𝑣 3 → 𝑣 5 → 𝑣 4 → 𝑣 1 → 𝑣 6
k 3 0 0 0 0 0 1
𝑣 3 → 𝑣 2 → 𝑣 1 → 𝑣 4 → 𝑣 5 → 𝑣 6
k 4 0 0 0 0 1 0
𝑣 4 → 𝑣 2 → 𝑣 6 → 𝑣 3 → 𝑣 1 → 𝑣 5 k 5 0 0 0 1 0 0 𝑣 5 → 𝑣 1 → 𝑣 2 → 𝑣 3 → 𝑣 6 → 𝑣 4
k 6 0 1 0 0
0 0 𝑣 6 → 𝑣 5 → 𝑣 4 → 𝑣 3 → 𝑣 1 → 𝑣 2
Maka  keseluruhan  perjalanan  semut  sebagai berikut.
Tabel 4.9 Rute perjalanan semut dan penambahan jumlah pheromone Semut Tabu List Panjang (km) ∆𝝉 𝒊𝒋𝒌
k 1 𝑣 1 → 𝑣 6 → 𝑣 5 → 𝑣 2 → 𝑣 3 → 𝑣 4 → 𝑣 1 11,7 0,085
k 2 𝑣 2 → 𝑣 3 → 𝑣 5 → 𝑣 4 → 𝑣 1 → 𝑣 6 → 𝑣 2 13 0,077 k 3 𝑣 3 → 𝑣 2 → 𝑣 1 → 𝑣 4 → 𝑣 5 → 𝑣 6 → 𝑣 3 10,6 0,094 k 4 𝑣 4 → 𝑣 2 → 𝑣 6 → 𝑣 3 → 𝑣 1 → 𝑣 5 → 𝑣 4 14,3 0,070 k 5 𝑣 5 → 𝑣 1 → 𝑣 2 → 𝑣 3 → 𝑣 6 → 𝑣 4 → 𝑣 5 11,8 0,085
k 6 𝑣 6 → 𝑣 5 → 𝑣 4 → 𝑣 3 → 𝑣 1 → 𝑣 2 → 𝑣 6 13 0,077
Berdasarkan  Tabel  4.9  diatas  didapatkan  rute terbaik  yaitu  rute  yang  dilalui  oleh  semut k 3 dengan  panjang  rute  10,6  km  dengan  rute 𝑣 3 → 𝑣 2 → 𝑣 1 → 𝑣 4 → 𝑣 5 → 𝑣 6 → 𝑣 3 .
Selanjutnya dilakukan pembaharuan pheromone dengan  jumlah pheromone yang  baru  saja ditambahkan
sebesar ∆𝜏 𝑖𝑗𝑘 = 0,094 menggunakan rumus sebagai berikut:
𝜏 𝑖𝑗 = (1 − 0,1)(0,714285714) +  0,094 =  0,737196765
Pencarian manual hanya membatasi siklus pertama.  Sehingga,  diperoleh  rute  terbaik sementara yaitu
𝑣 3 → 𝑣 2 → 𝑣 1 → 𝑣 4 → 𝑣 5 → 𝑣 6 → 𝑣 3 dengan jarak tempuh 10,6 km.

## 5. KESIMPULAN
Berdasarkan hasil penelitian yang diperoleh  dari  hasil  yang  telah  dihitung,  maka dapat diambil  kesimpulan  bahwa  dalam menyelesaikan  kasus Travelling  Salesman Problem (TSP)  khususnya  pada  penerapan algoritma ant  colony  optimization rute  jalur terpendek pada studi kasus distribusi barang JNE wilayah Bumi Tamalanrea Permai pada optimasi rute  kurir  jasa  pengiriman  untuk  6  titik  lokasi diperoleh  sementara  siklus  pertama  yaitu  GOR Prof  Tahir  Djide  ( 𝑣 3 )  menuju  Panti  Asuhan  Al Muhtadina ( 𝑣 2 ) menuju Rumah Yatim Makassar ( 𝑣 1 )  menuju  Lapangan  Tala  BTP/GLT  ( 𝑣 4 ) menuju Rusunawa Kodam XIV/Hsn ( 𝑣 5 ) menuju Pabrik Produksi Roti Tawar Bandung Makassar ( 𝑣 6 )  lalu  kembali  pada  titik  pertama  GOR  Prof Tahir Djide (V 3 ) dengan jarak tempuh sepanjang 10,6  km. (𝑣 3 → 𝑣 2 → 𝑣 1 → 𝑣 4 → 𝑣 5 → 𝑣 6 → 𝑣 3 ) .

## 6. DAFTAR PUSTAKA
[1] Batmetan,  J.  R.  (2016). Algoritma  Ant
Colony Optimization (ACO) untuk
pemilihan jalur tercepat evakuasi bencana Gunung  Lokon  Sulawesi  Utara . Jurnal Teknologi Informasi , 14(1), 31–48.
[2] Dorigo,  M.,  &  Stützle,  T.  (2004). Ant colony  optimization .  In  A  Bradford  Book The MIT Press Cambridge, Massachusetts London,
England. https://mitpress.mit.edu/books/ant-colony- optimization
[3] Hasmawati.  (2016). Bahan  Ajar  Bahan Ajar Bahan Ajar . In Hasanuddin University Repository.
http://repository.upy.ac.id/6374/1/BAHA
N-AJAR-SEJARAH-PERADABAN- BARAT-KLASIK-2023.pdf
[4] Lisdiarto,  A.,  &  Winarti,  W.  (2023).
Penerapan Metode Ant Colony Optimization  Untuk  Menentukan  Jalur Distribusi  Di  PT.  Indomarco  Adi  Prima. Teknik Dan Multimedia , 1 (4), 938–946.
[5] Maryati,  I.,  &  Wibowo,  H.  K.  (2012). Optimasi  penentuan  rute  kendaraan  pada sistem distribusi barang dengan ant colony optimization .  Semanticscholar , 163–168.
[6] Mutakhiroh,  I.,  Indrato,  &  Hidayat,  T. (2007). Pencarian Jalur Terpendek
Menggunakan  Algoritma  Semut .  Seminar Nasional Aplikasi Teknologi Informasi. 81- 85.
[7] Mutakhiroh,  I.,  Saptono,  F.,  Hasanah,  N., &  Wiryadinata,  R.  (2007).  Pemanfaatan Metode  Heuristik  Dalam  Pencarian  Jalur Terpendek  Dengan  Algoritma  Semut  dan Algoritma  Genetika. SNATI  (Seminar Nasional  Aplikasi  Teknologi  Informasi)
2007 , 2007 (Snati),
B33–B39. http://journal.uii.ac.id/index.php/Snati/arti cle/viewFile/1623/1398
[8] Nugraha,  D.  C.,  &  Khadafi,  S.  (2021).
Penerapan  Travelling  Salesman  Problem Untuk Optimasi Jarak Jalur Kurir
Menggunakan  Algoritma  Ant  Colony Optimization  (Aco). Seminar  Nasional Sains  Dan  Teknologi  Terapan  IX  2021 , 259–266.
[9] Wahyuningsih,  D.,  Syahreza,  E.  (2018). Shortest Path search Futsal Field Location with  Dijkstra  Algorithm .  IJCCS .  12(2), 161-170.
[10] Windarto,  A.  P.,  &  Sudirman.  (2018). Penerapan Algoritma Semut Dalam Penentuan Distribusi Jalur Pipa Pengolahan  Air  Bersih. Jurnal  Sistem Informasi Bisnis , 8(2), 9. https://doi.org/10.21456/vol8iss2pp9-18