ILKOM  Jurnal  Ilmiah  Volume  11  Nomor 2 Agustus 2019 Terakreditasi peringkat 3 SK. No. 28/E/KPT/2019

## SISTEM PENENTUAN RUTE PENDISTRIBUSIAN PRODUK AIR MINERAL MENGGUNAKAN ALGORITMA ANT COLONY SYSTEM
Deny Wiria Nugraha 1 , Albrecht Yordanus Erwin Dodu 2 , Stevi Septiana 3
1 deny.wiria.nugraha@gmail.com, 2 ayerwin.dodu@gmail.com, 3 steviseptiana27@gmail.com 1,2,3 Jurusan Teknologi Informasi, Fakultas Teknik, Universitas Tadulako

## Abstrak
Permasalahan penentuan rute distribusi dapat dikategorikan sebagai Travelling Salesman Problem (TSP). TSP merupakan pencarian urutan lokasi dimana seorang salesman melakukan perjalanan dari lokasi  awal  menuju  daftar  sejumlah  lokasi  yang  harus  dilalui.  Setiap  lokasi  hanya  boleh  dikunjungi satu kali dan berakhir pada lokasi awal keberangkatan. Penelitian ini bertujuan untuk menyelesaikan masalah penentuan rute pendistribusian produk air mineral pada PT. Anugerah Wina Sentosa dengan mengimplementasikan  algoritma Ant  Colony  System (ACS)  untuk  melakukan  pencarian  rute. Algoritma  ACS  merupakan  algoritma  yang  diadopsi  dari  perilaku  semut  untuk  menentukan  rute terpendek  dari  sarang  menuju  sumber  makanan.  Berdasarkan  penelitian,  hasil  algoritma  ACS menunjukan  bahwa  semakin  besar  kasus  yang  akan  diselesaikan  maka  berpengaruh  pada  waktu eksekusi sistem namun tetap dapat menghasilkan rute dengan jarak terbaik. Keberhasilan algoritma ini dipengaruhi oleh penentuan nilai parameter ACS yaitu β, qo, q, α, 𐐙 , jumlah semut dan jumlah siklus semut yang ditentukan dengan melakukan analisa berdasarkan kasus TSP yang akan diselesaikan. Kata kunci: Travelling Salesman Problem (TSP), Ant Colony System (ACS)

## Abstract
The problem of determining distribution routes can be categorized as Traveling Salesman Problem (TSP). TSP is a search for a sequence of locations where a salesman travels from the initial location to a list of locations  which must be passed. Each location can  only be visited once and ends at the initial location of departure. This study aims to resolve the problem of determining the distribution route for  mineral  water products  at  PT.  Anugerah Wina  Sentosa  by  implementing  the  Ant  Colony  System (ACS)  algorithm  to  conduct  route  searches.  The  ACS  algorithm  is  an  algorithm  adopted  from  the behavior  of  ants  to  determine  the  shortest  route  from  the  nest  to  the  food  source.  Based  on  the research, the results of the ACS algorithm show that the greater the case to be resolved will affect the system execution time but still can produce the best distance route. The success of this algorithm is influenced by the determination of the value of the ACS parameter, namely β, qo, q, α, 𐐙 , the number of ants and the number of ant cycles determined by analyzing the TSP case to be resolved. Keywords: Travelling Salesman Problem (TSP), Ant Colony System (ACS)

## 1.  Pendahuluan
Kegiatan distribusi merupakan kegiatan yang sering dilakukan untuk menyalurkan hasil produksi kepada  para  konsumen.  Dalam  dunia  industri,  pendistribusian  yang  baik  sangat  penting  karena berpengaruh pada pengoptimalan biaya, kualitas barang serta ketepatan waktu pengantaran.
Kegiatan  pendistribusian  juga  terjadi  pada  PT.  Anugerah  Wina  Sentosa  yang  merupakan produsen air mineral yang cukup besar di kota Palu. Produsen air mineral ini memiliki pelanggan tetap yang  menerima  produk  air  mineral  berupa  kemasan  galon  dan  gelas  (250  ml  dan  220  ml)  setiap harinya  sesuai  jadwal  pengantaran  produk  yang  dilakukan  oleh  lima  kendaraan  milik  perusahaan pada  masing-masing  wilayah  yang  telah ditentukan.  Banyaknya  pelanggan  tetap  pada  produsen  air mineral  ini  membuat  perusahaan  harus  menjaga  kepercayaan  para  konsumen  dengan  memberikan pelayanan  yang  baik  yaitu  mengantarkan  produk  air  mineral  dengan  kualitas  yang  tinggi  dan  tepat waktu.
Proses pendistribusian produk air mineral PT. Anugerah Wina Sentosa disalurkan kepada para pelanggan  dengan  mengunjungi  semua  agen/toko  yang  telah  terjadwal  walaupun  agen/toko  tidak mengambil  produk  yang  sudah  dibawa.  Dalam  hal  ini,  karyawan  yang  bertugas  mengemudikan kendaraan  harus  memilih  rute  perjalanan  terbaik  untuk  mengujungi  setiap  agen/toko.  Namun banyaknya  jalur  menuju  tempat  tujuan  terkadang  membuat  pengemudi  memilih  jalur  atau  rute pendistribusian  yang  kurang  tepat.  Hal  ini  dapat  menyebabkan  kurang  efisiennya  jarak  pengantaran produk sehingga kegiatan pendistribusian menjadi tidak optimal.
ILKOM  Jurnal  Ilmiah  Volume  11  Nomor 2 Agustus 2019 Terakreditasi peringkat 3 SK. No. 28/E/KPT/2019
Permasalahan  penentuan  rute  pada  penelitian  ini  tanpa  mempertimbangkan  kapasitas kendaraan  serta  mengikuti  aturan  bahwa  lokasi-lokasi  pendistribusian  hanya  dikunjungi  satu  kali dapat dikategorikan sebagai permasalahan Travelling Salesman Problem (TSP) yang kemudian akan diselesaikan menggunakan algoritma Ant Colony System (ACS). Ant Colony System (ACS) merupakan algoritma pemecahan masalah optimasi yang terinspirasi dari  tingkah  laku  semut  dari  sarang  menuju  sumber  makanan.  Secara      alamiah      koloni      semut mampu     menemukan      rute      terpendek      dalam      perjalanan      dari      sarang     ke      tempat-tempat sumber      makanan.  Hal  tersebut  dapat  dilakukan  dengan  meninggalkan  jejak pheromone untuk berkomunikasi dengan semut lainnya.
Dalam  penelitiannya,  Amalia  (2015)  meneliti  tentang  pencarian  jalur  terpendek  menggunakan Ant  Colony  System (Kasus:  Pariwisata  Kota  Bogor).  Penelitian  ini  bertujuan  untuk  membantu  agen travel  atau  Dinas  Pariwisata  dan  Kebudayaan  kota  Bogor  untuk  memberikan  alternatif  terbaik  bagi para wisatawan untuk menguji obyek-obyek wisata yang ada di kota Bogor. Pencarian jalur terpendek menggunakan Ant  Colony  Sytem mendapatkan  pilihan  terbaik  dalam  mengunjungi  obyek  obyek wisata  yang  ada  di  kota  Bogor  dengan  memperhitungkan  efisiensi  waktu  dan  biaya.  Pemilihan  rute dengan menggunakan algoritma Ant Colony System pada 9 obyek wisata kota Bogor  menghasilkan rute dengan jarak tempuh sejauh 27482 meter [1].
Dalam penelitiannya, Gunawan dkk (2015) membuat perancangan sistem informasi penentuan rute pengiriman barang dengan metode Ant Colony Optimization studi kasus: PT. XYZ. Penelitian ini dilakukan  untuk  mengatasi  masalah  kegiatan  pendistribusian  yang  sering  mengalami  keterlambatan pengiriman  pesanan  kepada  konsumen.  Dari  hasil  penelitian  ini,  pengolahan  data  menggunakan metode  Ant  Colony  Optimization untuk  perancangan  rute  yang  menangani  30  pesanan, metode Ant Colony Optimization dapat mengurangi keterlambatan sebesar 10% dari keterlambatan [2]. Dalam  penelitiannya,  Tutupary  dkk  (2014)  membuat  aplikasi  algoritma Ant  Colony  System dalam penentuan rute optimum distribusi BBM pada PT. Burung Laut. Penelitian ini dilakukan untuk membandingkan rute hasil pencarian algoritma Ant Colony System dengan rute yang tidak pasti atau system tramper dalam pendistribusian BBM yang dilakukan oleh PT. Burung Laut dari kota Ambon ke 13 lokasi disekitarnya. Hasil dari penelitian ini membuktikan bahwa dengan menggunakan algoritma Ant  Colony  System ,  jarak  rute  pendistribusian  BBM  dapat ditempuh  sejauh  5.262  mil  dengan  waktu tempuh 3,09 minggu. Sedangkan menggunakan sistem tramper , jarak rute yang harus ditempuh untuk pendistribusian  BBM  sejauh  5.798  mil  dalam  waktu  3,37  minggu.  Dari  hasil  penelitian,  rute  yang didapatkan  oleh  algoritma Ant  Colony  System mendapatkan  nilai  yang  lebih  baik  sehingga membuktikan bahwa algoritma ini dapat digunakan untuk mendapatkan rute yang lebih baik [3].
Berdasarkan masalah yang dihadapi oleh PT. Anugerah Wina Sentosa seperti yang dijabarkan maka solusi yang dapat dilakukan adalah membuat sebuah sistem yang memanfaatkan google maps API  dan  implementasi  algoritma Ant  Colony System (ACS)  untuk  menggambarkan  dan  menentukan jalur-jalur terpendek yang dapat dilalui oleh driver kendaraan pengantar produk air mineral. Sistem ini akan  dibangun  berbasis  web  dan  terbagi  dalam  dua  sistem  yakni  sistem  admin  dan  sistem  drvier. Sistem  admin  merupakan  sistem  yang  dirancang  untuk  melakukan  pengolahan  data  kendaraan, pelanggan dan rute distribusi sedangkan sistem driver merupakan sistem yang dirancang untuk driver agar  dapat  melihat  rute  pendistribusian  secara  online.  Penelitian  ini  bertujuan  untuk  membantu menyelesaikan  masalah  pada  PT.  Anugerah  Wina  Sentosa  dalam  menentukan  rute  terbaik  untuk mendistribusikan produk air mineral hasil produksi perusahaan kepada para pelanggan di seluruh kota Palu dengan jarak yang lebih baik.
2.  Metode
2.1. Graph
Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai G = (V,  E),  dimana:  G  = graph ,  V  =  simpul  atau  vertex,  E  =  busur  atau  edge. Graph terdiri  dari graph berbobot dan tak berbobot [4].
2.2. Travelling Salesman Problem (TSP) Traveling  Salesman  Problem (TSP)  merupakan  permasalahan  optimasi  kombinatorial  dimana terdapat  seorang  salesman  yang  ingin  mengunjungi  seluruh  kota  pada  suatu daerah  tepat  satu  kali dan  harus  kembali  ke  kota  awal  keberangkatan.  Penyelesaian  dari  TSP  adalah  rute  dengan  bobot minimum.  Beberapa  permasalahan  yang  dapat  diselesaikan  dengan  TSP  adalah  permasalahan perencanaan kunjungan wisata, logistik, integrated circuit (IC), dan lain-lain [5][6][7].
ILKOM  Jurnal  Ilmiah  Volume  11  Nomor 2 Agustus 2019 Terakreditasi peringkat 3 SK. No. 28/E/KPT/2019
2.3.  Algoritma Ant Colony System (ACS)
Menurut  Dorigo dan Gambardella  (dalam Amalia, 2015) ACS memiliki tiga aspek utama yaitu pertama  aturan  transisi  status,  pada  sistem  ini  memberikan  suatu  cara  langsung  untuk menyeimbangkan  antara  penjelajahan  ( exploration )  ruas-ruas  yang  baru  dengan  eksploitasi ( exploitation ) dari sebuah priori dan pengetahuan yang dihimpun mengenai masalah tersebut, kedua yaitu  disaat ants membangun  sebuah  solusi,  diterapkan  suatu  aturan  pembaruan  pheromone  lokal ( local  pheromone  updating  rule )  dan  ketiga  yaitu  aturan  pembaruan pheromone global  yang  hanya dilakukan pada ruas-ruas yang merupakan bagian dari tur terbaik [1][8].
2.4.  Karakteristik Algoritma Ant Colony System (ACS)
Terdapat tiga  karakteristik  utama  dari  ACS,  yaitu  aturan  transisi  status,  aturan  pembaruan pheromone lokal dan aturan pembaruan pheromone global.
1.  Aturan Transisi Status
Aturan  transisi  status  yang  berlaku  pada  ACS  adalah  sebagai  berikut:  seekor  semut  yang ditempatkan pada titik t memilih untuk menuju ke titik v , kemudian diberikan bilangan pecahan acak q dimana  0≤ q ≤1, q 0 adalah  sebuah  parameter  yaitu  probabilitas  semut  melakukan  eksplorasi  pada setiap  tahapan,  dimana    (0≤ q 0 ≤1)  dan p k (t,v) adalah  probabilitas  dimana  semut  k  memilih  untuk bergerak  dari  titik  t  ke  titik  v.  Jika q < q 0 maka  pemilihan  titik  yang  akan  dituju  menerapkan  aturan yang ditunjukkan oleh persamaan (1).
(1)
dengan v = titik yang akan dituju sedangkan jika q>q 0 digunakan persamaan (2).
(2)
dengan
dimana  ( t , u )  adalah  nilai  dari  jejak pheromone pada  titik ( t , u ), adalah fungsi heuristik dimana dipilih sebagai invers jarak antara titik t dan u, β merupakan sebuah parameter yang mempertimbangkan kepentingan relatif dari informasi heuristic , yaitu besarnya bobot yang  diberikan  terhadap  parameter  informasi  heuristik,  sehingga  solusi  yang  dihasilkan  cenderung berdasarkan nilai fungsi matematis. Nilai untuk parameter β adalah ≥ 0.
2.  Aturan Pembaruan Pheromone Lokal
Selagi  melakukan  tur  untuk  mencari  solusi  dari  TSP,  semut mengunjungi  ruas-ruas  dan mengubah  tingkat pheromone pada  ruas-ruas  tersebut  dengan  menerapkan  aturan  pembaruan pheromone lokal yang ditunjukan oleh persamaan (3).
(3)
dimana: 𐐙 = Parameter dengan nilai 0 sampai 1 ∆τ     = Perubahan pheromone
= Panjang tur yang diperoleh antar
= Jumlah node
𐐙 adalah sebuah parameter (koefisien evaporasi), yaitu besarnya koefisien penguapan pheromone. Adanya penguapan pheromone menyebabkan tidak semua semut mengikuti jalur yang sama dengan semut sebelumnya.
3.  Aturan Pembaruan Pheromone Global
Pada sistem ini, pembaruan pheromone secara global hanya dilakukan oleh semut yang membuat tur  terpendek  sejak  permulaan  percobaan.  Pada  akhir  sebuah  iterasi,  setelah  semua  semut menyelesaikan  tur  mereka,  sejumlah pheromone ditaruh  pada  ruas-ruas  yang  dilewati  oleh  seekor semut  yang  telah  menemukan  tur  terbaik  (ruas-ruas  yang  lain  tidak  diubah). Tingkat pheromone itu diperbarui  dengan  menerapkan  aturan  pembaruan pheromone global  yang  ditunjukkan  oleh persamaan (4).
τ(t,v)←(1 - α).τ(t,v) + α.∆τ(t,v)
(4)
ILKOM  Jurnal  Ilmiah  Volume  11  Nomor 2 Agustus 2019 Terakreditasi peringkat 3 SK. No. 28/E/KPT/2019
Dimana: τ ( t , v ) = Nilai pheromone akhir setelah mengalami pembaruan lokal L gb = Panjang jalur terpendek pada akhir siklus α       = Parameter dengan nilai antara 0 sampai 1 ∆τ     = P erubahan pheromone ∆τ ( t , v ) bernilai 1/ L gb jika ruas (t,v) merupakan bagian dari rute terbaik namun jika sebaliknya ∆τ ( t , v ) = 0. α adalah tingkat kepentingan relatif dari pheromone atau besarnya bobot yang diberikan terhadap pheromone , sehingga solusi yang dihasilkan cenderung mengikuti sejarah masa lalu dari semut dari perjalanan sebelumnya, dimana nilai parameter α adalah ≥ 0, dan L gb adalah panjang dari tur terbaik secara global sejak permulaan percobaan.

## 3.  Hasil dan Pembahasan

## 3.1. Sistem Penentuan Rute Pendistribusian Produk Air Mineral
Sistem  penentuan  rute  pendistribusian  produk  air  mineral  memiliki  dua  bagian  sistem  yakni sistem  administrator  dan  sistem driver .  Sistem  administrator  dapat  melakukan  pengolahan  data sedangkan  sistem driver digunakan  untuk  melihat  hasil  pengolahan  data  dari  sistem  admin  berupa lokasi pelanggan dan rute distribusi. Halaman hasil lokasi pelanggan dapat dilihat pada gambar 1. dan halaman hasil rute distribusi produk air mineral dapat dilihat pada gambar 2.
Gambar 1. Halaman lokasi pelanggan
ILKOM  Jurnal  Ilmiah  Volume  11  Nomor 2 Agustus 2019 Terakreditasi peringkat 3 SK. No. 28/E/KPT/2019

## Gambar 2. Halaman rute distribusi

## 3.2. Implementasi Algoritma Ant Colony System (ACS)
Implementasi algoritma ACS dalam sistem dapat digambarkan pada flowchart ACS untuk penyelesaian TSP yang dapat dilihat pada gambar 3.
Jumlahtitik=Jumlah titik kasus TSP Tentukan nilai pheromone awal Jumlahsemut=Tentukan jumlah semut Tentukan titik awal semua semut Tentukan qo, beta, alpha , rho Siklus=Tentukan jumlah iterasi
(For j=0; j<count(Siklus); j++) Pilih titik selanjutnya dengan persamaan 1 atau 2 Ubah nilai pheromone lokal dengan persamaan 3 Hitung rute lintasan masing- masing semut Pilih semut dengan rute lintasan terbaik Ubah pheromone global dengan persamaan 4 Pilih rute lintasan terbaik dari semua iterasi (For k=0; k<count(Jumlahsemut); k++) (For x=0; x<count(Jumlahsemut); x++) (For l=0; l<Jumlahtitik; l++) Catat titik yang sudah dilalui dalam tabu list Titik  terpilih== tabulist Y T Titik terpilih == next Y T If k>=count(Jumlah semut) Y T If x>=count(Jumlah semut) T Y If j>=count(Siklus) T Y Selesai Kembali ke titik awal, Ubah nilai pheromone lokal dengan persamaan 3 Mulai
ILKOM  Jurnal  Ilmiah  Volume  11  Nomor 2 Agustus 2019 Terakreditasi peringkat 3 SK. No. 28/E/KPT/2019
Berikut  adalah  ilustrasi  implementasi  algoritma  ACS  dalam  menemukan  rute  distribusi  dari lokasi perusahaan menuju beberapa lokasi pelanggan. Gambar lokasi pelanggan yang akan dilakukan ilustrasi pencarian rute dapat dilihat pada gambar 4.
Gambar 4. Lokasi ilustrasi pelanggan
Jarak  antar  pelanggan  dapat  direpresentasikan  dalam  bentuk  tabel  jarak  yang  dapat  dilihat pada tabel 1.
Tabel 1. Jarak (KM) A B C D E A 0 1,68 3,66 2,62 3,56 B 1,68 0 2,75 2,41 4,07 C 3,66 2,75 0 1,71 1,51 D 2,62 2,41 1,71 0 1,67 E 3,56 4,07 1,51 1,67 0
Keterangan:
A : PT. Anugerah Wina Sentosa
B : Abil C : Salsabila D : Nil Swalayan E : Diana
Selanjutnya dilakukan proses pembuatan rute dengan beberapa tahap sebagai berikut :
1.  Pembuatan tabel invers jarak Nilai invers jarak dihasilkan dari
. Tabel invers jarak dapat dilihat pada tabel 2. Tabel 2. Invers jarak A B C D E A 0 0,59 0,27 0,38 0,28 B 0,59 0 0,36 0,41 0,24 C 0,27 0,36 0 0,58 0,66 D 0,38 0,41 0,58 0 0,6 E 0,28 0,24 0,66 0,6 0
ILKOM  Jurnal  Ilmiah  Volume  11  Nomor 2 Agustus 2019 Terakreditasi peringkat 3 SK. No. 28/E/KPT/2019
2.  Penentuan pheromone awal
Nilai pheromone awal  dihasilkan  dari dimana  n  adalah  jumlah  titik  yang  ada  pada
masalah  sedangkan merupakan  panjang  atau  jarak  rute  yang  dihasilkan  dari  metode Nearest Neighboard . Tabel pheromone awal dapat dilihat pada tabel 3.
Tabel 3. Pheromone awal A B C D E A  0,000018  0,000018  0,000018  0,000018  0,000018 B  0,000018  0,000018  0,000018  0,000018  0,000018 C  0,000018  0,000018  0,000018  0,000018  0,000018
D  0,000018  0,000018  0,000018  0,000018  0,000018 E  0,000018  0,000018  0,000018  0,000018  0,000018

## 3.  Penentuan parameter ACS
Parameter  yang  digunakan  pada  algoritma  ACS  dapat  diinisialisasi  secara  berbeda-beda  untuk setiap  kasus  karena  hasil  yang  didapatkan  algoritma  ini  bergantung  pada  nilai  parameter  yang ditentukan. Jika inisialisasi parameter tidak tepat maka dapat berpengaruh pada hasil jarak dan waktu eksekusi  algoritma  yang  cenderung  akan  lebih  lama.  Pada  kasus  ilustrasi  ini  digunakan  parameter dengan nilai ,
jumlah semut = 10 dan jumlah siklus semut/iterasi =
5.
4.  Proses algoritma ACS
Setelah  proses  penentuan  parameter  telah  selesai  selanjutnya  agen-agen  semut  ditempatkan pada  setiap  titik  secara  random  untuk  mengunjungi  setiap  titik-titik  yang  terhubung  melalui  proses transisi status. Proses transisi status dipengaruhi oleh pemilihan nilai parameter qo (0≤ q 0 ≤1) dan nilai random  dari  nilai  parameter  q  ( 0≤ q ≤1 ).  Pada  proses  ini  semut  akan  memilih  untuk  melakukan eksploitasi  (jika q < q 0 )  dengan  melakukan  perhitungan
atau  eksplorasi
(jika q > q 0 ) dengan melakukan perhitungan
. Eksploitasi berarti semut hanya akan mengunjungi ruas-ruas simpul yang memiliki pheromone yang tinggi dengan bobot jarak yang kecil sedangkan ekplorasi berarti semut bisa saja mengunjungi ruas-ruas simpul yang memiliki pheromone yang tinggi dengan bobot jarak yang kecil atau ruas-ruas simpul yang memiliki pheromone yang rendah dengan bobot jarak yang besar.
Dalam  proses  perjalanan  setiap  semut,  proses  transisi  status  dilakukan  secara  berulang-ulang hingga  semua  titik  berhasil  dikunjungi  dan  menandai  setiap  titik  yang  telah  dikunjunginya  dengan menyimpannya  pada  tabu  list  yang  dimiliki  oleh  masing-masing  semut.  Titik  yang  telah  tersimpan dalam  tabu  list  semut  menjadi  daftar  titik  terlarang  yang  tidak  boleh  dikunjungi  lagi  oleh  semut tersebut.
Selagi  membangun  tur,  setiap  kali  semut  telah  memilih  titik  melalu  proses  transisi  status,  maka akan  dilakukan  proses  pembaharuan pheromone lokal  pada  ruas  titik  yang  sudah  dipilih  dengan melakukan  perhitungan
.  Tujuan  pembaruan pheromone lokal adalah  untuk  mengurangi  ketertarikan  ruas  dengan  melakukan  penguapan pheromone pada  ruas simpul  yang  telah  dilaluinya  sehingga  semut-semut  lain  tidak  akan  terjebak  atau  melalui  titik  yang sama secara terus-menerus.
Setelah semua semut menyelesaikan kunjungannya hingga tidak ada lagi titik yang tersisa maka semut akan kembali pada titik awal nya kemudian menghitung jarak atau bobot tiap titik yang sudah dilalui.  Hasil  bobot  jarak  yang  dihasilkan  setiap  semut  akan  dibandingkan  dan  memilih  satu  jalur semut dengan hasil bobot jarak terkecil. Semut dengan bobot jarak yang paling kecil akan mengalami pembaruan pheromone global  dengan  melakukan  perhitungan τ(t,v)←(1 - α).τ ( t,v)  +  α.∆τ(t,v)  . Proses pembaruan pheromone global ini dapat menguatkan ketertarikan ruas yang pendek dan mengarahkan semut-semut untuk mendapatkan hasil yang lebih baik pada siklus semut atau iterasi selanjutnya.
Selanjutnya setelah satu siklus semut atau iterasi telah selesai, maka masing-masing semut akan mengosongkan daftar tabu list dan melakukan pencarian rute pada siklus selanjutnya hingga batasan siklus  yang  telah  ditetapkan.  Jika  proses  semua  siklus  telah  selesai  maka  hasil  setiap  siklus  akan dibandingkan dan mengambil rute dengan bobot yang paling kecil untuk dijadikan hasil akhir sebagai rute terbaik.
ILKOM  Jurnal  Ilmiah  Volume  11  Nomor 2 Agustus 2019 Terakreditasi peringkat 3 SK. No. 28/E/KPT/2019
Pada proses algoritma ini, setiap kali melakukan pencarian rute, hasil yang didapatkan tidak selalu sama  karena  algoritma  ini  mendapatkan  hasil  berdasarkan  probabilitas  atau  peluang  namun  dapat menghasilkan hasil terbaik dengan mengatur nilai parameter yang tepat.
5.  Hasil pembuatan rute
Hasil pembuatan rute menghasilkan rute terbaik pada semut ke 2 dalam proses siklus semut atau iterasi ke 1 dengan bobot jarak 10,24 KM dan waktu eksekusi pencarian rute 0,009 detik. Rute terbaik yang dihasilkan yaitu A - D - E - C - B - A dengan keterangan jalur yaitu PT. Anugerah Wina Sentosa - Nil  Swalayan  -  Diana  -  Salsabila  -  Abil  -  PT.  Anugerah  Wina  Sentosa.  Hasil rute dapat dilihat  pada gambar 5.
Gambar 5. Hasil rute
Dari  hasil  pembuatan  rute  pada  gambar  5,  jalur  berwarna  hijau  merupakan  jalur  dimana driver memulai  proses  distribusi  sampai  pada  titik  pelanggan  terakhir  sedangkan  jalur  berwarna  biru merupakan jalur dimana driver kembali ke lokasi perusahaan

## 3.3. Pengujian Implementasi Algoritma ACS
Pengujian implementasi algoritma ACS akan dilakukan pada 3 kasus yaitu kasus 20 titik, 50 titik dan kasus 100 titik. Hasil pengujian dapat dilihat pada tabel 4.
Tabel 4. Hasil pengujian implementasi algoritma ACS
No. Jumlah Titik Jarak Waktu eksekusi 1 20 9,382 KM 58,236 detik 2 20 9,346 KM 58,708 detik 3 20 9,346 KM 61,756 detik Rata-rata 9,413 KM 9,358 KM 1 50 15,434 KM 370,045 detik 2 50 15,262 KM 373,159 detik 3 50 15,188 KM 454,313 detik Rata-rata 14,581 KM 15,295 KM 1 100 35,582 KM 1405,151 detik 2 100 36,636 KM 1728,304 detik 3 100 36,423 KM 2073,598 detik Rata-rata 36,214 KM 1735,684 detik
ILKOM  Jurnal  Ilmiah  Volume  11  Nomor 2 Agustus 2019 Terakreditasi peringkat 3 SK. No. 28/E/KPT/2019
Hasil pengujian pada tabel 4. memperlihatkan bahwa algoritma ini menghasilkan nilai yang rata- rata berbeda setiap kali melakukan pencarian rute. Hal ini disebabkan oleh pencarian rute  algoritma ACS  dilakukan  berdasarkan  probabilitas  atau  peluang.  Waktu  eksekusi  pada  algoritma  ini  juga cenderung  lebih  lama  jika  kasus  yang  diselesaikan  merupakan  kasus  yang  memiliki  banyak  titik. Semakin  banyak  titik  yang  akan  diselesaikan  maka  semakin  lama  waktu eksekusi proses  pencarian rute dan sebaliknya.

## 4.  Kesimpulan dan Saran

## 4.1. Kesimpulan
Dari  hasil  pembuatan  sistem  dapat  disimpulkan  bahwa  sistem  penentuan  rute  pendistribusian produk air mineral menggunakan algoritma Ant Colony System (ACS) dapat menghasilkan rute terbaik untuk mendistribusikan produk air mineral dari lokasi perusahaan menuju lokasi seluruh pelanggan di kota  Palu.  Sistem  ini  dapat  membantu  perusahaan  untuk  meminimalkan  jarak  tempuh driver dalam melakukan pendistribusian dengan jarak yang minimal.
Hasil  penelitian  algoritma  ACS  menunjukan  bahwa  ukuran  kasus  TSP  berpengaruh  pada  waktu eksekusi  algoritma  ACS.  Selain  itu,  penentuan  nilai  parameter  (qo, ,  ,  ,  jumlah  semut  dan jumlah  siklus  semut/iterasi)  untuk  setiap  kasus  pada  algoritma  ACS  sangat  berpengaruh  pada  rute yang  akan  dihasilkan  karena  hal  ini  merupakan  bagian  penting  untuk  melakukan  tahapan  algoritma ACS yang meliputi transisi status, pembaruan pheromone lokal dan pembaruan pheromone global. 4.2. Saran
Berdasarkan  kesimpulan  penelitian,  maka  penulis  merekomendasikan  berupa  saran  untuk membangun  sebuah  sistem  analisis  pemilihan  parameter  ACS  yang  tepat  untuk  setiap  kasus  yang berbeda-beda.

## Daftar Pustaka
[1]  Amalia,  R. “ Pencarian  Jalur  Terpendek  Menggunakan  Ant  Colony  System  (Kasus:      Pariwisata Kota Bogor) ” , Faktor Exacta 8(4): 290-304, Vol 8, No 4 2015.
[2]  Gunawan, A. S. Sipayung, E. M. dan Wiguno, A. “ Perancangan Sistem Informasi Penentuan Rute Pengiriman  Barang  Dengan  Metode  Ant  Colony  Optimization  Studi  Kasus:  PT.  XYZ ” ,  Seminar Nasional Sistem Informasi Indonesia, 2-3 November 2015.
[3]  Tutupary, F. S. Talakua, M. W. dan Lesnussa, Y. A. “ Aplikasi Algoritma Ant Colony System Dalam Penentuan Rute Optimum Distribusi BBM Pada PT. Burung Laut ” , Jurnal Barekeng Vol.8,  No.1 2014.
[4]  Wardhani,  N. “ Optimisasi  Traveling  Saleseman  Problem  (TSP)  Menggunakan  Algoritma  Semut ” , Jurnal IT STMIK Handayani, Vol 15, Desember 2014.
[5]  Farisi,  O.  I.  R.  dan  Pratamasunu,  G.  Q.  O. “ Penyelesaian  Multi-Depot  Multiple  Traveling Salesmanproblem  menggunakan  K-Means  dan  Ant  Colony  Optimization ” ,  Nusantara  Journal  of Computersand its Applications, Vol 2, No.5 2016.
[6]  A.A.  Ismail,  S.  Herdjunanto,  Priyatmadi. “ Penerapan  Algoritma  Ant  System  dalam  Menemukan Jalur  Optimal  pada  Traveling  Salesman  Problem  (TSP)  dengan  Kekangan  Kondisi  Jalan ” . JNTETI, Vol. 1, No. 3 2012.
[7] R. H. Nugroho . “ Ant Colony System Algorithm to Solve Multi Depot Vehicle Routing Problem with Travel Time Variable ” . Tesis Institut Teknologi Sepuluh Nopember 2015 [8]  K.  Nugroho. “ Penggunaan  Algoritma  Semut  Untuk  Penentuan  Optimisasi  Jalur  Tim  Marketing ” . Jurnal INFOKAM September 2015.
[9]  P . Victor , SN.  Azhari . “ Ant  Colony  Optimization  on  Crowdsourced  Delivery  Trip  Consolidation ” . IJCCS (Indonesian Journal of Computing and Cybernetics Systems) . Vol.11, No.2, July 2017.