## SAINTEKS: JURNAL SAIN DAN TEKNIK Volume 5 Nomor 2 Tahun 2023

## E-ISSN : 2685-8304
Briquette Characteristics of Mixed Charcoal of Taro Peel and Rice Husk Galu Murdikaningrum, Mutiara Putri Utami Susanto, Raden Tarisa Nurhanifah, Mualifah (pp:126 –136)
Analysis of Interest In Using Electrical Bicycles in Palangka Raya Vivien Nopella Valentina, Robby,Sutan Parasian Silitonga (pp: 137 –144)
The Effect Of H2O2 On The Bleaching-Scouring Simultaneous Process Of 100% Cotton Fabric With Pad – Batch System
Luciana, Agni Salamah (pp: 145 –153)
Management of Water Quality Parameters In Cultivating Vaname Shrimp (Litopenaeus Vannamei) In Intensive Tambak PT. Aneka Tambak Oseana Nusantara , NTB Pieter Amalo, Riris Yuli Velentine, Catur Pramono Adi, Restye Putri Geofani Mbura (pp: 154 –162)
Analysis of The Ant Number Effects on Ant Colony Optimization for Solving Russia-20-Nodes-SDVRP Instance Ekra Sanggala, Muhammad Ardhya Bisma (pp: 163 –174) Facilities Re- layout of “X” Health Center
Dini Yulianti, Tombak Gapura Bhagya, Didi Kusvendi (pp: 175 –186)
Use of Gold Mine Waste Sand From Penda Pilang Village as Hrs-Base Mixture
Deskianto, Supiyan, Devia (pp: 187 –199)
In Vitro Antagonism Test of Endophytic Isolates From The Ciplukan Plant (Physalis Angulata L.)
Against Ralstonia Solanacearums Ika Afifah Nugraheni, Inneke Ashri Mawaddah (pp: 200 –210)
Employee Performance Measurement at PT. Cahaya Mekanindo Perkasa Using the Human Resources Scorecard Method Ilyas Habibi, AuliaFashanah Hadining (pp: 211 –219)
The Effect of Temperature Variations in the Pressing Process on Glossing Defects Bigborn 2-Tuck Pants Style 3651 Trousers in the Finishing Department of PT. X Afriani Kusumadewi, Feny Nurherawati, Filly Pravitasari (pp: 220 –227)
Optimum Splice Thickness Ratio Splicer of a Winding Machine to PE20KT Thread Splicing Quality
Hendri Pujianto, Bambang Yulianto, Hamdan S Bintang, Dinda Amelia Pramesti (pp: 228 –235) The Influence of Organizational Culture and Organizational Commitment to Employee Work Discipline at the Bandung City Transportation Service Moch Ruli Chaerudin, Riza Rizkiah (pp: 236 –245)
Feasibility Analysis of Smelter Grade Alumina (SGA) Project Development at PT. X Dio Rianto , Dedy Setyo Oetomo, Rizky Fajar, Ramdhani (pp: 246 –258)
Evaluation of Decision Making on Using Online Media in the D'Amerta Berniaga Bandung Business Group Alam Avrianto , Ira Murwenie, Rahmina Puspa AR, Dwirani Fauzi L, Abdul Fatah H (pp: 259 –265)
5 Year Effectiveness Index From Research Ministry Of Marine And Fisheries
Catur Pramono Adi, Pieter Amalo (pp: 266 –273)
Technology Acceptance Model for the Use of Learning Management System in Indonesia Graha Prakarsa, Elly Komala, Tombak Gapura Bhagya, Safira Noor Andinia (pp: 274 –284)
UNIVERSITAS INSAN CENDEKIA MANDIRI dh UNIVERSITAS BANDUNG RAYA Fakultas Teknik
Jl. Pasir Kaliki No. 199 Bandung – Jawa Barat http://ejournal.uicm.ac.id/index.php/sainteks UICM – UNBAR www.uicm.ac.id
http://ejournal.uicm.ac.id/index.php/sainteks/
Analysis of The Ant Number Effects on Ant Colony Optimization for Solving Russia-20-Nodes-SDVRP Instance
Analisis Pengaruh Jumlah Semut Pada Ant Colony Optimization Untuk Penyelesaian Russia-20-Nodes-SDVRP Instance
Ekra Sanggala 1*) , Muhammad Ardhya Bisma 2)
1) Universitas Logistik dan Bisnis Internasional, Jalan Sariasih No. 54, Bandung, 40151 Email: ekrasanggala@mail.ru
2) Universitas Logistik dan Bisnis Internasional, Jalan Sariasih No. 54, Bandung, 40151 Email: bisma@ulbi.ac.id
*) Corresponding author
Abstract:  SDVRP  is  a  variation  of  the  CVRP  that  allows  different  vehicles  to  visit  the  same  node.  ACO performance is influenced by it’s parameter value. The number of ants parameter has a strong influence on ACO Performance, because it influences directly on solution quality and computation time. It is too hard to find the parameter value that can make ACO performance being the best performance. Because of this, what can be done is to test several parameter values,  then compare the ACO  performance of each  parameter value. Russia-20-Nodes- SDVRP Instance is attractive to be solved because it’s number of nodes are not too many, only 20 nodes. Based on that number of nodes, the computation time of this instance is relatively fast and it has a lot of solution  candidate. This  research  focus on the ant number effects on ACO for Solving Russia-20-Nodes-SDVRP Instance. Five ant numbers will be tested, they are 5, 10, 15, 20 and 25 ants, each ant number will be tested 10 times, so there will be 50 tests. These tests show that more ants used, greater possibility of getting a better route, but longer calculation time needed. The decrease in average of length of route is 1,1521% while the increase in average of calculation time is 42.5525%.
Keywords: SDVRP, ACO, Parameter ACO, The Number of Ant
Abstrak: SDVRP merupakan pengembangan dari CVRP yang memungkinkan sebuah titik dikunjungi lebih dari  sekali  untuk  pemenuhan  kebutuhannya.  Performansi  dari ACO sangat  dipengaruhi  oleh  nilai parameter-parameternya. Parameter jumlah semut sangat berpengaruh terhadap performansi ACO karena berpengaruh  langsung  terhadap  kualitas  solusi  yang  dihasilkan  dan  waktu  perhitungan.  Tidak  dapat diketahui nilai-nilai parameter yang dapat menjadikan performansi ACO menjadi performansi yang terbaik. Dikarenakan  hal  ini,  yang  dapat  dilakukan  adalah  dengan  menguji  beberapa  nilai-nilai  parameter  dan kemudian membandingkan performansi ACO untuk setiap nilai-nilai parameter. Russia-20-Nodes-SDVRP Instance menjadi menarik untuk diselesaikan karena jumlah titiknya tidak terlalu banyak, hanya 20 titik saja. Dengan jumlah titik tersebut, menjadikan instance tersebut waktu perhitungannya relatif cepat dan mempunyai kemungkinan solusi yang sangat banyak. Penelitian ini berfokus pada analisis pengaruh jumlah semut terhadap performansi ACO dalam menyelesaikan Russia-20-Nodes-SDVRP Instance . Jumlah semut yang akan diujikan adalah 5, 10, 15, 20  dan 25 semut,  pada setiap jumlah semut akan dilakukan 10 kali percobaan, dengan demikian akan ada sebanyak 50 percobaan. Dari percobaan-percobaan tersebut terlihat bahwa  semakin  banyak  semut  maka  semakin  besar  peluang  mendapatkan  rute  yang  lebih  baik,  tetapi semakin  lama  waktu  perhitungannya.  Penurunan  rata-rata  panjang  rute  adalah  1,1521%  sedangkan kenaikan rata-rata waktu perhitungan adalah 42,5525%.
Kata Kunci: SDVRP , ACO , Parameter ACO , Jumlah Semut
DOI: http://dx.doi.org/10. 37577/sainteks.v%vi%i.608 Received: 07, 2023.  Accepted: 08, 2023. Published: 09, 2023.
Analysis  of  The  Ant  Number  Effects  on  Ant  Colony  Optimization  for  Solving  Russia-20-Nodes-SDVRP Instance

## PENDAHULUAN
Seiring  dengan  adanya  perkembangan  teknologi  dan  ekonomi,  logistik  tidak  lagi  hanya  untuk pengiriman  saja,  tuntutan  kebutuhan  dan  keterbatasan  logistik  perlu  dipertimbangkan.  Pada penerapan Vehicle  Routing Problem  (VRP) di dunia  nyata,  terdapat banyak keterbatasan yang perlu dipertimbangkan, seperti keterbatasan kapasitas kendaraan, waktu perjalanan kendaraan, keterbatasan waktu dan lain-lain. Keterbatasan-keterbatasan ini menyebabkan lahirnya berbagai jenis VRP, seperti Capacity Vehicle Routing Problem (CVRP), Periodic Vehicle Routing Problem ( PVRP),  Multiple  Depot  Vehicle  Routing  Problem  (MDVRP),  Split  Delivery  Routing  Problem ( SDVRP), Vehicle Routing Problem with Time Windows (VRPTW) dan Vehicle Routing Problem with Simultaneous Pickups and Deliveries (VRPSPD) (Chen, 2018).
Split  Delivery  Vehicle  Routing  Problem  (SDVRP)  merupakan  pengembangan  dari Capacitated Vehicle Routing Problem (CVRP) yang memungkinkan sebuah titik dikunjungi lebih dari sekali untuk pemenuhan kebutuhannya. Pada SDVRP, kebutuhan dari sebuah titik mungkin lebih  banyak  dari  pada  kapasitas  kendaraan.  Dengan  demikian  dimungkinkan  ada  titik  yang dikunjungi  oleh  beberapa  kendaraan  dan  pemenuhan  kebutuhan  titik  tersebut    dibagi  pada kendaraan-kendaraan  tersebut,  bahkan  hal  ini  dapat  dilakukan  pada  titik  yang  kebutuhannya tidak melebihi kapasitas kendaraan. (Shi, 2018).
Ilustrasi  perbedaan  antara VRP  dengan  SDVRP  dapat  dilihat  pada  gambar  1.  Diketahui bahwa  ada  1  depot  dengan  4  titik  yang  kebutuhannya  perlu  dipenuhi.  Titik-titik  tersebut mempunyai kebutuhan sebanyak 3 produk, dan diketahui kapasitas kendaraan yang digunakan paling banyak mampu membawa 4 produk (Archetti, 2012).
(a) Data jarak antar titik & kebutuhan setiap titik.
(b) Penyelesaian VRP dengan 4 rute dan total jarak 16.
Analysis  of  The  Ant  Number  Effects  on  Ant  Colony  Optimization  for  Solving  Russia-20-Nodes-SDVRP Instance
(c) Penyelesaian SDVRP dengan 3 rute dan total jarak 16.
Gambar 1: Ilustrasi Perbedaan Antara VRP dengan SDVRP (Archetti, 2012).
Pada gambar 1(b) terlihat bahwa untuk memenuhi kebutuhan setiap titik dilakukan dengan sekali kunjungan, sedangkan pada gambar 1(c) terlihat bahwa ada sebuah titik yang pemenuhan kebutuhannya dilakukan dengan tiga kali kunjungan, titik tersebut ditandai dengan warna merah.
Dengan adanya kemungkinan pemenuhan kebutuhan sebuah titik dilakukan oleh lebih dari satu  kali  kunjungan,  mengakibatkan  munculnya  potensi  untuk  mengurangi  jumlah  rute kunjungan  dan  mengurangi  total  jaraknya  (Chen,  2007).  Pada  gambar  2,  terlihat  penyelesaian SDVRP  yang  dapat  melakukan  pengurangan  jumlah  rute  kunjungan  dan  pengurangan  total jaraknya dalam menyelesaikan permasalahan yang terdapat pada gambar 1.
Gambar 2: Penyelesaian SDVRP dengan 3 rute dan total jarak 15 (Chen, 2007).
Penyelesaian SDVRP  pada  gambar  1(c)  mempunyai  total  jarak  yang  sama  dengan penyelesaian VRP  pada gambar 1(b), dengan demikian penyelesaian  SDVRP  ini belum mampu mengurangi total jarak, sedangkan penyelesaian SDVRP pada gambar 2 mempunyai total jarak 15, dengan demikian penyelesaian SDVRP ini mampu mengurangi total jarak. Pada SDVRP jumlah produk yang dibawa oleh kendaraan untuk titik yang dikunjungi lebih dari satu kali, menjadi sebuah variabel. Hal ini menyebabkan meningkatnya kompleksitas VRP. Kompleksitas  ini  menjadikan SDVRP  sebuah  NP-Hard  Problem  (Nondeterministic  polynomial time) (Ozbaygin, 2018).  Dalam menyelesaikan NP-Hard Problem diperlukan waktu yang sangat lama, yang tidak wajar untuk ditunggu (Applegate, 2006). Meskipun demikian NP-Hard Problem dapat  diselesaikan  dalam  jangka  waktu  yang  wajar  dengan  menggunakan  algoritma heuristic serta metaheuristic meskipun solusi yang dihasilkan belum tentu yang terbaik (Labadie, 2016).
Analysis  of  The  Ant  Number  Effects  on  Ant  Colony  Optimization  for  Solving  Russia-20-Nodes-SDVRP Instance
Heuristic merupakan  sebuah  kata  dari  bahasa  yunani  yang  berarti  “menemukan”  atau “mengeksplorasi”. Heuristics  disebut  sebagai  approximate  techniques.  Tujuan  utama  dari heuristics adalah untuk membangun sebuah model optimasi yang mudah dipahami dan mampu memberikan solusi yang baik dalam waktu perhitungan yang wajar (Kumar, 2020). Sufiks meta, juga  berasal  dari  bahasa  yunani  yang  berarti “upper  level  methodology” .  Maka metaheuristic dapat didefinisikan sebagai sebuah template yang dapat dikembangkan menjadi heuristic untuk menyelesaikan sebuah masalah optimasi (Talbi, 2009).
Ant  Colony  Optimization  (ACO)  merupakan  sebuah  metaheuristic  dimana  sekumpulan semut  tiruan  bekerja  sama  untuk  menemukan  solusi  yang  baik  dalam  menyelesaikan  masalah optimasi (Dorigo, 2004). Konsep ACO ini terinspirasi dari perilaku semut. Semut adalah serangga yang hidup secara berkoloni dan berperilaku untuk kepentingan koloni. Hal menarik dari perilaku semut  adalah  kemampuannya  untuk  menemukan  rute  terpendek  antara  sarangnya  dengan sumber makanan (Santosa, 2017).
Perilaku semut dalam mencari makanan dapat dideskripsikan seperti berikut: Sekelompok semut yang berada di depan harus memilih jalur tertentu untuk dilewati. Pada saat semut pertama berjalan, semut tersebut meninggalkan pheromone yang dapat dicium oleh semut- semut  dibelakangnya,  sehingga semut-semut  tersebut  dapat  mengetahui  apakah  jalur  tersebut sudah terlewati atau belum. Mereka pun selama berjalan meninggalkan pheromone pada jalur yang  dilewatinya.  Semakin  banyak  semut  yang  melewati  suatu  jalur,  maka  semakin  pekat pheromone  yang  ditinggalkan  pada  jalur  tersebut.  Kepekatan  pheromone  ini  pun  dipengaruhi oleh  adanya  penguapan  pada  pheromone.  Semakin  pekat  pheromone  pada  suatu  jalur,  maka semakin besar peluang jalur tersebut akan dipilih untuk dilewati. Pada gambar 3 dapat dilihat gambaran sekelompok semut dalam memilih jalur untuk menemukan makanan.
Gambar 3: Gambaran Semut Dalam Memilih Jalur Untuk Menemukan Makanan (Talbi, 2009).
Peluang suatu jalur untuk dilewati oleh semut dapat dituliskan pada persamaan berikut ini (Gao, 2020):
𝑃 𝑖𝑗 𝑘 (𝑡) = 𝜏 𝑖𝑗 𝛼 (𝑡) . 𝜂 𝑖𝑗 𝛽 ∑ 𝜏 𝑖𝑗 𝛼 (𝑡) 𝑗𝜖𝑁 𝑖 𝑘 . 𝜂 𝑖𝑗 𝛽 , 𝑖𝑓 𝑗𝜖𝑁 𝑖 𝑘
Analysis  of  The  Ant  Number  Effects  on  Ant  Colony  Optimization  for  Solving  Russia-20-Nodes-SDVRP Instance
𝜂 𝑖𝑗 = 1 𝑑 𝑖𝑗 𝑃 𝑖𝑗 𝑘 (𝑡) : peluang semut k memilih jalur dari titik i ke titik j t : iterasi k : semut k i : titik i j : titik j α : derajat kepentingan pheromone β : derajat kepentingan kebalikan jarak antar titik 𝑁 𝑖 𝑘
: titik-titik yang dapat dipilih oleh semut k pada saat berada di titik i 𝜏 𝑖𝑗 : kepekatan pheromone jalur dari titik i ke titik j 𝜂 𝑖𝑗 : kebalikan jarak jalur dari titik i ke titik j 𝑑 𝑖𝑗
: jarak antara titik i dengan titik j
Kepekatan  pheromone  pada  suatu  jalur  setelah  terjadinya  penguapan  pheromone  dapat dituliskan pada persamaan berikut ini (Gao, 2020):
𝜏 𝑖𝑗 (𝑡 + 1) = (1 − 𝜌)𝜏 𝑖𝑗 (𝑡) 𝜏 𝑖𝑗 : kepekatan pheromone jalur titik i ke titik j ρ : derajat penguapan pheromone
t : iterasi
Banyaknya pheromone yang ditinggalkan seekor semut pada suatu jalur dapat dituliskan pada persamaan berikut ini (Gao, 2020):
∆𝜏 𝑖𝑗 𝑘 (𝑡) = { 𝑄 𝐿 𝑘 (𝑡), 𝑖𝑓 𝑎𝑛𝑡 𝑘 𝑡𝑟𝑎𝑣𝑒𝑙𝑠 𝑜𝑛 𝑒𝑑𝑔𝑒 (𝑖, 𝑗) 0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
∆𝜏 𝑖𝑗 𝑘 : banyaknya pheromone yang ditinggalkan semut k pada jalur titik i ke titik j
Q : konstanta
𝐿 𝑘
: panjang rute yang dilalui oleh semut k t : iterasi
Kepekatan  pheromone  pada  suatu  jalur  setelah  adanya  pheromone  yang  ditinggalkan semut yang melaluinya dapat dituliskan pada persamaan berikut ini (Gao, 2020):
𝜏 𝑖𝑗 (𝑡 + 1) = 𝜏 𝑖𝑗 (𝑡 + 1) + ∑ ∆𝜏 𝑖𝑗 𝑘 (𝑡) 𝑚 𝑘=1
𝜏 𝑖𝑗 : kepekatan pheromone jalur titik i ke titik j ∆𝜏 𝑖𝑗 𝑘 : banyaknya pheromone yang ditinggalkan semut k pada jalur titik i ke titik j m : banyaknya semut
t : iterasi
Analysis  of  The  Ant  Number  Effects  on  Ant  Colony  Optimization  for  Solving  Russia-20-Nodes-SDVRP Instance
Proses  pada  persamaan-persamaan  diatas  akan  terus  berulang  hingga  mencapai  jumlah iterasi R (Gao, 2020).
Berdasarkan  persamaan-persamaan  diatas  dapat  diketahui  bahwa  parameter-parameter untuk ACO adalah sebagai berikut ini (Wang, 2021):
1. α : derajat kepentingan pheromone
2. β
: derajat kepentingan kebalikan jarak antar titik
3. ρ
: derajat penguapan pheromone (0≤ρ≤1)
4. 𝜏 𝑖𝑗 (1) : kepekatan pheromone pada iterasi 1
5. 𝑚 : jumlah semut
6. 𝑅 : maksimal iterasi
Nilai-nilai parameter ini dapat mempengaruhi performansi dari ACO. Biasanya pengukuran performansi  tersebut  adalah  berdasarkan  solusi  yang  dihasilkan  dan  waktu  perhitungan  yang diperlukan. Parameter jumlah semut merupakan parameter yang sangat berpengaruh terhadap performansi dari ACO karena berpengaruh langsung terhadap solusi yang dihasilkan dan waktu perhitungan. Semakin banyak jumlah semut, maka semakin besar peluang untuk mendapatkan solusi  yang  lebih  baik,  tetapi  mengakibatkan  waktu  perhitungan  semakin  lama.  Hal  ini  terjadi karena  semakin  banyak  semut  maka  semakin  banyak  rute  yang  dicoba,  tetapi  hal  ini mengakibatkan  semut  memerlukan  waktu  lebih  lama  untuk  mencoba  banyak  rute.  Berbeda dengan  parameter-parameter  lainnya  yang  hanya  berpengaruh  langsung  terhadap  waktu perhitungan karena berapa pun nilainya, jumlah rute yang dicoba tetap sama.
Tidak  dapat  diketahui  nilai-nilai  parameter  yang  dapat  menjadikan  performansi ACO menjadi performansi yang terbaik. Penentuan nilai-nilai parameter ini tidak ada ketentuannya, sehingga nilai-nilai ini ditentukan langsung oleh pengguna ACO. Dikarenakan hal ini, yang dapat dilakukan adalah dengan menguji beberapa nilai-nilai parameter dan kemudian membandingkan performansi ACO untuk setiap nilai-nilai parameter.
Sebuah SDVRP Instance yang dibuat oleh penulis adalah Russia-20-Nodes-SDVRP Instance. Instance  ini  dibuat  berdasarkan  20  kota  berpenduduk  terbanyak  di  Russia  (Sanggala,  2023). Instance  ini  menjadi  menarik  untuk  diselesaikan  karena  jumlah  titiknya  tidak  terlalu  banyak, hanya 20 titik saja. Dengan jumlah titik sebanyak 20 titik, menjadikan instance tersebut sebagai permasalahan  yang  menarik  untuk  dilakukannya  pengujian  nilai-nilai  parameter ACO,  karena waktu  perhitungannya  yang  relatif  cepat  dan  mempunyai  kemungkinan  solusi  yang  sangat banyak.
Penelitian  ini  berfokus  pada  analisis  pengaruh  jumlah  semut  terhadap  performansi ACO dalam  menyelesaikan Russia-20-Nodes-SDVRP  Instance.  Performansi  ACO  yang  akan  diukur adalah solusi yang dihasilkan dan waktu perhitungan. Dengan demikian diharapkan penelitian ini dapat menjadi acuan dalam penentuan jumlah semut dalam ACO.

## METODOLOGI
Secara umum tahapan-tahapan yang dilakukan adalah sebagai berikut ini:
1. Penentuan Instance
Instance  merupakan sekumpulan data  awal  yang akan menjadi acuan pengerjaan pada penelitian  ini. Instance  yang  akan  digunakan  adalah  Russia-20-Nodes-SDVRP  Instance. Pada tabel 1 dapat dilihat data yang terdapat pada instance tersebut.
Analysis  of  The  Ant  Number  Effects  on  Ant  Colony  Optimization  for  Solving  Russia-20-Nodes-SDVRP Instance
Tabel 1: Russia-20-Node-SDVRP Instance
2. Penentuan Nilai-Nilai Parameter Jumlah Semut Karena  yang  akan  dianalisis  adalah  pengaruh  nilai  parameter  jumlah  semut  terhadap performansi ACO, maka nilai-nilai parameter ini akan berbeda-beda. Nilai-nilai parameter tersebut adalah 5 semut, 10 semut, 15 semut, 20 semut dan 25 semut.
3. Penentuan Nilai-Nilai Parameter Selain Parameter Jumlah Semut Berikut ini adalah nilai-nilai parameter selain parameter jumlah semut:
α = 2 β = 2
ρ = 0,01 𝜏 𝑖𝑗 (1) = 10
𝑅 = 20
Nilai-nilai parameter tersebut akan selalu tetap pada setiap percobaan.
4. Pengujian ACO Terhadap Instance
Dengan  menggunakan  nilai-nilai  parameter  yang  sudah  ditentukan,  maka  dilakukan pengujian ACO  terhadap  Russia-20-Nodes-SDVRP  Instance.  Pada  setiap  percobaan
Analysis  of  The  Ant  Number  Effects  on  Ant  Colony  Optimization  for  Solving  Russia-20-Nodes-SDVRP Instance
dilakukan  pencatatan  solusi  yang  dihasilkan  dan  pencatatan  waktu  perhitungan  yang diperlukan. Untuk setiap nilai parameter jumlah semut akan dilakukan 10 kali percobaan. Dengan demikian pada pengujian ini akan terdapat 50 kali percobaan.
5. Analisis Pengaruh Jumlah Semut Terhadap Performansi ACO Berdasarkan  pencatatan  yang  dilakukan  pada  tahap  ke-4  dilakukan  analisis  pengaruh jumlah semut terhadap performansi ACO. Analisis tersebut dilakukan terhadap nilai-nilai berikut ini:
a) Panjang rute terpendek
b) Panjang rute terjauh
c) Rata-rata panjang rute
d) Penurunan rata-rata panjang rute
e) Waktu perhitungan tercepat
f) Waktu perhitungan terlama
g) Rata-rata waktu perhitungan
h) Kenaikan rata-rata waktu perhitungan
Untuk membantu menyelesaikan pengujian, digunakan perangkat lunak GNU Octave. GNU Octave merupakan alat multifungsi untuk melakukan analisis numerik. Berbagai alat bantu yang tersedia di dalam GNU Octave adalah sebagai berikut ini (Quarterno, 2006):
1. Sekumpulan function untuk menyelesaikan berbagai masalah.
2. Bahasa  pemrograman  yang  dapat  digunakan  untuk  mengembangkan  kemampuan GNU Octave.
3. Berbagai fasilitas untuk melakukan plotting.
Nama GNU Octave diambil dari seorang ahli kimia yang bernama Octave Levenspiel. GNU Octave  ini  merupakan  proyek  resmi  dari  GNU  dan  lisensi  source  code  berada  di  bawah  GNU General Public License (GPL), sehingga siapa pun boleh menggunakannya untuk berbagai tujuan (Hansen, 2011).

## HASIL PENELITIAN DAN PEMBAHASAN
Sebelum dilakukan pengujian  dilakukan perhitungan untuk menghitung jarak antar titik. Jarak antar titik ini dihitung berdasaran Haversine Formula. Haversine Formula merupakan persamaan yang digunakan untuk menghitung jarak antara dua titik di Bumi, bentuk persamaannya adalah seperti berikut ini (Idrizi, 2020):
𝑎 = 𝑠𝑖𝑛 2 ( 𝛥𝜙 2 ) + cos 𝜙 1 . cos 𝜙 2 . 𝑠𝑖𝑛 2 ( 𝛥𝜆 2 )
𝑐 = 2 . 𝑎𝑡𝑎𝑛2 [√𝑎, √(1 − 𝑎) ]
𝑑 = 𝑅 . 𝑐 ϕ1 : Latitude titik pertama ϕ2 : Latitude titik kedua λ1 : Longitude titik pertama λ2 : Longitude titik kedua Δϕ : ϕ1 – ϕ2 Δλ : λ1 – λ2 R : Radius Bumi (6371 Km)
Berikut  ini  merupakan  contoh  penggunaan Haversine  Formula  dalam  menghitung  jarak antara dua titik di Bumi:
Analysis  of  The  Ant  Number  Effects  on  Ant  Colony  Optimization  for  Solving  Russia-20-Nodes-SDVRP Instance
Moscow (Lat: 55,75222; Long: 37,61556) St.Petersburg (Lat:59,93863; Long: 30,31413)
𝑎 = 𝑠𝑖𝑛 2 ( 𝛥𝜙 2 ) + cos 𝜙 1 .  cos 𝜙 2 .  𝑠𝑖𝑛 2 ( 𝛥𝜆 2 ) 𝑎 = 0,002477
𝑐 = 2 . 𝑎𝑡𝑎𝑛2 [√0,002477, √0,998761 ] 𝑐 = 0,099581 𝑑 = 6371 . 0,099581 𝑑 = 634,4309  ≈ 635 𝑘𝑚
Dengan  menggunakan  bantuan GNU  Octave  dilakukan  pengujian  ACO  terhadap  instance sehingga  diperoleh  hasil  seperti  yang  terlihat  pada  tabel  2.  Bagi  para  pembaca  yang membutuhkan file  dari  listing  program  yang  digunakan,  dapat  langsung  menghubungi  penulis melalui e-mail.
Tabel 2: Hasil Pengujian ACO Pada Russia-20-Node-SDVRP Instance
Analysis  of  The  Ant  Number  Effects  on  Ant  Colony  Optimization  for  Solving  Russia-20-Nodes-SDVRP Instance
Tabel 2: Hasil Pengujian ACO Pada Russia-20-Node-SDVRP Instance (Lanjutan)
Pada tabel 3 dapat dilihat panjang rute terpendek, panjang rute terjauh, rata-rata panjang rute dan penurunan rata-rata panjang rute
Analysis  of  The  Ant  Number  Effects  on  Ant  Colony  Optimization  for  Solving  Russia-20-Nodes-SDVRP Instance
Tabel 3: Panjang Rute Terpendek, Panjang Rute Terjauh, Rata-Rata Panjang Rute dan Penurunan Rata-Rata Panjang Rute
Berdasarkan tabel 3 terlihat bahwa semakin banyak jumlah semut yang digunakan, maka panjang rute terpendek, panjang rute terjauh dan rata-rata panjang rute cenderung mengalami penurunan.  Tetapi  berdasarkan  penurunan  rata-rata  panjang  rute,  terlihat  juga  penurunan  ini tidak signifikan, dengan rata-rata penurunan 1,1521% saja.
Pada tabel 4 dapat dilihat waktu perhitungan tercepat, waktu perhitungan terlama, rata- rata waktu perhitungan dan kenaikan rata-rata perhitungan
Tabel  4:  Waktu  Perhitungan  Tercepat,  Waktu  Perhitungan  Terlama,  Rata-Rata  Waktu Perhitungan dan Kenaikan Rata-Rata Waktu Perhitungan
Berdasarkan tabel 4 terlihat bahwa semakin banyak jumlah semut yang digunakan, maka waktu  perhitungan  tercepat,  waktu  perhitungan  terlama  dan  rata-rata  waktu  perhitungan cenderung  mengalami  kenaikan.  Berdasarkan  kenaikan  rata-rata  waktu  perhitungan,  terlihat kenaikan ini cukup signifikan, dengan rata-rata kenaikan 42,5525%.
Berdasarkan  uraian-uraian  diatas,  diharapkan  penelitian  ini  dapat  menjadi  acuan  para pengguna ACO dalam menentukan nilai parameter jumlah semut, jika mementingkan penurunan panjang rute maka dapat digunakan jumlah semut yang banyak dengan resiko kenaikan rata-rata waktu perhitungan yang terus meningkat secara signifikan.

## SIMPULAN
Pendekatan metaheuristic  seperti  ACO  tidak  selalu  menampilkan  performansi  yang  terbaik. Performansi yang diukur biasanya adalah solusi yang dihasilkan dan waktu perhitungan. Nilai- nilai  parameter  sangat  berpengaruh  terhadap  performansi  tersebut.  Parameter  jumlah  semut sangat berpengaruh terhadap performansi tersebut, karena berdampak langsung terhadap solusi yang  dihasilkan  dan  waktu  perhitungan.  Penelitian  ini  memperlihatkan  bahwa  penambahan jumlah semut yang digunakan tidak berpengaruh signifikan terhadap peningkatan kualitas solusi, tetapi berpengaruh cukup signifikan terhadap peningkatan waktu perhitungan. Meskipun begitu, pengujian dengan jumlah semut yang lebih banyak dapat dilakukan pada penelitian selanjutnya agar  semakin  terlihat  pengaruh  jumlah  semut  terhadap  kualitas  solusi  yang  dihasilkan.  Begitu pula, pengujian terhadap nilai parameter-parameter lainnya perlu dilakukan, sehingga semakin banyak acuan dalam menentukan nilai-nilai parameter ACO.
Analysis  of  The  Ant  Number  Effects  on  Ant  Colony  Optimization  for  Solving  Russia-20-Nodes-SDVRP Instance

## DAFTAR PUSTAKA
Archetti, A. & Speranza, M. G. (2012). Vehicle Routing Problems With Split Deliveries, International Transactions In Operational Research
Chen,  R.,  &  Guo,  J.  (2018).  Optimal  Routing  for  Split  Delivery  Vehicle  Routing  Problems, 7 th International Congress on Advanced Applied Informatics
Chen, S., & Golden, B. (2007). The Split Delivery Vehicle Routing Problem: Applications, Algorithms, Test Problems, and Computational Results, Networks An International Journal
Dorigo, M. & Stutzle, T. (2004). Ant Colony Optimization, The MIT Press Cambridge, Massachusetts
Gao,  W.  (2020).  New  Ant  Colony  Optimization  Algorithm  for  The  Traveling  Salesman  Problem, International Journal of Computational Intelligence Systems
Hansen, J.S. (2011). GNU Octave Beginner’s Guide , PACKT – Birmingham
Idrizi,  B.  (2020).  Necessity  for  Geometric  Corrections  of  Distances  in  Web  and  Mobile  Maps, International Conference on Cartography and GIS
Labadie, N., Prins, C., & Prodhon, C. (2016). Metaheuristics for Vehicle Routing Problem, ISTE – London
Ozbayhin, G., Karasan, O. & Yaman, H. (2018). New Exact Solution Approaches for the Split Delivery Vehicle Routing Problem, Euro Journal on Computational Optimization
Quarteroni, A. & Saleri, F. (2006). Scientific Computing with MATLAB and Octave Second Edition, Springer
Sanggala, E. & Bisma, M. A.  (2023). Perbandingan Savings Algorithm dengan Nearest Neighbour dalam Menyelesaikan Russian TSP Instances, Jurnal Media Teknik & Sistem Industri
Santosa, B., & Ai, T. J. (2017). Pengantar Metaheuristik Implementasi dengan Matlab, ITS Tekno Sains
Shi, J. (2018). Particle Swarm Optimization for Split Delivery Vehicle Routing Problem, Asia-Pacific Journal of Operational Research
Talbi, E. (2009). Metaheuristics from Design to Implementation, John Wiley & Sons – USA
Wang, Y., & Han, Z. (2021). Ant Colony Optimization for Traveling Salesman Problem Based On Parameters Optimization, Applied Soft Computing