Vol. 16, No. 4, Dec 2023, pp. 264~273 eISSN: 2502-339X, pISSN: 1979-276X, DOI: 10.30998/faktorexacta.v16i4.18962  264
Penerapan Algoritma Sweep dan Particle Swarm Optimization
(PSO) sebagai Alternatif Menentukan Rute Distribusi
Ilham Saiful Fauzi 1 , Imaniah Bazlina Wardani 2 , Indra Lukmana Putra 3 , Peni Puspitasari 4 1,3,4 Jurusan Akuntansi, Politeknik Negeri Malang, Indonesia
2 Program Studi Tadris Biologi, FTIK, UIN Kiai Haji Achmad Siddiq Jember, Indonesia
Article Info ABSTRACT Article history: Received Jul 07, 2023 Revised Dec 20, 2023 Accepted Dec 28, 2023 One aspect of marketing activities is distribution. In the process of distributing goods, it is important to determine the optimal route that minimize mileage and  reduce  costs.  This  study  aims  to  provide  alternative  solutions  in determining  distribution  routes  with  the  shortest  distance  which  has implications for shorter travel times and lower costs. This research adapts the Capacitated  Vehicle  Routing  Problem  (CVRP)  model  with  the  approach  of sweep  and  Particle  Swarm  Optimization  (PSO)  algorithm  to  determine  the route.  To  generate  a  comparison  route,  we  use  the  Nearest  Neighbor  (NN) algorithm. The result was that 100 agents were divided into 6 clusters and the total distance of the PSO-generated route is 218.115 units or 85.70% of the route distance generated by Nearest Neighbor algorithm .
Keywords:
Distribution Route CVRP PSO algorithm NN algorithm Copyright © 2023 Universitas Indraprasta PGRI. All rights reserved.

## Corresponding Author:
Ilham Saiful Fauzi, Jurusan Akuntansi, Politeknik Negeri Malang, Jl. Soekarno Hatta No. 9, Lowokwaru, Malang, Indonesia. Email: ilham.fauzi@polinema.ac.id

## 1. PENDAHULUAN
Salah  satu  aspek  penting  dari  kegiatan  pemasaran  adalah  distribusi.  Distribusi  merupakan  bagian penting dari alur pemasaran yang menjadi jembatan pada proses penyampaian barang atau jasa yang diproduksi oleh produsen sebagai penghasil kepada konsumen yang membutuhkan [1]. Kegiatan distribusi memiliki peran penting untuk menjamin bahwa konsumen sebagai pengguna produk dapat menerima produk yang dihasilkan oleh produsen dengan efektif dan efisien. Rangkaian pada proses distribusi akan membantu masyarakat untuk memperoleh barang dan jasa  yang dibutuhkan dengan lebih mudah meskipun lokasi produsen bisa saja jauh dari lokasi masyarakat tersebut. Distribusi meningkatkan keterjangkauan masyarakat terhadap barang dan jasa yang menjadi kebutuhan atau keinginan mereka [2].
Di era persaingan pasar yang ketat, setiap perusahaan yang ingin tetap bertahan perlu memperhatikan sistem organisasi mereka terkait dengan rantai pasok ( supply chain ). Secara khusus, dibutuhkan analisis oleh perusahaan terkait rantai pasok untuk meningkatkan kualitas layanan kepada pelanggan tanpa disertai dengan pertumbuhan biaya yang tidak terkontrol. Setiap perusahaan dituntut untuk meningkatkan efisiensi operasional logistik mereka. Oleh karena itu, sangat penting untuk mengoptimalkan arus distribusi barang antara produsen sebagai penghasil dan konsumen sebagai pengguna.
Selain sistem distribusi, terdapat beberapa  faktor lain  yang  mempengaruhi proses distribusi  barang yakni transportasi dan rute distribusi [3]. Salah satu permasalahan klasik dalam proses pendistribusian barang adalah  kesulitan  dalam  menentukan  rute  distribusi  yang  optimal  sehingga  muncul  masalah  keterlambatan barang diterima konsumen atau meningkatnya biaya yang dikeluarkan distributor untuk menyalurkan barang.
265
Pola  pendistribusian  barang  yang  disusun  tanpa  pertimbangan  yang  terencana  dan  matang,  misalnya  hanya berdasarkan pengalaman pengendara atau pengelompokan wilayah, tidak menjamin diperoleh rute terpendek sehingga berdampak pada meningkatnya jarak tempuh kendaraan, waktu tempuh yang lebih lama dan ongkos lebih besar selama proses pendistribusian barang kepada para konsumen.
Menentukan rute distribusi barang yang efektif dan efisien bukan perkara mudah, apalagi jika terdapat banyak  agen yang  harus  didatangi  dan  lokasinya  tersebar  di  berbagai  wilayah.  Kendala  tambahan  seperti jumlah permintaan produk yang berbeda dari tiap agen dan keterbatasan kapasitas angkut kendaraan juga perlu diperhatikan [4]. Permasalahan menentukan rute dengan meminimukan biaya dari suatu distributor ke beberapa agen yang tersebar acak di suatu wilayah tertentu dengan kapasitas kendaraan terbatas dan jumlah permintaan tiap  agen  yang  berbeda  dikenal  dengan  istilah Capacitated  Vehicle  Routing  Problem (CVRP).  Beberapa penelitian  sebelumnya  telah  dilakukan  untuk  menyelesaikan  masalah  CVRP,  diantaranya  menggunakan algoritma sweep [5,6],  algoritma nearest  neighbor [7],  algoritma  PSO  [8,9],  dan  algoritma  genetik  [10,11]. Tujuan  penelitian  ini  adalah  memberikan  alternatif  solusi  dalam  menentukan  rute  distribusi  sehingga menghasilkan rute dengan jarak terpendek, waktu tempuh singkat, dan biaya rendah dengan memperhatikan kapasitas kendaraan untuk melayani permintaan agen. Kombinasi algoritma sweep dan PSO digunakan untuk menentukan rute dan selanjutnya dibandingkan dengan algoritma nearest neighbor .

## 2. METODE
Metode  penelitian  yang  digunakan  pada  penelitian  ini  adalah  metode  penelitian  terapan  ( applied reserach ). Penelitian terapan adalah  metode penelitian yang lebih diarahkan untuk menciptakan inovasi dan pengembangan iptek [12]. Penelitian ini bertujuan untuk mendapatkan solusi dari suatu masalah yang ada di masyarakat  dan  industri  yang  dalam  hal  ini  berkaitan  dengan  penentuan  rute  distribusi  yang  optimal.  Alur pelaksanaan penelitian ini disajikan dalam Gambar 1 sebagai berikut.
Gambar 1. Alur Penelitian

## 2.1 Data Penelitian
Penelitian ini bersifat umum karena tidak menggunakan data riil sehingga dapat diadaptasi oleh pihak terkait untuk diaplikasikan pada data yang dimiliki. Dengan  menggunakan  metode barisan Sobol, sebanyak 100 titik dibangkitkan secara acak pada bidang kartesius {(𝑥, 𝑦)| − 10 ≤ 𝑥, 𝑦 ≤ 10} yang mewakili lokasi dari 100 agen. Penggunaan barisan Sobol untuk menghasilkan titik acak didasari pertimbangan bahwa barisan ini menghasilkan  partisi  yang  seragam  dan  distribusi  yang  baik.  Barisan  Sobol  dirancang  untuk  memberikan distribusi titik-titik yang lebih merata dalam ruang pencarian khususnya untuk dimensi tinggi, dan telah banyak digunakan dalam penelitian yang berkaitan dengan pembangkitan data secara acak [13,14].
Lokasi distributor diatur sebagai titik pusat koordinat. Permintaan barang dari setiap agen, dinyatakan dengan 𝑑 , juga dibangkitkan secara acak pada interval [10,100] . Lokasi masing-masing agen beserta jumlah permintaan barang ditunjukkan dalam Gambar 2 sebagai berikut. Titik hitam yang terletak di pusat koordinat
266
( 0,0 )  menyatakan  lokasi  distributor.  Titik-titik  ditampilkan  dengan  warna  yang  berbeda  sesuai  dengan permintan  agen.  Titik  hijau  adalah  agen dengan  permintaan 10 ≤ 𝑑 ≤ 40 ,  titik  biru  adalah  agen dengan permintaan 40 < 𝑑 ≤ 70 , dan titik merah adalah agen dengan permintaan 70 < 𝑑 ≤ 100 .
Gambar 2. Lokasi masing-masing agen yang diperoleh dari proses randomisasi
Hasil randomisasi permintaan untuk masing-masing agen menghasilkan total permintaan sebesar 5.773 produk. Diasumsikan bahwa distributor memiliki kendaraan dengan kapasitas angkut yang sama yakni 1.000 produk, sehingga  dibutuhkan  enam  kendaraan  untuk  mendistribusikan  produk  ke  100  agen  yang  menjadi  tanggung jawab distributor tersebut. Tahap selanjutnya adalah penentuan kelompok ( cluster )  menggunakan algoritma sweep dan pembentukan rute pada masing-masing kelompok ( cluster ) menggunakan algoritma PSO. Sebagai pembanding  akan  digunakan  juga  algoritma nearest  neighbor (NN)  untuk  membentuk  rute  mengingat algoritma  ini  adalah  algoritma  yang  paling  umum  digunakan  untuk  membentuk  rute  dalam  penyelesaian masalah CVRP. Pada algoritma NN, lokasi selanjutnya yang dikunjungi hanya titik tujuan terdekat dari lokasi sebelumnya. Setelah semua agen dilayani, maka selanjutnya rute ditutup.

## 2.2 Masalah CVRP
Permasalahan membentuk rute yang meminimumkan biaya dari suatu depot ke beberapa agen dengan lokasi menyebar di suatu wilayah tertentu dengan jumlah permintaan berbeda disertai kendala tambahan berupa kapasitas kendaraan yang terbatas dikenal dengan istilah Capacitated Vehicle Routing Problem (CVRP) [15]. Penentuan rute dilakukan dengan pertimbangan bahwa setiap agen akan dikunjungi tepat satu kali oleh satu kendaraan. Semua rute yang terbentuk berawal dan berakhir di depot dan semua agen harus terlayani, artinya setiap  agen  masuk  dalam  rute  tertentu.  Penentuan  rute  dalam  CVRP  tidak  hanya  menekankan  pada  biaya minimum tetapi juga memperhatikan kapasitas masing-masing kendaraan yang terbatas dan homogen, yakni memiliki kapasitas sama [16]. Setiap kendaraan harus mengunjungi beberapa agen dengan permintaan tertentu dan  sudah  diketahui  sebelumnya.  Proses  distribusi  oleh  setiap  kendaraan  hanya  dilakukan  dalam  satu  kali perjalanan yang berawal dari depot ke sejumlah agen dan berakhir di depot yang sama. Hal ini bertujuan untuk membentuk suatu sistem penyampaian barang dengan rute lebih efektif dan efisien dari pihak produsen kepada pihak konsumen yang membutuhkan.
Secara  matematis,  CVRP  didefinisikan  sebagai  suatu  graf 𝐺 = (𝑉, 𝐸) dengan  himpunan  titik 𝑉 = {0,1, … , 𝑁} dan himpunan sisi 𝐸 = {(𝑖, 𝑗): 𝑖, 𝑗 ∈ 𝑉} [17]. Titik 0 mewakili depot (distributor) dan titik lainnya [1, … , 𝑁] menunjukkan agen dengan permintaan sejumlah 𝑞 𝑖 , dimana 𝑖 = {1, … , 𝑁} , yang harus dikirimkan. Jarak titik 𝑖 dan titik 𝑗 didefinisikan dengan 𝑑 𝑖𝑗 > 0 . Dengan depot tunggal 0, kendaraan sejumlah 𝐾 dengan batas kapasitas homogen 𝑄 berangkat dan kembali ke depot tersebut. Jika kendaraan 𝑘 berpindah dari agen 𝑖 ke  agen 𝑗 secara  langsung,  maka 𝑋 𝑖𝑗 𝑘 = 1 selainnya 𝑋 𝑖𝑗 𝑘 = 0 .  Fungsi  objektif  dari  CVRP  ditunjukkan  pada persamaan berikut.
𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒  ∑ ∑ ∑ 𝑑 𝑖𝑗 𝑋 𝑖𝑗 𝑘 𝐾 𝑘=1 𝑁 𝑗=0 𝑁 𝑖=0
(1)
267 yang meminimumkan total jarak tempuh kendaraan. Terdapat beberapa kendala yang ada pada CVRP dalam penelitian ini. Persamaan 2 dan persamaan 3 menunjukkan bahwa  setiap agen dilayani tepat satu kendaraan. Kendala total permintaan agen di masing-masing rute tidak lebih dari kapasitas 𝑄 ditunjukkan di persamaan 4. Persamaan 5 menunjukkan bahwa setiap rute harus berawal dan berakhir di depot yang sama.
∑ ∑ 𝑋 𝑖𝑗 𝑘 𝑁 𝑖=0 𝐾 𝑘=1 = 1         𝑗 ∈ {1, … , 𝑁} ∶ 𝑖 ≠ 𝑗 (2) ∑ ∑ 𝑋 𝑖𝑗 𝑘 𝑁 𝑗=0 𝐾 𝑘=1 = 1         𝑖 ∈ {1, … , 𝑁} ∶ 𝑖 ≠ 𝑗 (3) ∑ ∑ 𝑋 𝑖𝑗 𝑘 𝑁 𝑗=0 𝑁 𝑖=0 𝑞 𝑖 ≤ 𝑄         𝑘 ∈ {1, … , 𝐾}
(4)
∑ 𝑋 𝑖𝑗 𝑘 𝑁 𝑗=1 = ∑ 𝑋 𝑗𝑖 𝑘 𝑁 𝑗=1 ≤ 1         𝑖 = 0, 𝑘 ∈ {1, … , 𝐾} (5)

## 2.3 Algoritma Sweep
Diperkenalkan pertama kalinya oleh Gillet dan Miller pada tahun 1974, algoritma sweep merupakan metode pengelompokan paling sederhana dalam penyelesaian CVRP [18]. Titik pusat koordinat diatur sebagai lokasi distributor dan masing-masing agen tersebar secara acak sesuai lokasinya. Pada dasarnya algoritma ini mengumpulkan agen-agen dengan arah yang sama dari distributor ke dalam satu rute yang akan ditempuh oleh salah satu kendaraan. Langkah algoritma sweep adalah sebagai berikut.
1) Menetapkan  pusat  koordinat  sebagai  lokasi  distributor  dan  masing-masing  agen  digambarkan dalam koordinat kartesius sesuai lokasi.
2) Melakukan  konversi  dari  koordinat  kartesius  ke  dalam  koordinat  polar  untuk  mengetahui koordinat polar untuk setiap agen yang diketahui.
𝑟 = √𝑥 2 + 𝑦 2 𝜃 = 𝑎𝑟𝑐 tan ( 𝑦 𝑥 ) (6)
3) Membentuk  kelompok  dengan  memperhatikan  kapasitas  kendaraan  dimulai  dari  agen  dengan sudut polar paling kecil dan dilanjutkan berurutan sampai agen dengan sudut polar paling besar. Klasterisasi berhenti saat total permintaan satu kelompok melebihi kapasitas.
4) Mengulangi  langkah  3  untuk  membuat pengelompokan baru  dimulai  dari  agen  dengan  sudut polar  paling  kecil  dan  belum  tergabung  dalam  kelompok  sebelumnya.  Semua  agen harus terlayani oleh salah satu kendaraan, artinya harus masuk dalam salah satu kelompok (klaster).
2.4 Algoritma Particle Swarm Optimization (PSO)
Pada  tahun  1995,  Eberhart  dan  Kennedy  pertama  kali  memperkenalkan  algoritma Particle  Swarm Optimization (PSO)  [19]. Algoritma  ini  meniru perilaku sosial suatu kawanan  makhluk  hidup, seperti  ikan, burung,  lebah,  rayap,  atau  semut.  Masing-masing  individu  memiliki  perilaku  secara  terdistribusi  dengan memanfaatkan kecerdasan sendiri dan juga mendapat pengaruh dari perilaku kelompok [20]. Apabila seekor burung mendapati rute yang benar ke arah lokasi sumber makanan, maka anggota kelompok yang lain akan dapat  menyusul  dan  mengikuti  rute tersebut  meskipun  lokasinya  saling  berjauhan.  Dalam  konteks  optimasi multivariabel, diasumsikan bahwa koloni memiliki suatu ukuran dan posisi awal setiap individu tersebar secara acak di suatu ruang. Masing-masing individu mempunyai dua karakteristik, yaitu posisi dan kecepatan. Selama bergerak di dalam ruang,  individu akan  mengingat  dimana posisi terbaik  yang sebelumnya pernah  dilintasi. Setiap  individu  saling  bertukar  informasi  terkait  posisi  terbaiknya  kepada  individu  lain  dan  akan  mengatur ulang posisi dan kecepatannya.
Simulasi  algoritma  ini  dilakukan  dalam  ruang  berdimensi  hingga  dengan  beberapa  iterasi,  dimana posisi  partikel  di  masing-masing  iterasi  akan  semakin  mendekat  ke  tujuan  yang  dicari.  Santosa  [21] menjabarkan algoritma PSO ke dalam langkah-langkah berikut ini.
1) Misalkan 𝑁 adalah  jumlah  partikel  (ukuran  kelompok).  Ukuran 𝑁 yang  dipilih  sebaiknya  tidak terlalu besar untuk mengurangi penghitungan nilai fungsi dalam proses menemukan solusi dan juga tidak terlalu kecil sehingga diperoleh banyak posisi yang nantinya menuju solusi terbaik.
268
2) Populasi awal 𝑋 dibangkitkan secara acak dalam interval [𝑎, 𝑏] dan diperoleh 𝑋 1 , 𝑋 2 , … , 𝑋 𝑁 . Notasi 𝑋 𝑗 (𝑖) menyatakan partikel ke- 𝑗 pada iterasi ke- 𝑖 , sehingga 𝑋 1 (0), 𝑋 2 (0), . . . , 𝑋 𝑁 (0) adalah partikel- partikel  yang  terbnetuk  di  awal.  Hitung  nilai  fungsi  objektif  untuk  masing-masing  partikel  dan hasilnya dinyatakan dalam:
𝑓[𝑋 1 (0)], 𝑓[𝑋 2 (0)], . . . , 𝑓[𝑋 𝑁 (0)]
(7)
3) Hitung  kecepatan  masing-masing  partikel.  Setiap  partikel  memiliki  kecepatan  tertentu  saat bergerak menuju target. Diasumsikan semua partikel memiliki kecepatan awal sama dengan nol. Set iterasi 𝑖 = 1 .
4) Temukan  2  parameter  untuk  setiap  partikel 𝑗 pada  iterasi  ke- 𝑖 ,  yakni 𝑃 𝑏𝑒𝑠𝑡,𝑗 dan 𝐺 𝑏𝑒𝑠𝑡 .  Variabel 𝑃 𝑏𝑒𝑠𝑡,𝑗 adalah  nilai  terbaik  dari 𝑋 𝑗 (𝑖) sejauh  ini  dengan  nilai  fungsi  tujuan 𝑓[𝑋 𝑗 (𝑖)] paling  kecil yang didapat oleh partikel 𝑗 di iterasi sebelumnya. Variabel 𝐺 𝑏𝑒𝑠𝑡 adalah nilai terbaik dari semua partikel 𝑋 𝑗 (𝑖) yang didapat hingga iterasi ke- 𝑖 dengan nilai fungsi objektif paling kecil dari semua partikel-partikel pada proses iterasi-iterasi yang telah dilakukan sebelumnya.
5) Lakukan perbaruan kecepatan setiap partikel ke- 𝑗 pada iterasi ke- 𝑖 . 𝑉 𝑗 (𝑖) = 𝑉 𝑗 (𝑖 − 1) + 𝑐 1 𝑟 1 [𝑃 𝑏𝑒𝑠𝑡,𝑗 − 𝑥 𝑗 (𝑖 − 1)] + 𝑐 2 𝑟 2 [𝐺 𝑏𝑒𝑠𝑡 − 𝑥 𝑗 (𝑖 − 1)]
(8)
untuk 𝑗 = 1, 2, . . . , 𝑁 . Konstanta 𝑐 1 dan 𝑐 2 menyatakan kecerdasan sendiri (kognitif) dan pengaruh kelompok (sosial). Konstanta 𝑟 1 dan 𝑟 2 adalah bilangan acak berdistribusi uniform pada 0 dan 1.
6) Lakukan perbaruan posisi (koordinat) setiap partikel ke- 𝑗 pada iterasi ke- 𝑖 dengan rumus: 𝑋 𝑗 (𝑖) = 𝑋 𝑗 (𝑖 − 1) + 𝑉 𝑗 (𝑖)
(9)
untuk 𝑗 = 1, 2, . . . , 𝑁 . Selanjutnya hitung nilai fungsi objektif untuk masing-masing partikel yang diperbarui dan hasilnya dinyatakan dalam:
𝑓[𝑋 1 (𝑖)], 𝑓[𝑋 2 (𝑖)], . . . , 𝑓[𝑋 𝑁 (𝑖)]
(10)
7) Periksa kekonvergenan dari solusi yang diperoleh saat ini. Jika belum konvergen maka kembali ke langkah 4 untuk memperbarui  iterasi, 𝑖 = 𝑖 + 1 , yakni  mengevaluasi  nilai 𝑃 𝑏𝑒𝑠𝑡,𝑗 dan 𝐺 𝑏𝑒𝑠𝑡 yang baru. Iterasi terus dilanjutkan hingga semua partikel mengarah ke satu tujuan yang sama. Kriteria penghentian biasanya digunakan dengan membatasi iterasi, 𝑖 𝑚𝑎𝑥 .
2.5 Algoritma Nearest Neighbor (NN)
Untuk memecahkan masalah pembentukan rute perjalanan, Algoritma Nearest Neighbor merupakan salah satu algoritma heuristik yang dapat digunakan [22]. Algoritma ini membentuk rute distribusi dari satu titik awal (depot) ke sejumlah titik lainnya (agen) dan kembali ke depot. Setelah setiap agen dikelompokkan ke  dalam  beberapa  kelompok  agen  dengan  menggunakan  Algoritma Sweep ,  tahapan  selanjutnya  adalah membentuk  rute  untuk  masing-masing  kelompok.  Pembentukan  rute  untuk  setiap  kelompok  dengan menggunakan Algoritma NN dapat dilakukan dengan langkah-langkah sebagai berikut [23].
1) Lakukan proses inisialisasi dengan memilih depot sebagai titik awal keberangkatan.
2) Pilih agen yang belum dikunjungi dan memiliki jarak terdekat dengan depot saat ini. Tambahkan agen tersebut ke dalam rute.
3) Perbarui titik keberangkatan menjadi agen yang baru ditambahkan.
4) Ulangi langkah-langkah tersebut sampai semua agen dalam satu kelompok telah dikunjungi.
5) Setelah semua agen telah dikunjungi, tambahkan langkah terakhir untuk kembali ke depot. Depot menjadi titik terakhir dalam rute.

## 2.6 Evaluasi Rute Terbaik
Rute  yang  terbentuk  dari  Algoritma  PSO  dan  Algoritma  NN  selanjutnya  dibandingkan  untuk menentukan rute manakah yang terbaik. Dalam konteks CVRP, rute optimal adalah kombinasi perjalanan yang memenuhi  semua  kendaraan  dan  meminimalkan  jarak  tempuh  atau  waktu  tempuh,  serta  memenuhi  semua kendala  dan  batasan  yang  diberlakukan  [24].  Pada  penelitian  ini,  penentuan  rute  terbaik  berdasarkan  jarak tempuh kendaraan di masing-masing kelompok agen. Jarak antara titik ke- 𝑖 dan titik ke- 𝑗 , disimbolkan dengan 𝐷 𝑖,𝑗 , dapat dihitung dengan menggunakan rumus sebagai berikut:
𝐷 𝑖,𝑗 = √(𝑥 𝑗 − 𝑥 𝑖 ) 2 + (𝑦 𝑗 − 𝑦 𝑖 ) 2 (11)
269 dengan  ( 𝑥, 𝑦 )  menyatakan  lokasi  koordinat  suatu  titik.  Misalkan 𝐾 menyatakan  banyaknya  agen  di  suatu kelompok. Distributor sebagai titik awal keberangkatan diberi label 0, sekaligus sebagai titik terakhir dari suatu rute  diberi  label 𝐾 + 1 .  Agen  yang  pertama  dikunjungi  diberi  label  1,  agen  selanjutnya  diberi  label  2,  dan seterusnya hingga agen terakhir yang dikunjungi diberi label 𝐾 . Total jarak tempuh kendaraan dalam satu rute kelompok agen dapat dihitung dengan menggunakan rumus sebagai berikut.
𝑇 = ∑ 𝐷 𝑛,𝑛+1 𝐾
𝑛=0
(12)
Dengan menggunakan rumus tersebut akan dihitung total jarak tempuh kendaraan dari rute yang dibentuk oleh Algoritma  PSO  ( 𝑇 𝑃𝑆𝑂 )  dan  Algoritma  NN  ( 𝑇 𝑁𝑁 ).  Rute  terbaik  adalah  rute  yang  memberikan  jarak  tempuh paling pendek sehingga kendaraan akan membutuhkan waktu lebih singkat saat proses distribusi.

## 3. HASIL DAN PEMBAHASAN

## 3.1 Statistika Deskriptif
Dengan  melakukan randomisasi titik  menggunakan barisan Sobol diperoleh 100 titik  yang tersebar acak pada daerah pencarian sebagaimana ditampilkan dalam Gambar 1 dan lebih lengkapnya disajikan dalam tabel  di  Apendiks.  Proses  randomisasi  dilakukan  dengan  menggunakan  software  Matlab.  Selanjutnya  data lokasi  dan  permintaan  untuk  masing-masing  agen  dianalisis  dan  hasil  analisis  statistika  deskriptif  yang diperoleh ditunjukkan pada Tabel 1.
Tabel 1. Statistika Deskriptif Label N Mean Varians Std. Dev Min Max 𝑥 100 0,00 34,09 5,84 -9,97 9,88 𝑦 100 0,86 71,22 5,59 -9,97 9,90 𝑞 100 57,7 702,8 26,5 11,0 97,0
Nilai 𝑥 menyatakan absis dari lokasi agen pada sumbu- 𝑥 dan nilai 𝑦 menyatakan ordinat pada sumbu- 𝑦 . Nilai 𝑞 menyatakan banyaknya permintaan untuk masing-masing agen. Banyaknya nilai yang dibangkitkan adalah sama, yakni 100. Secara umum, lokasi agen terdistribusi dengan baik dan tersebar secara merata pada interval pencarian di bidang kartesius {(𝑥, 𝑦)| − 10 ≤ 𝑥, 𝑦 ≤ 10} .

## 3.2 Perbandingan Jarak Tempuh
Titik lokasi agen yang diperoleh dari randomisasi titik sebanyak 100 lokasi. Jumlah total produk yang diminta  oleh  masing-masing  agen  adalah  5.773  produk.  Dengan  menggunakan  algoritma  sweep  yang mengurutkan  sudut  polar  dimulai  dari  sudut  paling  kecil  hingga  sudut  polar  terbesar  berdasarkan  kapasitas maksimal kendaaran yakni 1.000 produk menghasilkan sebanyak 6 klaster. Proses menentukan klaster untuk masing-masing agen menggunakan software Matlab.
(a) Rute 1 dengan PSO                           (b) Rute 1 dengan NN
270
(c) Rute 2 dengan PSO                           (d) Rute 2 dengan NN
(e) Rute 3 dengan PSO                           (f) Rute 3 dengan NN
Gambar 3. Rute yang terbentuk pada klaster 1, 2 dan 3 dengan algoritma PSO dan algoritma NN
Tahap  selanjutnya  adalah  menentukan  rute  untuk  masing-masing  klaster.  Proses  penentuan  rute dilakukan menggunakan dua metode, yaitu algoritma PSO dan algoritma NN sebagai pembanding mengingat algoritma NN adalah algoritma yang paling sering digunakan dengan hanya mempertimbangkan titik terdekat untuk dilalui selanjutnya. Rute dimulai dari distributor dan nantinya akan kembali ke distributor setelah semua agen di masing-masing klaster telah dilewati. Rute yang terbentuk dari algoritman PSO dan NN untuk klaster 1, 2 dan 3 ditampilkan di Gambar 3, sedangkan rute untuk klaster 4, 5 dan 6 ditampilkan di Gambar 4.
(a) Rute 4 dengan PSO                         (b) Rute 4 dengan NN
(c) Rute 5 dengan PSO                         (d) Rute 5 dengan NN
(e) Rute 6 dengan PSO                         (f) Rute 7 dengan NN
Gambar 4. Rute yang terbentuk pada klaster 4, 5 dan 6 dengan algoritma PSO dan algoritma NN
Pada Gambar 3 dan Gambar 4, rute yang dibentuk untuk masing-masing klaster oleh algoritma PSO ditunjukkan oleh garis lurus di gambar kiri (a,c,e). Sedangkan hasil dari algoritma NN ditunjukkan oleh garis putus-putus di gambar kanan (b,d,f). Secara umum rute yang dihasilkan oleh algoritma PSO membentuk kurva tertutup  sehingga  menghasilkan  panjang  lintasan  yang  lebih  pendek  jika  dibandingkan  dengan  rute  yang dibentuk  oleh  algoritma  NN.  Rute  yang  dihasilkan  algoritma  NN  memuat  beberapa  perpotongan  lintasan sehingga  mengakibatkan  jarak  tempuh  yang  lebih  jauh  dan  tentu  saja  tidak  efektif  digunakan  untuk  proses distribusi produk. Perpotongan ini muncul karena landasan utama pemilihan lokasi kunjungan berikutnya dari algoritma  NN  adalah  titik  terdekat  dari  titik  sebelumnya.  Gabungan  dari  semua  rute  yang  diperoleh  dari algoritma PSO untuk masing-masing klaster ditampilkan di Gambar 5.
Tabel 2. Perbandingan Jarak Tempuh Rute Banyak Agen Total Permintaan Jarak PSO Jarak NN Persentase Efisiensi 1 17 931 34,718 38,039 91,27% 2 17 934 38,112 43,689 87,23% 3 16 992 35,629 41,294 86,28% 4 17 972 31,955 43,912 72,77% 5 18 985 39,205 40,152 97,64% 6 15 959 38,496 47,413 81,19% Total 100 5.773 218,115 254,499 85,70%
Gambar 5. Rute distribusi produk yang terbentuk dari algoritma PSO
Dari semua klaster yang dibentuk menggunakan algoritma sweep sebelumnya, algoritma PSO mampu menghasilkan  rute  dengan  jarak  lebih  pendek  dibandingkan  rute  dari  algoritma  NN.  Perbandingan  jarak tempuh, persentase efisiensi rute dan total produk untuk masing-masing rute disajikan dalam Tabel 2.
272
Dari algoritma PSO, rute dengan jarak terpendek adalah rute 4 yang melayani 17 agen dengan jarak 31,955 satuan, sedangkan jarak terpanjang adalah rute 5 yang melayani 18 agen dengan jarak 39,205 satuan. Rute 6 melayani agen dengan jumlah paling sedikit, yakni 16 agen dengan total permintaan 959 produk. Secara keseluruhan, total jarak rute semua klaster yang diperoleh dari PSO adalah 85,70% dari total jarak rute yang dihasilkan  NN.  Berdasarkan  persentase  efisiensi,  rute  hasil  PSO  dengan  efisiensi  terbaik  dibandingkan  rute hasil NN ditunjukkan oleh rute 4, yakni jarak rute hasil PSO adalah 72,77% dari jarak rute hasil NN. Pada rute 5, algoritma NN menghasilkan rute yang baik dan mendekati rute yang dihasilkan oleh algoritma PSO, dimana hal ini tidak ditunjukkan di rute lain.
Dalam  menentukan  suatu  rute  distribusi,  aspek  penting  selain  jarak  tempuh  adalah  biaya  yang dikeluarkan  dan  waktu  tempuh  kendaraan.  Mengingat  penelitian  ini  tidak  menggunakan  data  riil,  maka diasumsikan  bahwa  waktu  tempuh  adalah  hasil  pembagian  jarak  dengan  kecepatan  konstan  kendaraan  saat proses  distribusi  dan  biaya  diperoleh  dari  biaya  penggunaan  bahan  bakar  dengan  asumsi  jarak  yang  sama membutuhkan  bahan  bakar  dengan  jumlah  sama.  Penelitian  lanjutan  dapat  dikembangkan  dengan menggunakan data sebenarnya dan memperhatikan waktu tempuh dan biaya sesuai dengan kondisi jalan dan tingkat kesulitan masing-masing rute yang tentunya berbeda satu dengan lainnya.
Hasil yang diperoleh dalam penelitian ini sejalan dengan hasil beberapa penelitian sebelumnya, yakni algoritma PSO adalah salah satu algoritma yang cukup efektif dalam menentukan rute distribusi terbaik pada masalah CVRP. Penelitian yang dilakukan oleh Utami [25] menunjukkan bahwa algoritma PSO menghasilkan rute  dengan  jarak  tempuh  45,33%  lebih  pendek  dan  efisiensi  biaya  sebesar  7,08%  dalam  sekali  perjalanan. Hannan dkk. [26] melakukan penelitian tentang penjadwalan pengumpulan sampah dan diperoleh hasil bahwa algoritma  PSO  menghasilkan  rute  dengan  efisiensi  sebesar  70-75%.  Hasil  serupa  juga  ditunjukkan  oleh Venkatesan  dkk.  [9]  bahwa  PSO  mampu  membangun  rute  untuk  melayani  pelanggan  dengan  jarak tempuh minimum dan kapasitas kendaraan maksimum sehingga efisiensi rute lebih baik.

## 4. PENUTUP
Penelitian  ini  untuk  memberikan  alternatif  solusi  dalam  menentukan  rute  distribusi  dalam  masalah CVRP  untuk  menghasilkan  rute  dengan  jarak  tempuh  terpendek.  Data  yang  digunakan  dibangun  melalui randomisasi titik dengan barisan Sobol dan diperoleh 100 lokasi agen yang tersebar acak di daerah pencarian. Pembentukan  kluster  dilakukan  dengan  menggunakan  algoritma  sweep  dan  menghasilkan  6  kluster. Pembentukan  rute  untuk  masing-masing  kluster  dilakukan  dengan  menggunakan  algoritma  PSO.  Sebagai pembanding,  algoritma nearest  neighbor (NN)  juga  digunakan  untuk  menentukan  rute  pada  setiap  kluster. Total jarak tempuh rute hasil PSO adalah 85,70% dari total jarak rute hasil NN, yang artinya memiliki efisiensi jarak sebesar 14,30%. Waktu tempuh dan biaya sebanding dengan jarak tempuh kluster.
Penelitian ini dapat dikembangkan lebih lanjut dalam berbagai aspek. Dengan menggunakan data riil, waktu tempuh dan biaya dapat dipengaruhi oleh kondisi medan dan tingkat kesulitan akses. Dalam beberapa kasus  dapat  ditambahkan  kendala  seperti  kemacetan  lalu  lintas  dan  emisi  karbon  untuk  pengiriman  produk dingin  menggunakan  lemari  pendingin.  Dari  aspek  metode,  pembentukan  kluster  menggunakan  algoritma sweep dapat dikembangkan lebih adaptif sehingga tidak selalu dimulai dari arah sumbu- 𝑥 positif.

## DAFTAR PUSTAKA
[1] Putri,  W.  E.,  Syahputra,  T.,  &  Rahmadiansyah,  D. (2020).  Sistem  Pendukung  Keputusan  Menentukan Prioritas Distribusi Rokok Di  Wilayah  Langkat Pada PT. Surya  Kekal Mandiri Menggunakan Metode Multi Objective Optimization On The Basis Of Ratio Analysis (MOORA). Jurnal Cyber Tech , 3 (5), 844– 855.
[2] Ruauw,  E.  (2015).  Kajian  distribusi  pangan  pokok  beras  di  Kabupaten  Kepulauan  Talaud. Agri- Sosioekonomi , 11 (1), 58–68.
[3] Muhammad, M., Bakhtiar, B., & Rahmi, M. (2017). Penentuan rute distribusi sirup untuk meminimalkan biaya transportasi. Industrial Engineering Journal , 6 (1).
[4] Cahyaningsih,  W.  K., Sari, E. R., & Hernawati,  K. (2015). Penyelesaian  Capacitated Vehicle  Routing Problem (Cvrp) Menggunakan Algoritma Sweep Untuk Optimasi Rute Distribusi Surat Kabar Kedaulatan Rakyat. Seminar Nasional Matematika Dan Pendidikan Matematika UNY , 1–8.
[5] Arifta, E., & Rakhmawati, F. (2023). Analysis of Book Distribution Routes Using the Capacity Vehicle Routing Problem (CVRP) Method Using the Sweep Algorithm. Sinkron: Jurnal Dan Penelitian Teknik Informatika , 8 (1), 360–367.
273
[6] Hanafi,  R.,  Rusman,  M.,  Mardin,  F.,  Parenreng,  S.  M.,  &  Azzazli,  A.  (2020).  Distribution  Route Optimization of a Capacitated Vehicle Routing Problem by Sweep Algorithm. IOP Conference Series: Materials Science and Engineering , 875 (1), 12066.
[7] Fitriani,  N.  A.,  Pratama,  R.  A.,  Zahro, S.,  Utomo, P.  H.,  &  Martini,  T.  S. (2021).  Solving  capacitated vehicle routing problem using saving matrix, sequential insertion, and nearest neighbor of product ‘X’in Grobogan district. AIP Conference Proceedings , 2326 (1), 20007.
[8] Kao, Y., & Chen, M. (2013). Solving the CVRP problem using a hybrid PSO approach. Computational Intelligence:  Revised  and  Selected  Papers  of  the  International  Joint  Conference,  IJCCI  2011,  Paris, France, October 24-26, 2011 , 59–67.
[9] Venkatesan,  S.  R.,  Logendran,  D.,  &  Chandramohan,  D.  (2011).  Optimization  of  capacitated  vehicle routing  problem  using  PSO. International  Journal  of  Engineering  Science  and  Technology  (IJEST) , 3 (10), 7469–7477.
[10] Mohammed, M. A., Ahmad, M. S., & Mostafa, S. A. (2012). Using genetic algorithm in implementing capacitated vehicle routing problem. 2012 International Conference on Computer & Information Science (ICCIS) , 1 , 257–262.
[11] Wang, C.H., & Lu, J.Z. (2009). A hybrid genetic algorithm that optimizes capacitated vehicle routing problems. Expert Systems with Applications , 36 (2), 2921–2936.
[12] Krueger, R. A. (2014). Focus groups: A practical guide for applied research. Sage publications.
[13] Kucherenko, S. (2008). High dimensional Sobol’s sequences and their application. In Technical Report. Technical Report.
[14] Joe,  S.,  &  Kuo,  F.  Y.  (2008).  Constructing  Sobol  sequences  with  better  two-dimensional  projections. SIAM Journal on Scientific Computing, 30 (5), 2635-2654.
[15] Ralphs, T. K., Kopman, L., Pulleyblank, W. R., & Trotter, L. E. (2003). On the capacitated vehicle routing problem. Mathematical Programming , 94 , 343–359.
[16] Pratikno,  S.  R.  I.  B.  B.  (2017).  Implementasi  Algoritma  Floyd-Warshall  Untuk  Menentukan  Rute Tercepat Pada Jalur Distribusi Jasa Pengiriman Barang. Universitas Negeri Jakarta.
[17] Altabeeb,  A.  M.,  Mohsen,  A.  M.,  Abualigah,  L.,  &  Ghallab,  A.  (2021).  Solving  capacitated  vehicle routing problem using cooperative firefly algorithm. Applied Soft Computing , 108 , 107403.
[18] Nono,  V.,  Sofitra,  M.,  &  Wijayanto,  D.  (2020).  Penyelesaian  Capacitated  Vehicle  Routing  Problem Dengan  Menggunakan  Algoritma Sweep Untuk Penentuan  Rute Distribusi Untuk Depo Pt. Abc  Kubu Raya. Jurnal TIN Universitas Tanjungpura , 4 (2).
[19] Wati, D. A. R., &  Rochman, Y. A. (2013). Model Penjadwalan  Matakuliah Secara Otomatis Berbasis Algoritma Particle Swarm Optimization (PSO). Jurnal Rekayasa Sistem Industri , 2 (1), 22–31.
[20] Muhammad,  R.  D.  (2016).  Metode  Particle  Swarm  Optimization  Untuk  Mengontrol  Frekuensi  Pada Hibrid Wind-Diesel. Jurnal INTAKE: Jurnal Penelitian Ilmu Teknik Dan Terapannya , 7 (2), 1–13.
[21] Santosa, B. (2006). Tutorial particle swarm optimization. Sukolilo Surabaya: Kampus ITS , 66 .
[22] Taiwo, O. S., Josiah, O., Taiwo, A., Dkhrullahi, S., & Sade, O. K. (2013). Implementation of heuristics for  solving  travelling  salesman  problem  using  nearest  neighbor  and  nearest  insertion  approaches. International Journal of Advance Research , 1(3), 139-155.
[23] Rozalina, A., Uslianti, S., & Anggela, P. (2020). Optimasi Rute Distribusi Dengan Penyelesaian Vehicle Routing Problem Menggunakan Algoritma Sweep Pada PD. XYZ Di Pontianak. Jurnal TIN Universitas Tanjungpura , 4(1).
[24] Cattaruzza, D., Absi, N., & Feillet, D. (2018). Vehicle routing problems with  multiple trips. Annals of Operations Research, 271 , 127-159.
[25] Utami,  A.  P.  (2022).  Optimasi  CVRP  Pada  Industri  Automotive  Spare  Parts  Dengan  Membandingkan Metode Sweep Algorithm & PSO. Universitas Mercu Buana Jakarta-Menteng.
[26] Hannan, M.  A., Akhtar, M., Begum, R. A., Basri, H., Hussain, A., & Scavino, E. (2018). Capacitated vehicle-routing problem  model  for scheduled solid waste collection and route optimization using PSO algorithm. Waste Management , 71 , 31–41.