## Ant Colony  Optimization untuk Menyelesaikan Perutean Distribusi  Snack  dengan Vehicle Routing Problem
Endang Setyati Departemen Teknologi Informasi
Institut Sains dan Teknologi Terpadu Surabaya
Surabaya, Indonesia endang@stts.edu Ine Juniwati Departemen Teknologi Informasi Institut Sains dan Teknologi Terpadu Surabaya Surabaya, Indonesia inejuniwati2019@gmail.com
Abstrak— One of the challenges faced by Small and Medium Industries (IKM) in their production marketing support  activities  is  the  problem  of  transportation. Transportation  of  goods  and  services  is  an  important topic  that  attracts  the  attention  of  the  business  world today.  And  things  that  are  closely  related  to  the transportation  sector,  namely  the  Vehicle  Routing Problem  (VRP)  or  routing  problems.  The  VRP  variant used  in  this  study  is  the  Capacity  Vehicle  Routing Problem  (CVRP)  which  uses  the  capacity  limit  of  the vehicles  used.  CVRP  is  used  to  minimize  goods distribution  channels  at  IKM  Jajan  FITRIA  located  in Sidoarjo.  The  distribution  problem  at  IKM  Snack FITRIA is how to effectively manage the route of delivery of goods from the warehouse to several stores/customers spread  across  various  locations  in  Surabaya,  Sidoarjo and Gresik. This study includes route planning for each vehicle when delivering products to consumers who are scattered  at  several  points  originating  from  the  same warehouse.  Vehicles  deliver  goods  from  warehouse  to customer  in  one  day  in  one  shipment.  So  far,  the  Ant Colony  Optimization  (ACO)  algorithm  is  being  used. ACO is used because it can show the best route for the 95% optimal solution.
Keywords—VRP;  CVRP;  ACO;  Optimization;  Ant Colony
Abstrak- Salah satu tantangan yang dihadapi Industri Kecil  Menengah  (IKM)  pada  aktivitas  penunjang pemasaran  produksinya  adalah  masalah  transportasi. Transportasi barang dan jasa merupakan topik penting yang   menarik  perhatian dunia  usaha  saat ini.  Dan hal yang  berkaitan  erat  dengan  bidang    transportasi  yaitu Vehicle  Routing  Problem  (VRP)  atau  permasalahan perutean. Varian VRP yang digunakan dalam penelitian ini  adalah  Capacity  Vehicle  Routing  Problem  (CVRP) yang memanfaatkan kendala kapasitas kendaraan yang digunakan. CVRP digunakan untuk meminimalkan rute distribusi produk di IKM Snack FITRIA yang berlokasi di  Sidoarjo.  Masalah  pendistribusian  di  IKM  Snack FITRIA adalah bagaimana mengatur secara efektif rute pengiriman barang dari gudang ke beberapa toko/pelanggan  yang  tersebar  di  berbagai  lokasi  di Surabaya,  Sidoarjo  dan  Gresik.  Dalam  penelitian  ini meliputi  perencanaan  rute  setiap  kendaraan  pada  saat pengiriman  produk  ke  konsumen  yang  tersebar  di beberapa  titik  yang  berasal  dari  gudang  yang  sama. Transportasi dalam satu hari mengirimkan barang dari gudang  ke  pelanggan  dengan  satu  pengiriman.  Sejauh
ini,  algoritma  Ant  Colony  Optimization  (ACO)  yang digunakan. ACO digunakan karena dapat menunjukkan 90%  jalur  solusi  optimal  terbaik.  Dan  dapatkan  total jarak tempuh minimum dengan varian rendah.
Kata  kunci—  VRP;  CVRP;  ACO;  Optimasi;  Ant Colony.

## PENDAHULUAN
Dilihat  dari  perkembangan  saat  ini,  IKM  sudah memiliki data yang tersimpan secara sederhana dalam pengelolaan  usahanya,  salah  satunya  adalah  data distribusi  barang.  Dan  permasalahan  yang  dihadapi adalah  distribusi  dengan  kapasitas  kendaraan  yang terbatas.  Oleh  karena  itu,  diperlukan  sistem  routing (peruteaan)  yang  optimal  yang  membuat  distribusi menjadi  sangat  efisien.  Saat  menentukan  rute distribusi,  dikenal  dengan  Vehicle  Routing  Problem (VRP).
VRP  merupakan  masalah  optimasi  kombinatorial untuk  menentukan  rute  yang  dapat  diterapkan  pada mekanisme  distribusi  komoditas.  Varian  VRP  yang digunakan  dalam  penelitian  ini  adalah  Capacity Vehicle Routing Problem (CVRP) yang menggunakan batasan kapasitas kendaraan yang digunakan. Menggunakan  algoritma  Ant  Colony  Optimization (ACO) untuk menentukan jarak terdekat. Namun jarak bukanlah satu-satunya faktor yang berpengaruh untuk menentukan rute perjalanan. Oleh karena itu, penelitian ini  bertujuan  untuk  melengkapi  kekurangan  pada penelitian sebelumnya dengan menambahkan variabel lain dalam lingkup CVRP. Dan untuk lebih memahami istilah-istilah  dalam  penelitian  ini,  kami  berikan beberapa penjelasan.
IKM  merupakan  sektor  mayoritas  atau  yang mendominasi  dari  jumlah  populasi  industri  di Indonesia.  Pemerintah  berperan  aktif  mendorong pelaku IKM untuk mampu meningkatkan produksinya lebih  optimal  khususnya  di  tengah  era  digital  dan pandemi  ini.  IKM  Snack  FITRIA  yang  berlokasi  di Sidoarjo  dan  memproduksi  jajanan  “Snack  Almond Crispy” yang memiliki 4 varian rasa dengan kemasan yang sama.  Memiliki beberapa kendaraan pengangkut dengan  kapasitas  tertentu.  Mengalami  kesulitan  pada pengaturan  rute  untuk  setiap  kendaraan.  Karena kurangnya penjadwalan rute yang optimal pada setiap
kendaran pengangkut menyebabkan kurangnya efisiensi jarak tempuh dan waktu.
Pada  penelitian  Wan  Amir  Fuad  Wajdi  Othman, Aezaal Azman Abd Wahab, Syed Sahal Nazli Alhady, Haw  Ngie  wong  (2018)  tentang  penerapan  algoritma ACO guna memecahkan VRP. Bahwa parameter yang berpengaruh yaitu jumlah semut (nAnt), alpha (α), beta (β) dan rho (ρ). Dengan parameter semut = 20, alpha= 1, beta= 1 dan rho= 0,05 didapat rute optimal[2]. Tetapi pada penelitian ini tidak diterangkan lebih detail varian VRP yang digunakan.
Penelitian  Ibrahim  A.A,  Lo  N.,  Abdulaziz  R.O, Ishaya J.A (2019) tentang  pengembangan teknik dalam penentuan  jalur  optimal  dari  depot  ke  pelanggan dengan  mempertimbangkan  kapasitas  kendaraan. Dengan  asumsi  dasar  bahwa  setiap  kendaraan mengawali  perjalanan  dari  depot  kemudian  ke pelanggan  dengan  kendaraan  yang  homogen.  Dalam penelitian  ini  CVRP  diselesaikan  dengan  beberapa metode  yaitu:  Column  Generation  (CG),  Google Operation  Research  Tool    (Google  OR-Tool),  dan Reinforcement Learning (RL) dengan membandingkan masing-masing  hasil.  Dan  hasilnya  dari  penelitian secara  komputasi  RL  lebih  unggul  dari  Google  OR- Tools[8].  Penelitian  Modhi  Lafta  Mutara,  M.A. Burhanuddin, Asaad Shakir Hameed, Norzihani Yusof and  Hussein  Jameel  Mutashar  (2020)  tentang penggunaan  Sistem  Ant  Colony  (ACS)  untuk mengatasi permasalahan distribusi dengan target untuk mengurangi  jarak  dan  sebagai  referensi  baru  untuk algoritma ACS [7].
Maka  pada  penelitian  ini  akan  menerapkan  ACO pada  CVRP  untuk  menghasilkan  rute  optimal  pada distribusi  jajanan  “Snack  Almond  Crispy”.  Tujuan perutean  optimal  tersebut  adalah  agar  distribusi  yang dilakukan  dapat  menjadi  efisien  baik  dari  segi  jarak maupun  waktu.  Sehingga  semua  pelanggan  dapat terlayani  secara  maksimal.  Pada  penelitian  ini  ada beberapa  hal  yang  menjadi  batasan,  antara  lain  : kendaraan  box  yang  digunakan  sebagai  pengangkut dengan  dimensi  :  dalam=  2.510mm,  lebar=1.680mm, dan tinggi=1.680mm. Jajanan tersebut dikemas dalam tabung  berukuran  :  tinggi  =15  cm  dan  diameter  =  8 cm.  Permintaan  konsumen  yang  bervariatif  telah tercatat dan setiap pelanggan hanya dikunjungi dengan satu kali.

## Optimasi
Menurut  Brogran  (1991),  optimasi  adalah  suatu proses  yang  ditujukan  untuk  mencapai  hasil  yang optimal atau ideal (nilai efektif tercapai). Optimalisasi intuitif  melakukan  pekerjaan  dengan  cara  terbaik. Sedangkan  menurut  Licker  (2003),  optimasi  berasal dari kata  bahasa  Inggris “optimization”, yang berarti meminimalkan  atau  memaksimalkan  suatu  fungsi dengan  beberapa  macam  kendala.  Masalah  optimasi mengacu  pada  studi  masalah  yang  mencoba  mencari nilai maksimum atau minimum dari suatu fungsi real. Berdasarkan  beberapa  nilai  yang  telah  dijelaskan, dapat  diartikan  bahwa  optimasi  adalah  proses
pencapaian  nilai  minimum  atau  maksimum  dari beberapa  fungsi  tujuan  dengan  mempertimbangkan beberapa kendala yang diberikan.

## Vehicle Routing Problem (VRP)
VRP  pertama  kali  diperkenalkan  oleh  George Dantzig dan John Ramser pada tahun 1959 [13]. VRP merupakan simulasi permasalahan transportasi dalam menentukan  sistem  distribusi  yang  digambarkan sebagai  model  graf  dengan  banyak  pilihan  untuk menemukan rute terbaik.  Untuk mengirimkan produk ke sejumlah pelanggan sesuai permintaan di beberapa lokasi  berbeda  dengan  menggunakan  beberapa kendaraan.
VRP  merupakan  evolusi  dari  Travelling  Salesman Problem  (TSP)  yang  merupakan  permasalahan optimasi rute yang klasik. Dalam masalah ini, satu atau lebih kendaraan berjalan melalui jaringan, meninggalkan  dan  kembali  ke  simpul  depot.  Setiap pelanggan harus dikunjungi oleh satu mobil dalam satu kali. Pelanggan biasanya terletak di simpul jaringan.

## Capacitated Vehicle Routing Problem (CVRP)
CVRP  merupakan  salah  satu  bentuk  VRP  yang memiliki kendala pada daya dukung suatu kendaraan. Masalah  ini  termasuk  dalam  masalah  optimisasi kombinatorial  kompleks  yang  termasuk  dalam kategori  NP-Hard.  Ini  adalah  permasalahan  yang membutuhkan perhitungan yang rumit. Juga merupakan optimasi kombinatorial pada pendistribusian barang antara gudang dan pelanggan. Ini penting secara ekonomi dalam bisnis karena sekitar 10-20%  dari  harga.  Barang  dipengaruhi  oleh  proses pengangkutan, terutama dalam biaya penanganan. .
CVRP dirancang untuk mendistribusikan barang ke sekelompok  pelanggan  dengan  pengiriman  sesuai dengan permintaan yang diketahui. Tujuan dari CVRP adalah  untuk  mengurangi  total  biaya  perjalanan dengan menggunakan fungsi pembobotan dari jumlah kendaraan  dan  jarak  yang  ditempuh  oleh  kendaraan dalam  melayani  sekumpulan  pelanggan  dengan permintaan yang telah diketahui. Rute harus dibangun sedemikian  rupa  sehingga  semua  pelanggan  pada simpul  dikunjungi  satu  kali  dan  hanya  oleh  satu kendaraan.  Ada  beberapa  persyaratan  dalam  CVRP, yaitu:
− Semua informasi permintaan pelanggan diidentifikasi sebelumnya,
− Armada homogen yang berasal dari satu depo,
− Setiap  pesanan  tidak  dapat  dibagi  atau  dilayani oleh lebih dari satu kendaraan.

## Graf (Peta) Hamilton
Lintasan  Hamilton  adalah  lintasan  yang  melalui setiap titik pada graf tepat satu kali. Rantai Hamilton adalah rantai yang melalui setiap titik dalam graf tepat satu  kali,  kecuali  titik  asal  (serta  titik  akhir)  yang melalui  dua  kali.  Graf  yang  memiliki  lintasan Hamiltonian disebut graf Hamiltonian, sedangkan graf yang  hanya  memiliki  lintasan  Hamiltonian  disebut
graf semi-Hamiltonian.
Gambar. 1. Menggambar grafik berdasarkan jalur: (1) graf Hamilton, (2) graf semi-Hamilton, (3) graf non-Hamilton
Ant Colony Optimization (ACO) ACO adalah teknik metaheuristik dengan pendekatan  populasi  yang  terinspirasi  oleh  koloni semut. Pertama kali diusulkan oleh Dorigo dkk untuk memecahkan beberapa masalah optimisasi diskrit [4]. ACO adalah salah satu teknik pengoptimalan ramalan yang  meniru  sistem  komunikasi  koloni  semut,  yang meninggalkan bahan kimia yang disebut feromon pada rute  perjalanannya  sebagai  jejak.  Feromon  adalah senyawa  kimia  hidrokarbon  yang  berguna  untuk interaksi dalam ekosistem dan berperan penting dalam sistem komunikasi semut.
Setiap  semut  memulai  perjalanannya  melalui  titik yang  dipilih  secara  acak.  Perjalanan  dilakukan berulang  kali,  semut  mengunjungi  satu  per  satu  titik yang ada guna menyusun rute perjalanan. Pilihan titik yang akan dilewati didasarkan pada fungsi probabilitas yang  disebut  aturan  transisi  keadaan,  dengan mempertimbangkan visibilitas atau jarak timbal balik dari titik dan jumlah feromon yang ada pada segmen yang  menghubungkan  titik.  Semut  yang  menemukan sumber  makanan  meninggalkan  feromon  dalam perjalanan kembali ke koloninya.
Semut lain yang mencium feromon di sepanjang rute akan  cenderung  mengikuti  rute  tersebut  jika kandungan  feromon  cukup  padat.  Semakin  padat kandungan feromon pada rute tersebut. Semakin besar kemungkinan  semut  lain  akan  mengikuti  rute  ini. Feromon menguap dari waktu ke waktu. Rute pendek akan mengandung feromon yang cukup padat, karena waktu  yang  dihabiskan  untuk  pergi  atau  setiap  kali mereka  kembali  ke  koloninya,  semut  selalu meninggalkan  feromon.  Jika  dari  koloni  ke  sumber makanan  berkurang,  penguapan  feromon  akan minimal.
Jejak  feromon  akan  hilang  seiring  waktu.  Untuk antrean  panjang.  Jejaknya  akan  mulai  hilang  karena jarang dilalui. Sedangkan untuk jalur pendek jalurnya akan  memiliki  kepadatan  feromon  yang  tinggi  dan akan  membuat  jalur  tersebut  dapat  dipilih.  Dan  jauh akan ditinggalkan.
Dengan  demikian,  dapat  dikatakan  bahwa  semut menggunakan lingkungan sebagai sarana komunikasi. Mereka  bertukar  informasi  secara  tidak  langsung melalui  feromon  mereka.  Sistem  ini  disebut "stigmergy". Sistem ini didasarkan pada 2 (dua) input, yang  terdiri  dari  input  positif  dan  input  negatif. Kontribusi positif : menarik feromon semut lain yang
akan  memperkuat  diri.  Sedangkan  input  negatif  : hamburan  sepanjang  jalur  sistem,  yang  mencegah penguapan. Sistem stigma dapat digambarkan sebagai berikut:

## Gambar 2. Bentuk komunikasi stigmergy pada Ant
Colony Optimization [1]
Gambar  2A  di  atas  menunjukkan  bahwa  ada  dua kelompok  semut  yang  akan  melakukan  perjalanan. Kelompok “L” adalah yang berangkat dari kiri sarang semut.  Dan  “R”,  yang  beranjak  dari  kanan  sumber makanan.  Keduanya  berangkat  dari  titik  awal  dalam kondisi  pemilihan  jalur.  Kemudian  kelompok  “L” dibagi  menjadi  dua  kelompok.  Kelompok  melalui garis  atas,  dan  yang  melalui  garis  bawah,  yang  juga berlaku untuk kelompok “R”.
Gambar 2B dan 2C menunjukkan bahwa sekelompok  semut  berjalan  dengan  kecepatan  yang sama, meninggalkan feromon di rute yang dilaluinya. Feromon yang ditinggalkan semut yang melewati rute atas  menguap  dengan  cepat.  Karena  lebih  sedikit semut yang melewati rute atas daripada rute bawah. Ini dipengaruhi oleh jarak yang ditempuh. Jarak dari rute atas  lebih  besar  daripada  rute  bawah.  Sedangkan feromon  yang  berada  pada  rute  bawah  penguapan lebih  rendah.  Karena  lebih  banyak  semut  yang melewati rute bawah daripada garis atas.
Gambar  2D  menunjukkan  bahwa  semut  lainnya akhirnya memutuskan untuk mengikuti jejak tersebut. Karena  masih  banyak  feromon  yang  tersisa. Sedangkan  feromon  di  rute  atas  sudah  banyak menguap,  sehingga  semut  tidak  memilih  rute  atas. Semakin banyak semut yang berjalan di rute tersebut, semakin  banyak  pula  semut  yang  mengikutinya. Begitu  pula  dengan  rute  atas:  semakin  sedikit  semut yang melewati rute atas, semakin sedikit feromon yang tersisa  dan  bahkan  menghilang.  Dari  sini,  rute terpendek antara sarang dan sumber makanan dipilih.
Artinya semakin banyak semut yang mengikuti rute tersebut  maka  akan  semakin menarik  untuk  dilewati. Probabilitas  seekor  semut  memutuskan  untuk mengikuti suatu rute meningkat dengan jumlah semut yang menggunakan jalur tersebut terlebih dahulu. Jadi, algoritma koloni semut adalah sebagai berikut: 1. Awalnya, semut berjalan secara acak.
2. Saat semut menemukan rute yang berbeda, seperti tiba di persimpangan jalan, mereka mulai memilih arah secara acak.
3. Beberapa semut lebih suka naik dan beberapa lebih
suka turun.
4. Ketika  mereka  menemukan  makanan,  mereka kembali ke koloni mereka, memberi isyarat dengan jejak feromon.
5. Karena  rute  yang  dilalui  adalah  rute  bawah  yang lebih  pendek,  semut  bawah  akan  tiba  lebih  dulu, dengan asumsi kecepatan semua semut sama.
6. Feromon yang ditinggalkan semut pada rute yang lebih pendek akan memiliki aroma yang lebih kuat daripada feromon pada rute yang lebih panjang.
7. Semut  lain  akan  lebih  tertarik  mengikuti  jejak  di bawahnya karena aroma feromonnya lebih kuat.

## METODE PENELITIAN
Bagian  ini  membahas  tentang  penerapan  algoritma ACO  untuk  menyelesaikan  permasalahan  perutean kendaraan  pada  pendistribusian  jajanan  “Snack Almond Crispy”. Pada Gambar 3 menunjukkan bagan alur umum dari metodologi penelitian ini.:
Gambar 3. Blok diagram sistem metodologi
Data  yang  diberikan  IKM  dari  data  sebaran  yang diperoleh  IKM  selama  ini.  Data  tersebut  meliputi: jenis pesanan (tipe rasa snack), jumlah pesanan snack, alamat  pelanggan/pelanggan,  dan  moda  transportasi yang  digunakan.  Untuk  menyelesaikan  masalah routing pada penelitian ini dilakukan dalam beberapa tahapan, tahapan tersebut adalah :

## 1. Algoritma ACO.
Dalam ACO dibagi menjadi dua tahap utama yaitu tahap  semut  yang  Membangun  rute,  dan  tahap memperbarui  feromon  [3].  Pada  tahap  pertama  yaitu tahap  membangun  rute.  Dalam  hal  ini,  semut  dipilih secara  bersamaan  dalam  n  jaringan  pada  simpul pelanggan  (termasuk  depot/gudang  utama).  Pada
setiap  langkah  membangun  semut  k  yang  saat  ini berada  di  simpul  i,  aturan  probabilitas  proporsional acak diterapkan untuk memutuskan simpul mana yang akan  dipindahkan  berikutnya.  Hal  ini  merupakan langkah dalam memilih rute dengan dua nilai. Yakni, fungsi heuristic  ij dan level feromon pada titik (i,j), dilambangkan dengan τij.  ij adalah panjang sisi dari simpul  i  ke  simpul  j.  Dan  τij  menunjukkan  jumlah feromon pada sisi dari simpul i ke simpul j. Dan untuk mendapatkan  lintasan  rute  digunakan  beberapa persamaan yaitu :
• Pembangunan Rute:
Semut akan bergerak dari simpul i ke simpul j dengan persamaan probabilitas:
𝑝 𝑖,𝑗 = (𝜏𝑖,𝑗 𝛼 )(  𝑖,𝑗 𝛽 ) 𝛴(𝜏𝑖,𝑗 𝛼 )(  𝑖,𝑗 𝛽 ) (1)
dimana α =  parameter  yang  mempengaruhi  kontrol terhadap  τij τij =  jumlah feromon di sisi I dan j i =   1,2,3,…..,n j =   1,2,3,…..,k ηij =  nilai keselarasan sisi i,j, dengan perhitungan  :  1/d i ,j ,  di  mana  d  adalah jarak. β =  parameter  yang  mempengaruhi  control terhadap η i ,j
Pada tahap ini yaitu pembangunan rute, k semut yang berada di simpul i berpindah ke simpul n, dipilih sesuai dengan persamaan di atas. Kemudian, setelah k semut pindah  ke  simpul  berikutnya,  simpul  baru  beralih  ke simpul  i,  dan  simpul  baru  menjadi  n,  yang  dipilih kembali sesuai dengan aturan probabilitas proporsional acak, simpul hanya akan melewati tahap ini satu kali.
Pada  tahap  kedua,  pembaruan  feromon  ACO  yang sangat  berperan  untuk  mencapai  solusi  optimal. Persamaan  pemulihan  feromon  dirancang  untuk merangsang  perubahan  jumlah  feromon  baik  karena akumulasi feromon baru yang disimpan oleh semut di tepi yang dikunjungi, dan karena penguapan feromone [4].  Algoritma  ACO  menggunakan  dua  jenis pembaruan feromon, yaitu pembaruan feromon global dan  pembaruan  feromon  loka,  yang  menggunakan  2 persamaan berikut:
• Pembaruan Feromon Lokal:
τ(i,j)baru ← (1 – ρ). τ(i,j)tua + ρ. t 0 (2)
di mana :
τi,j   =  jumlah feromon pada sisi i,j ρ = parameter  yang  mewakili  feromon  dengan penguapan lokal yang bernilai dari 0 sampai 1 (0< ρ < 1)
τ0   = (jumlah awal feromon) =
1/ (jarak awal*jumlah kotak)
Parameter  ρ  akan  menentukan  jumlah  penguapan feromon  pada  sisi  yang  baru  saja  dikunjungi  semut. Semakin  besar  nilai  ρ-nya,  maka  semakin  besar pengurangan  jumlah  feromon.  Jadi  rute  semut  akan cepat konvergen pada rute tertentu.
Dengan  pembaruan  lokal,  jumlah  feromon  di  sisi yang baru dikunjungi berkurang. Sehingga kemungkinan dipilihnya sisi ini oleh semut lain pada langkah  iterasi  yang  sama  berkurang.  Akibatnya, semut tidak pernah konvergen pada sisi tertentu saja, dan  semut  lebih  memilih  sisi  yang  belum  pernah dikunjungi.  Pada  saat  semut  telah  menyelesaikan semua    perjalanannya.  Jumlah  feromon  di  setiap  sisi diubah  dengan  menerapkan  pembaruan  foremon global sesuai dengan persamaan berikut:
• Pembaruan Feromon Global :
τ(i,j) ← (1 – ρ). τ(i,j) + ρ. 1 Lgb (3)
di mana:
τi,j   =   jumlah feromon pada sisi i,j
R =  parameter  yang  mewakili penguapan feromon  global;  yaitu  antara  0  dan  1 (0<ρ<1)
Lgb  =   jarak  terpendek  dari  awal  iterasi  ke  iterasi saat ini.
Pembaruan  global  dirancang  untuk  mengurangi jumlah  feromon  di  semua  sisi  sebesar  ρ.  Kemudian tambahkan jumlah feromon pada sisi rute dengan jarak terpendek.  Parameter  ρ  pada  persamaan  3  untuk menentukan  jumlah  penguapan  feromon.  Semakin besar  nilai  ρ,  semakin  besar  penguapan  feromon. Penguapan  feromon  yang  terlalu  banyak  akan menyebabkan  perjalanan  semut  cepat  mencapai kesimpulan yg konvergen pada rute tertentu.

## 2. Menentukan Parameter Kontrol Algoritma ACO
Masalah optimasi dalam penelitian ini dipengaruhi oleh    4  (empat)  parameter  kontrol  yang  berbeda  dan dapat mempengaruhi output dari algoritma, algoritma akan  dievaluasi  sesuai  dengan  kombinasi  yang berbeda dari parameter ini. Parameter tersebut  dapat dilihat pada Table 1.
Tabel I. PENGATURAN PARAMETER
Parameter Pengaturan Semut 5; sepuluh
alfa (α) 0,1; satu beta (β) 2.25; empat ro (ρ) 0,5; 0,5
Tabel 1 menunjukkan pengaturan parameter kontrol yang  digunakan  untuk  mengevaluasi  kinerja  dan output dari algoritma.
3. Clustering  data  kapasitas  kendaraan  untuk memecahkan masalah perutean CVRP
Clustering  adalah  teknik  pengelompokkan  data kedalam beberapa kelas cluster berdasarkan karakteristik yang sama, sehingga setiap kelas cluster memiliki karakteristik yang berbeda dengan yang lain. Dan  untuk  menentukan  jumlah  kelas  cluster  yang optimal  pada  setiap  rute  di  kumpulan  data  pada penelitian  ini.  Yaitu  dengan  menerapkan  metode indeks  validitas,  dimana  jika  pada  uji  validitas memberikan  nilai  yang  lebih  rendah  maka  dapat dikatakan bahwa jumlah cluster yang digunakan lebih baik.

## HASIL PEMBAHASAN
Program  pencarian  rute  yang  dikembangkan  dapat memberikan  tingkat  optimalisasi  hasil  output  dan dapat digunakan sebagai referensi dalam pengambilan keputusan.  Pengujian  dilakukan  dengan  melakukan perubahan  nilai  parameter  alpha  dan  beta,  karena kedua  parameter  tersebut  berperan  dalam  mengubah hasil pencarian rute terbaik selama 100 iterasi.
Berikut  ini  adalah  skenario  pengujian  yang  akan dijalankan pada simpul data alamat pelanggan di setiap kendaraan:
a. Skenario  1  :  Perubahan  menggunakan  parameter alpha (α) dengan nilai = 0,1; 1 dan 5.
b. Skenario  2  :  Perubahan  parameter  beta  (β) digunakan dengan nilai = 2,25; 4 dan 8.
Hasil  pengujian  satu  kendaraan  pada  data  semua simpul  alamat  pelanggan  untuk  menentukan  jarak dengan nilai alpha (α) = 0,1 dan beta (β) = 2,25 dapat dilihat pada Tabel 2 :

## Tabel II. MATRIKS JARAK 1
Simpul 1 2 3 4 5 6 7 1 - 17,5 7,2 6,4 17,6 14,6 5,9 2 17,5 - 29,5 24,7 2,9 38,7 17,5 3 7,2 29,5 - 5,0 27,7 15,8 14,7 4 6,4 24,7 5,0 - 27,2 11,8 11,4 5 17,6 2,9 27,7 27,2 - 38,5 21,2 6 14,6 38,7 15,8 11,8 38,5 - 23,0 7 5,9 17,5 14,7 11,4 21,2 23,0 -
Pada  Tabel  2  terlihat  dengan  menggunakan parameter  alpha  (α)  =  0,1  dan  beta  (β)  =  2,25 menghasilkan jarak dengan tampilan matriks. Simpul
mewakili  alamat  pelanggan.  Jarak  dari  simpul  1  ke simpul 2 adalah = 17,5 km begitupun jarak dari simpul 2  ke  simpul  1.  Yang  berarti  dari  depo  awal  ke pelanggan  1  berjarak=17,5km.  Simpul  1  ke  simpul 3 berjarak=7,2  km,  yang  berarti  dari  depo  awal  ke pelanggan 3 berjarak=7,2km. Dan seterusnya.
Sementara itu, hasil pengujian satu kendaraan pada data  semua  simpul  alamat  pelanggan  untuk menentukan jarak dengan nilai alpha (α) = 1 dan beta (β) = 4 dapat dilihat pada Tabel 3.

## TABEL III. MATRIKS JARAK 2
Simpul 1 2 3 4 5 6 7 1 - 23,0 26,3 5,5 20,9 2,1 9,6 2 23,0 - 2,2 11,1 2,1 13,0 13,7 3 26,3 2,2 - 12,3 3,9 15,0 11,3 4 5,5 11,1 12,3 - 3,3 4,1 7,6 5 20,9 2,1 3,9 3,3 - 15,0 18,1 6 2,1 13,0 15,0 4,1 15,0 - 9,5 7 9,6 13,7 11,3 7,6 18,1 9,5 -
Pada  Tabel  3  terlihat  dengan  menggunakan parameter alpha (α) = 1 dan beta (β) = 4 menghasilkan jarak  dengan  tampilan  matriks.  Simpul  mewakili alamat  pelanggan.  Jarak  dari  simpul  1  ke  simpul  2 adalah  =  23  km  begitupun  jarak  dari  simpul  2  ke simpul 1. Yang berarti dari depo awal ke pelanggan 1 berjarak=23 km. Simpul 1 ke simpul 3 berjarak=26,3 km,  yang  berarti  dari  depo  awal  ke  pelanggan  3 berjarak=26,3 km. Dan seterusnya.
Penentuan jarak ini akan digunakan pada clustering data  pelanggan  berdasarkan  kapasitas  kendaraan  dan permintaan pelanggan.

## Menampilkan hasil visualisasi referensi rute
a. Hasil  pengujian  satu  kendaraan  pada  semua  data simpul  alamat  pelanggan  untuk  penentuan  jarak dengan alpha (α) = 0.1 dan beta (β) = 2.25 seperti pada Gambar 4.
Gambar 4. Hasil Uji 1
b. Hasil pengujian satu kendaraan dari semua simpul alamat  pelanggan  untuk  penentuan  jarak  dengan alpha (α) = 1 dan beta (β) = 4, seperti terlihat pada Gambar 5.

## Gambar 4. Hasil Uji 1

## Hasil referensi rute
Berdasarkan  hasil  yang  diperoleh  dari  pencarian rute  optimal  yang  diuji  sebelumnya,  diperoleh rekomendasi  baru  untuk  rute  dengan  jarak  yang berbeda, seperti terlihat pada tabel 4 :

## TABEL IV. PERBANDINGAN JARAK ANTARA
RUTE LAMA DAN MANUAL rute lama Rute baru 672 km 445 km Selisih jarak = 227 km
Berdasarkan  Tabel  4,  total  selisih  jarak  antara  jalur lama  dan  jalur  baru  adalah  227  km.  Tampilan rekomendasi rute baru tersebut adalah sebagai berikut:
0. PUSAT DEPO - Dermaga LCD blok c No.3; taman – Sidoarjo
54.  SENYUEN  WAKTU  -  Jl.  Tanggal  V  No.  78, Tanggal, Keck. Gajungan, Surabaya
42.  Toserba  Palapa  -  Jl.  Adityawarman  No.55, Savungaling, Kek. Wonokromo, Surabaya
91.  Wisata  Mencicipi  -  Jl.  Basuki  Rahmat  No.76, Tegalsari, Surabaya
97.  Wisata  selera  -  Embong  Kalyasin,  Kek.  Ubin, Surabaya
64.  Toko  67  -  Zhl.  Genteng  Besar  No.67,  Genteng, Kek. Ubin, Surabaya
44. Panen Raya - Jl. Genteng Besar No.77 A, Genteng Surabaya
3.  Bhek  Putra  -  Jl.  Genteng  Besar  No.75,  Genteng, Surabaya
90.  Wisata  Mencicipi  -  Jl.  Genteng  Besar  No.83A, Genteng, Surabaya
57. Silakan masuk - Zhl. Genteng Besar No. 72 - 74, Genteng, Surabaya
83.  Transmart  -  Jl.  Ngagel  No.  137  -  141,  Ngagel, Keck. Wonokromo, Surabaya
95.  Wisata  Mencicipi  -  Jl.  Raya  Jemursari  No.164, Jemur Wonosari, Tengilis Mejoyo, Surabaya
12.  Supermarket  Chicco  -  st.  Raya  Tengilis  No.82, Tengilis Mejoyo, Kek. Tengilis Mejoyo, Surabaya
55.  Ulem  fiber  sangat  cocok  untuk  lipat  WO  -  Jl. Melenturkan sel Merisi. Airdas, Bendul Merisi, Keck. Wonolo, Surabaya

## Analisis hasil tes
− Berdasarkan hasil pengujian dengan menggunakan skenario  variasi  alpha  dan  beta,  didapatkan  hasil yang paling optimal diperoleh dengan menggunakan nilai alpha sebesar 0,8 dan nilai beta sebesar 4 yang memberikan hasil runtime tercepat. Namun,  hal  ini  tidak  membuat  perbedaan  hasil jarak, karena jumlah simpul masukan untuk alamat klien masih kecil.
− Menggunakan metode ACO dan selisih nilai alpha dan beta, efisiensi jarak yang diperoleh adalah 227 km.
− Pendistribusian  produk  yang  dilaksanakan  oleh IKM berlandaskan konsep “one car for one store”, pengiriman dalam waktu satu hari.

## KESIMPULAN
Dari  kajian  yang  telah  dilakukan  oleh  peneliti selama  melakukan  penelitian  ini,  ada  beberapa kesimpulan  yang  dibuat  oleh  peneliti.  Bahwa Algoritme  ACO  dapat  membuat  cluster  yang  cukup baik untuk solusi CVRP dan membuat rute distribusi yang  optimal  dan  efisien.  Nilai  parameter  alpha  dan beta  sangat  berpengaruh  dalam  mengubah  hasil pencarian  rute  terbaik  terutama  pada  perhitungan jarak.  Jumlah  iterasi  yang  digunakan  memiliki pengaruh  yang  signifikan,  semakin  besar  jumlah iterasi  yang  digunakan  maka  semakin  mendekati solusi  optimal.  Jumlah  iterasi  yang  diperlukan  untuk mencapai hasil terbaik tidak berkorelasi positif dengan jumlah poin yang diselesaikan.

## REFERENSI
[1] Brogan, W. L.  "Applications of a determinant identity to pole-placement and observer problems" IEEE Transactions on Automatic Control ( Volume: 19, Issue: 5, October 1974)
[2] Wan  Amir  Fuad  Wajdi  Othman,  Aeizaal  Azman  Abd Wahab,  Syed  Sahal  Nazli  Alhady,  Haw  Ngie  Wong. Solving  Vehicle  Routing  Problem  using  Ant  Colony Optimisation  (ACO)  Algorithm.  ISSN:  2348-7860  (O)  | 2348-7852 (P) | Vol. 5 No. 9 | September-October 2018 | PP. 500-507..
[3] M. Reed, A. Yiannakou, and R. Evering, "An ant colony algorithm  for  the  multi-compartment  vehicle  routing
problem," Applied Soft Computing, vol. 15, pp. 169-176,
2// 2014 [4] M. Dorigo and L. M. Gambardella, "Ant colony system: a cooperative  learning  approach  to  the  traveling  salesman problem," IEEE
[5] Baldacci, R., P. Toth and D. Vigo, 2010. Exact algorithms for  routing  problems  under  vehicle  capacity  constraints.
Ann.  Oper.  Res.,  175:  213-245.  DOI:  10.1007/s10479- 009-0650-0. [6] Tan, W.F., 1, L.S. Lee, 1, Z.A. Majid and H.V. Seow. Ant
Colony  Optimization  for  Capacitated  Vehicle  Routing
Problem.  Journal  of  Computer  Science  8  (6):  846-852, 2012. [7]
Modhi Lafta Mutara*, M.A. Burhanuddina, Asaad Shakir Hameeda,  Norzihani  Yusofa  and  Hussein  Jameel Mutasharb.  An  efficient  improvement  of  ant  colony system  algorithm  for  handling  capacity  vehicle  routing problem.  International  Journal  of  Industrial  Engineering Computations 11 (2020) 549–564.
[8] Ibrahim  A.A,  Lo  N.,  Abdulaziz  R.O,  Ishaya  J.A. CAPACITATED  VEHICLE  ROUTING  PROBLEM. ISSN- 2350-0530(April 2019), ISSN-2394-3629(P) DOI : 10.5281/zenodo. 2636820.
[9] Bruce L Golden, Subramanian Raghavan, and Edward A Wasil,  The  Vehicle  Routing  Problem:  Latest  Advances and  New  Challenges,  vol.  43,  Springer  Science  & Business Media, 2008.
[10] Dorigo,  M.,  &  Gambardella,  L.  M.  (1997).  Ant  colony system: a  cooperative  learning  approach to  the  traveling salesman  problem.  IEEE  Transactions  on  evolutionary computation, 1(1), 53-66.
[11] Dorigo, M., Birattari, M., & Stutzle, T. (2006). Ant colony optimization. IEEE computational intelligence magazine, 1(4), 28-39.
[12]          Huo,  L.,  Yan,  G.,  Fan,  B.,  Wang,  H.,  &  Gao,  W  (2014, August). School bus routing problem based on ant colony optimization  algorithm.  In  2014  IEEE  Conference  and Expo  Transportation  ElectrificationAsia-Pacific  (ITEC Asia-Pacific) (pp. 1-5). IEEE.
[13] Dantzig, George Bernard; Ramser, John Hubert (October 1959). "The Truck Dispatching Problem" (PDF) . Management
Science. 6 (1):891. doi : 10.1287/mnsc.6.1.80 .