## ANALISIS PERBANDINGAN ALGORITMA WARSHALL DAN DIJKSTRAA PADA METODE GVRP DALAM PENENTUAN RUTE TERPENDEK (STUDI KASUS : PT YAKULT CABANG SUMBAWA)
Berry Firmansyah 1 , Koko Hermanto 2*
1,2 Program Studi Teknik Industri, Fakultas Teknik Universitas Teknologi Sumbawa *Corresponding Author email: koko.hermanto@uts.ac.id
Diterima  :
Bulan Januari 2021
Diterbitkan :
Bulan Februari 2021 Keyword : Rute terpendek, General Vehicle Problem, Algoritma Warshall, Algoritma Dijkstraa

## Abstrak
Yakult merupakan salah satu perusahan industri besar yang bergerak di bidang pembuatan susu  permentasi.  Perusahaan  ini  memiliki  aktivitas  usaha  yaitu  menjual  dan mendistribusikan  susu  permentasi  kepada  Toko-toko.  Tujuan  penelitian  ini  yaitu menganalisis perbandingan Algoritma Warshall dan Dijkstraa pada metode GVRP dalam penentuan  rute  terpendek.  Adapun  metode  General  Vehicle  Routing  Problem  (GVRP) dipakai  untuk  memudahkan  dalam  mengelompokan  banyak  toko  (vertek)  menjadi berbagai  kelompok  (kluster)  sehingga  dapat  menentukan  rute  optimal  dan  biaya  yang minimal. Algoritama Warshall merupakan metode yang memudahkan untuk menentukan rute terpendek dari semua titik ke semua titik serta memiliki metode yang sederhana dan mudah diimplementasikan. Sementara algoritma Dijkstraa adalah metode untuk mencari jalur terpendek antara 2 titik dari titik awal ke titik tujuan. Dalam penelitian ini dianalisis bahwa algoritma Warshall dan Dijkstraa untuk penentuan rute terpendek memiliki cara perhitungan  dan  hasil  yang  hampir  sama  dengan  selisih  total  jarak  800  meter  dengan selisih biaya Rp 645 dalam sekali jalan. Perbedaan rute hanya berada pada kluster 6 dan kluster 9. Kesimpulan penelitian ini menunjukkan bahwa baik Algoritma Warshall dan Algoritma Dijkstraa memiliki cara perhitungan yang hampir sama dengan total jarak dan biaya memiliki selisih yang relatif kecil.

## PENDAHULUAN
Dalam  dunia  bisnis,  banyak  aspek  yang mempengaruhi  keberhasilan  suatu  perusahaan dalam  bertahan  dan  bersaing  yaitu  di  bidang pemasaran,  produksi  serta  proses  sistem  distribusi. Salah satu  aspek yang mempengaruhi  keberhasilan pada  perusahaan  adalah  sistem  transportasi  dan distribusi.  Transportasi  dan  distribusi  merupakan dua komponen yang selalu mempengaruhi keunggulan  kompotitif  suatu  perusahaan  karena penurunan  biaya  tansportasi  dapat  meningkatkan keuntungan perusahaan secara tidak langsung.
Ada  berbagai  macam  perusahaan  industri yang  ada  di  kabupaten  Sumbawa,  salah  satunya perusahaan  susu  permentasi  yaitu  Yakult.  Yakult merupakan salah satu perusahan industri besar yang bergerak  di  bidang  pembuatan  susu  permentasi. Perusahaan  ini  memiliki  aktivitas  usaha  yaitu menjual  dan  mendistribusikan  susu  permentasi kepada  toko-toko  dalam  kegiatan  operasional usahanya.  Salah  satu  kantor  cabang  berada  di Kabupaten  Sumbawa  dengan  wilayah  distribusi meliputi daerah-daerah sekitar Sumbawa.
Oleh  karena  itu,  diperlukan  strategi  yang tepat  yang  diperlukan  untuk  menekan  biaya  rute distribusi seminimal mungkin. Dalam mendistribusikan  produk  ke  berbagai  daerah tentunya  membutuhkan  biaya  transportasi  yang tidak sedikit jumlahnya.
Mengetahui akan pentingnya proses pendistribusian  yang  tepat,  maka  penelitian  ini dilakukan  untuk  membandingkan  berbagai  metode terhadap  rute  distribusi  pada  perusahaan  Yakult dalam mencari solusi  agar biaya distribusi menjadi optimal. Dari latar belakang tersebut, maka penulis menggunakan  metode  General  Vehicle  Routing Problem  (GVRP),    Algoritma  Warshall  dan Algoritma  Dijkstraa  untuk  mengolah  data  dan mencari  rute  terpendek.  Karena  pada  metode  ini memiliki  kelebihan  yaitu:    menurut  Petrica  (2011) metode GVRP memudahkan dalam mengelompokan  banyak  toko  (vertek)  menjadi berbagai  kelompok  (kluster)  agar  memudahkan dalam  menentukan  rute  optimal  dan  biaya  yang minimal. Algoritama Warshall adalah metode yang memudahkan  menentukan  rute  terpendek  dari semua  titik  ke  semua  titik  serta  memiliki  metode yang  sederhana  dan  mudah  diimplementasikan. Sementara  Algoritma  Dijkstraa  digunakan  untuk mencari jalur terpendek antara 2 titik dari titik awal ke titik tujuan (Jong Jek Siang, 2014).
Beberapa penelitian tentang model general vehicle  routing  problem (GVRP)  dengan  metode Djikstra dalam pengaplikasiannya dalam kehidupan sehari-hari,  seperti  yang  penah  diaplikasikan  oleh Hermanto  &  Ermayanti  (2019)  dan  Gautama  & Hermanto (2020) pada penentuan rute terpendek bus sekolah. Selain itu juga aplikasi  model GVRP dapat
digunakan  dalam  menentukan  rute  terpendek pendistribusian sampah yang pernah dilakukan oleh Hermanto  &  Ruskartina  (2018)  dan  Hermanto  & Ruskartina (2018b) serta dapat juga diaplikan dalam penentuan  rute  terpendek  pendistribusian  gas  LPG seperti yang dilakukan oleh Hermanto et al (2020).

## LANDASAN TEORI

## Teori Graf
Graf adalah objek abstrak matematis, yang mana  mengandung  vertek  dan  edge.  Edge menghubungkan  sepasang  vertek.  Di  sepanjang edge  yang  ada  pada  graf  memungkinkan  bergerak dari satu vertek ke vertek lainnya. Tergantung pada apakah  atau  tidak  seseorang  dapat  berjalan  di sepanjang edge oleh kedua sisi atau hanya satu sisi tergantung  graf  tersebut  merupakan  directed  graf atau undirected graf (Magzhan & Jani, 2013).

## General Vehicle Routing Problem (GVRP)
Penggunaan GVRP dimaksudkan untuk mencari  rute  terpendek  yang  direpresentasikan dengan  sebuah  graf  berarah G =  (V,A) dengan V= {1,2,3,…..n } sebagai himpunan vertek dan A={(i,j)|i,j ∊ V, i≠j} himpunan edge. Nilai c ij tidak bernilai  negatif  untuk  setiap  edge (i,j) ∊ A , himpunan  vertek  dibagi  menjadi  k+1  himpunan bagian  tak  kosong  saling  esklusif,  yang  disebut dengan kluster V 0 ,V 1 ,V 2 ,……. V k (V = V 0 ∪ V 1 ∪ … ∪ V k dan  V l ∩ V p = ∅ untuk semua l, p ∈ {0,  l,  ... k} dan  l  ≠ p. Kluster V 0 hanya memiliki satu vertek 0, yang  mewakili  depot  dan  n  sisa  vertek-verteknya terbagi menjadi k kluster, yang mewakili konsumen yang  tersebar  secara  geografis  (Petrica  C.  Pop  dan Andrei  Horvat-Marc,  2012) . Ilustrasi GVRP dan solusi layak yang merupakan lanjutan dari masalah GVRP , yang dapat dilihat pada Gambar 1.
Gambar 1. Contoh solusi layak GVRP Sumber : Hermanto, 2015.

## Algoritma Warshall
Algoritma  Warshall  merupakan  algoritma yang  lebih  efisien  untuk  mencari  jarak  terpendek dari semua titik ke semua titik. Algoritma warshall untuk  mecari  path  terpendek  merupakan  algoritma yang  sederhana  dan  mudah  implementasinya. Prinsip  dasarnya  tidak  jauh  berbeda  dengan algoritma Dijkstraa. Pada iterasi ke-1, dihitung jarak terpendek  dari  semua  titik  ke  semua  titik  apabila path -nya melalui titik 𝑉 𝑖 .
Algoritma  warshall  untuk  mecari  path  terpendek adalah sebagai berikut :
1. 𝑊 = 𝑊 (0)
2. Untuk k = 1 hingga n, lakukan: {pengujian jarak lewat titik 𝑉 𝑘 } Untuk I = 1 hingga n, lakukan: Untuk j = 1 hingga n lakukan: Jika 𝑊 𝑖𝑗 > 𝑊 𝑖,𝑘 > 𝑊 𝑘𝑗 maka  tukar 𝑊 𝑖𝑗 dengan 𝑊 𝑖,𝑘 + 𝑊 𝑘𝑗 3. 𝑊 ∗ = 𝑊

## Algoritma Dijkstraa
Algoritma Dijkstraa ditemukan oleh Edsger Dijkstraa pada tahun 1959, adalah algoritma pencarian  graf  yang  memecahkan  masalah  jalur terpendek  yang  bersumber  dari  satu  vertek  untuk sebuah graf dengan bobot vertek tidak boleh negatif (Asti,  2013).  Analisis  dilakukan  dengan  cara memeriksa  vertek  dengan  bobot  terkecil  dan memasukkannya ke dalam himpunan solusi dengan awal pencarian vertek asal membutuhkan pengetahuan  tentang  semua  jalur  dan  bobotnya, sehingga  dibutuhkan  pertukaran  informasi  dengan semua vertek.

## METODE PENELITIAN
Analisis  terhadap  hasil  pengolahan  data  untuk analisis  perbandingan  Algoritma  Warshall dan Dijkstraa  pada Generalized  Vehicle  Routing Problem  (GVRP) dalam  penentuan  rute  terpendek, maka perlu di lakukan sebagai berikut :
1. Data  yang  sudah  dikumpulkan  langsung diolah  menggunakan  metode GVRP dan Algoritma Warshall :
a. Memodelkan dalam bentuk  graf yaitu model GVRP
b. Gunakan  Algoritma  Warshall untuk menyusun  model CGVRP dari  studi kasus
2. Menganalisis  perbandingan  rute  usulan berupa contoh penerapan beberapa metode dalam menentukan rute terpendek terhadap rute distribusi Yakult dalam kota sumbawa.
1 2 3 0 4 5 6 10 7 8 9 11 V 5 V 1 V 4 q 2 =9 V 3 q 1=12 V 2 q 3 =5 q 4 =11 V 0 q 0=0 d 1 = 3 d 2 = 5 d 3 = 4 d 4 = 5 d 5 = 4 d 6 = 5 d 7 = 2 d 10 = 3 d 9 = 4 d 8 = 2 d 11 = 7 q 5 = 7 K = 2 dan Q = 25

## HASIL DAN PEMBAHASAN

## Deskripsi Masalah
Depot  atau  gudang  Yakult  beralamat  Jl. Labu  Punti,  Karang  Dima,  Labuhan  Badas, Kabupaten  Sumbawa,  Nusa  Tenggara  Barat  dan terletak pada posisi geografis 8°28'06.8"S 117°22'40.1"E, merupakan perusahaan yang bergerak  dalam  pembuatan  dan  pengiriman  susu fermentasi. Proses pendistribusian dilakukan dengan mengirimkan Yakult ke toko-toko langganan. Pendistribusian yakult di kota Sumbawa menggunakan  1  kendaraan  mobil  box  yang menempuh  8  km  meter  per  liter  dengan  kapasitas
muatan  4400  pack  yakult  yang  berbahan  bakar bensin  dengan  harga  bensin  Rp  6.450  pada  tahun 2019.  Perhitungan  biaya  didapatkan  dengan  cara
menghitung total jarak dibagi jarak tempuh per liter dikali  dengan  harga  bensin.  Jarak  setiap  terminal ditentukan menggunakan google maps dengan tetap memperhatikan jarak yang sebenarnya.

## Simulasi Penyelesaian kasus Model GVRP
Setiap toko tujuan dikelompokan berdasarkan  masing-masing  kelurahan.  Kelurahan definisikan sebagai kluster, kluster disusun berdasarkan  jarak  terdekat  dari  depot  sedangkan toko  definisikan  sebagai  vertek.  Pengelompokkan tetap  memperhatikan  kapasitas  kendaraan  dan  bila melebihi kapasistas harus menggunakan kendaraan lain.  Jumlah  toko  dan  pengelompokkan  sesuai
kelurahan. Dapat diilustrasikan lokasi dan pengelompok  pada  gambar  seperti  Gambar  2 berikut:
Gambar 2 . Pengelompokkan toko Berdasarkan Gambar 2
setelah dikelompokan  selanjutnya  dimodelkan  rute  GVRP yaitu langkah pertama menentukan satu titik tujuan dari  vertek  0  ke  semua  vertek  yang  ada  dan  yang memiliki  jarak  terdekat  dengan  vertek  0  dan diperoleh  vertek  terdekat  yaitu  vertek  29  yang mewakili kluster 1, langkah kedua menentukan satu titik  akhir  dari  semua  vertek  yang  ada  ke  vertek 0 dan  yang  memiliki  jarak  terdekat  dengan  vertek  0 kecuali kluster 1 karena sudah dipilih dan diperoleh vertek  terdekat  yaitu  vertek  16  yang  mewakili kluster  2.  Langkah  ketiga  menentukan  titik  tujuan dari vertek 29 ke semua vertek kecuali kluster yang telah  terpilih  dan  diproleh  vertek  terdekat  yaitu vertek  19  yang  mewakili  kluster  3  dan  seterusnya dilakukan  dengan  langkah  yang  sama.  Setelah semua kluster mempunyai masing-masing titik awal yang  telah  dipilih  sehingga  pemodelan  GVRP  di ilustrasikan pada gambar 3.

## Menentukan rute terpendek menggunakan
Algoritma Warshall
Perhitungan  solusi  optimal  menggunakan  model CGVRP dan Algoritma Warshall dari model GVRP:
a. Penyelesaian pada kluster 1 Berdasarkan model GVRP diatas sudah dipilih titik awal pada kluster 1 yaitu vertek 29. i= 𝑣 29 , 𝑣 36 , 𝑣 46 , 𝑣 51 , 𝑣 52 j= 𝑣 29 , 𝑣 36 , 𝑣 46 , 𝑣 51 , 𝑣 52 𝑣 29 𝑣 36 𝑣 46 𝑣 51 𝑣 52 𝑣 29 𝑣 36 𝑣 46 𝑣 51 𝑣 52 [
∞ 1900 1000 4500 350 1900 ∞ 900 4100 1600 1000 4500 350 900 4100 1600 ∞    3500 650 3500 ∞ 3700
650 3700 ∞ ]
W=
Gambar 3 Model GVRP
Dari  matriks  diatas  langkah  selanjutnya  pada perhitungan  Algoritma  Warshall  yaitu  melakukan iterasi  untuk  mencari  jarak  terdekat  untuk  setiap vertek, karena jarak terdekat setiap vertek sudah ada maka tidak perlu lagi melakukan iterasi. Selanjutnya untuk  mencari  rute  teroptimal  yang  melalui  semua vertek  dengan  menggunakan  matrik  Z.  Matrik  Z berfungsi untuk menentukan titik tujuan dari vertek awal  dengan  memilih  jarak  yang  paling  kecil  dari vertek yang ada kecuali yang sudah terpih.
𝑣 29 𝑣 36 𝑣 46 𝑣 51 𝑣 52 𝑣 29 𝑣 36 𝑣 46 𝑣 51 𝑣 52 [ 𝑣 52 𝑣 52 𝑣 52 𝑣 52 𝑣 52 𝑣 51 𝑣 51 𝑣 51 𝑣 51 𝑣 51 𝑣 36 𝑣 46 𝑣 46 𝑣 36 𝑣 46 𝑣 46 𝑣 36 𝑣 36 𝑣 36 𝑣 46 𝑣 46 𝑣 46 𝑣 46 𝑣 46 𝑣 46 ] Z=
Berdasarkan  matrik  Z  diketahui  rute terpendek 𝑣 29 - 𝑣 52 - 𝑣 46 - 𝑣 36 - 𝑣 51 dengan  total jarak 6000 meter.
Setelah  melakukan  perhitungan  dengan  cara yang sama pada semua kluster didapatkan data dari perhitungan masing-masing kluster dengan menggunakan GVRP setelah itu mengunakan model CGVRP dalam  menghitung  didalam  kluster  dan untuk  menentukan  urutan  vertek  yang  dilalui
didalam  kluster  menggunakan Algoritma  Warshall didapatkan  keselurahan  rute  terpendek  yang digunakan  dalam  pendistribusian.  Dengan  rute terpendek sebagai berikut:
𝑣 0 - 𝑣 29 - 𝑣 52 - 𝑣 46 - 𝑣 36 - 𝑣 51 - 𝑣 19 - 𝑣 20 - 𝑣 25 - 𝑣 45 - 𝑣 34 - 𝑣 32 - 𝑣 31 - 𝑣 10 - 𝑣 22 - 𝑣 38 - 𝑣 37 - 𝑣 43 - 𝑣 9 - 𝑣 8 - 𝑣 35 - 𝑣 24 - 𝑣 39 - 𝑣 12 - 𝑣 33 - 𝑣 23 - 𝑣 48 - 𝑣 21 - 𝑣 41 - 𝑣 14 - 𝑣 1 - 𝑣 44 - 𝑣 28 - 𝑣 7 - 𝑣 6 - 𝑣 3 - 𝑣 47 - 𝑣 30 - 𝑣 4 - 𝑣 5 - 𝑣 15 - 𝑣 26 - 𝑣 27 , 𝑣 18 , 𝑣 13 , 𝑣 17 , 𝑣 11 - 𝑣 53 - 𝑣 2 - 𝑣 50 - 𝑣 54 - 𝑣 40 - 𝑣 49 - 𝑣 42 - 𝑣 16 - 𝑣 0 dengan total jarak sebesar 49400 meter. Dari  hasil  perhitungan  rute  terpendek  dapat diilustrasikan pada gambar 4.

## Menentukan  rute  terpendek  menggunakan Algoritma Dijkstraa
Perhitungan  solusi  optimal  menggunakan  model CGVRP dan Algoritma Dijkstraa dari model GVRP:
a. Penyelesaian pada kluster 1 Berdasarkan model GVRP diatas sudah dipilih titik awal pada kluster 1 yaitu vertek 29. i= 𝑣 29 , 𝑣 36 , 𝑣 46 , 𝑣 51 , 𝑣 52 j= 𝑣 29 , 𝑣 36 , 𝑣 46 , 𝑣 51 , 𝑣 52 𝑣 29 𝑣 36 𝑣 46 𝑣 51 𝑣 52
𝑣 29 𝑣 36 𝑣 46 𝑣 51 𝑣 52 [ ∞ 1900 1000 4500 350 1900 ∞ 900 4100 1600 1000 4500 350 900 4100 1600 ∞    3500 650
3500 ∞ 3700
650 3700 ∞ ] W=
Berdasarakan  data  matrik  tersebut  selanjutnya melakukan itersi yang diilustrasikan dalam tabel 1.
Gambar 4. Model C GVRP menggunakan perhitungan Algoritma Warshall
Tabel 1 Iterasi penyelesaian kluster 1 i D(29) D(36) D(46) D(51) D(52) L 0 0 ∞ ∞ ∞ ∞ 𝑣 29 1 - Min{∞,0+1900} =1900 Min{∞,0+1000 } =1000 Min{∞,0+450 0} =4500 Min{∞,0+350 } =350 𝑣 29 , 𝑣 52 2 - Min{1900,350+ 1600} =1900 Min{1000,350+ 650} =1000 Min{4500,350 +3700} =4050 - 𝑣 29 , 𝑣 52 , 𝑣 46 3 - Min{1900,1000 +900} =1900 - Min{4050,100 0+3500} =4050 - 𝑣 29 , 𝑣 52 , 𝑣 46 , 𝑣 36 4 - - - Min{4050,190 0+4100} =4050 - 𝑣 29 , 𝑣 52 , 𝑣 46 , 𝑣 36 , 𝑣 51
Keterangan  =        Rute Terpilih
Berdasarkan  tabel  diatas  diketahui  rute  terpendek 𝑣 29 - 𝑣 52 - 𝑣 46 - 𝑣 36 - 𝑣 51 dengan  total  jarak  6000 meter.
Setelah  melakukan  perhitungan  dengan  cara yang sama pada semua kluster didapatkan data dari perhitungan masing-masing kluster dengan menggunakan GVRP setelah itu mengunakan model CGVRP dalam  menghitung  didalam  kluster  dan untuk  menentukan  urutan  vertek  yang  dilalui didalam  kluster  menggunakan Algoritma  Dijkstraa didapatkan  keselurahan  rute  terpendek  yang
digunakan  dalam  pendistribusian.  Dengan  rute terpendek sebagai berikut:
𝑣 0 - 𝑣 29 - 𝑣 52 - 𝑣 46 - 𝑣 36 - 𝑣 51 - 𝑣 19 - 𝑣 20 - 𝑣 25 - 𝑣 45 - 𝑣 34 - 𝑣 32 - 𝑣 31 - 𝑣 10 - 𝑣 22 - 𝑣 38 - 𝑣 37 - 𝑣 43 - 𝑣 9 - 𝑣 8 - 𝑣 35 - 𝑣 24 - 𝑣 39 - 𝑣 23 - 𝑣 12 - 𝑣 33 - 𝑣 48 - 𝑣 21 - 𝑣 41 - 𝑣 1 - 𝑣 14 - 𝑣 44 - 𝑣 28 - 𝑣 7 - 𝑣 6 - 𝑣 3 - 𝑣 47 - 𝑣 30 - 𝑣 4 - 𝑣 5 - 𝑣 15 - 𝑣 26 -
Gambar 5 . Model CGVRP Perhitungan Algoritma Dijkstraa
𝑣 27 , 𝑣 18 , 𝑣 13 , 𝑣 17 , 𝑣 11 - 𝑣 53 - 𝑣 2 - 𝑣 50 - 𝑣 54 - 𝑣 40 - 𝑣 49 - 𝑣 42 - 𝑣 16 - 𝑣 0 dengan total jarak sebesar 50200 meter.
Dari  hasil  perhitungan  rute  terpendek  dapat  di ilustrasikan pada gambar 5.
Analisa Perbandingan Rute Terpendek Menggunakan Algoritma Warshall dan

## Algoritma Dijkstraa
Berdasarkan  data  hasil  perhitungan  yang  telah dilakukan  maka  dapat  menganalisis  perbandingan rute  terpendek  menggunakan  Algoritma  Warshall dan Algoritma Dijkstraa dilihat pada tabel 2 sebagai berikut:
Tabel 2. Tabel Perbandingan Algoritma Warshall dan Dijkstraa
No Perhitungan Perbandingan Rute Total Jarak Tempuh (Meter) Total Biaya
(RP)
1  Algoritma Warshall 𝑣 0 - 𝑣 29 - 𝑣 52 - 𝑣 46 - 𝑣 36 - 𝑣 51 - 𝑣 19 - 𝑣 20 - 𝑣 25 - 𝑣 45 - 𝑣 34 - 𝑣 32 - 𝑣 31 - 𝑣 10 - 𝑣 22 - 𝑣 38 - 𝑣 37 - 𝑣 43 - 𝑣 9 - 𝑣 8 - 𝑣 35 - 𝑣 24 - 𝑣 39 - 𝑣 12 - 𝑣 33 - 𝑣 23 - 𝑣 48 - 𝑣 21 - 𝑣 41 - 𝑣 14 - 𝑣 1 - 𝑣 44 - 𝑣 28 - 𝑣 7 - 𝑣 6 - 𝑣 3 - 𝑣 47 - 𝑣 30 - 𝑣 4 - 𝑣 5 - 𝑣 15 - 𝑣 26 - 𝑣 27 , 𝑣 18 , 𝑣 13 , 𝑣 17 , 𝑣 11 - 𝑣 53 - 𝑣 2 - 𝑣 50 - 𝑣 54 - 𝑣 40 - 𝑣 49 - 𝑣 42 - 𝑣 16 - 𝑣 0
49400 39.829-,.
2  Algoritma Djistraa 𝑣 0 - 𝑣 29 - 𝑣 52 - 𝑣 46 - 𝑣 36 - 𝑣 51 - 𝑣 19 - 𝑣 20 - 𝑣 25 - 𝑣 45 - 𝑣 34 - 𝑣 32 - 𝑣 31 - 𝑣 10 - 𝑣 22 - 𝑣 38 - 50200 40.474-,.
No Perhitungan Perbandingan Rute Total Jarak Tempuh (Meter) Total Biaya (RP) 𝑣 37 - 𝑣 43 - 𝑣 9 - 𝑣 8 - 𝑣 35 - 𝑣 24 - 𝑣 39 - 𝑣 23 - 𝑣 12 - 𝑣 33 - 𝑣 48 - 𝑣 21 - 𝑣 41 - 𝑣 1 - 𝑣 14 - 𝑣 44 - 𝑣 28 - 𝑣 7 - 𝑣 6 - 𝑣 3 - 𝑣 47 - 𝑣 30 - 𝑣 4 - 𝑣 5 - 𝑣 15 - 𝑣 26 - 𝑣 27 , 𝑣 18 , 𝑣 13 , 𝑣 17 , 𝑣 11 - 𝑣 53 - 𝑣 2 - 𝑣 50 - 𝑣 54 - 𝑣 40 - 𝑣 49 - 𝑣 42 - 𝑣 16 - 𝑣 0
Dari  Tabel  2  dapat  dianalisa  bahwa
Algoritma Warshall dan Dijkstraa untuk menentukan rute terpendek memiliki cara perhitungan  dan  hasil  yang  hampir  sama  dengan selisih total jarak 800 meter dengan selisih biaya Rp. 645.  dalam  sekali  jalan.  Perbedaan  rute  hanya berada pada kluster 6 dan kluster 9.

## PENUTUP

## Kesimpulan
Berdasarkan penelitian yang telah dilakukan  dapat  diperoleh  kesimpulan  yang didasarkan  atas  rumusan  masalah  dan  tujuan  awal penelitian  yaitu  menganalisis  penentuan  Rute Terpendek  dengan  membandingkan  Algoritma Warshall  dan  Dijkstraa  pada  metode  GVRP. Perhitungan  dengan  menggunakan  Algoritma Warshall  didapatkan  rute  terpendek  dengan  total jarak optimal sebesar 49,4 km sehingga menghabiskan  biaya  bahan  bakar  sebesar  Rp 39.829.  Sedangkan  perhitung  rute  terpendek menggunakan  Algoritma  Dijkstraa  didapatkan  rute terpendek  dengan  total  jarak  optimal  sebesar  50,2 km  yang  memiliki  biaya  sebesar  Rp  40.474.  Jadi Algoritma  Warshall  dan  Algoritma  Dijkstraa memiliki  cara  perhitungan  yang  hampir  sama dengan  total  jarak  dan  biaya  memiliki  selisih  yang relatif kecil.

## REFERENSI
Devo Avidianto P. (2010) Pengertian Distribusi dan
Fungsi Distribusi. [Online].http://www.devoav1997.webnode.c om Faisol,  F  &  Masdukil  Makruf.  2017.”  Distribusi Batik Madura Melalui Penerapan Generalized Vehicle Routing Problem
( GVRP )”. Jurnal Matematika :  Vol  3  No  2, 101-104.
Gautama, I. P. W., & Hermanto, K. (2020). Penentuan Rute Terpendek dengan Menggunakan Algoritma Dijkstra pada Jalur Bus Sekolah. Jurnal Matematika , 10 (2), 116–
123.
https://doi.org/10.24843/JMAT.2020.v10.i02.
p128
Hermanto, K., Adiasa, I., Altarisi, S., Rabani, R., &
Amirul, M. (2020). Rute Usulan
Pendistribusian LPG Menggunakan Model Clustered Generalized Vehicle Routing Problem (CGVRP) dan Algoritma Dijkstra.
Performa: Media Ilmiah Teknik Industri ,
19 (1), 27–36. https://doi.org/10.20961/performa.19.1.41858 Hermanto, K., & Ermayanti, T. D. (2019). Analisa Optimasi Rute Transportasi Antar Jemput
Siswa Menggunakan Model CGVRP dan Algoritma Dijkstra di SDIT Darus Sunnah. Jurnal UJMC , 5 (2), 19–28. http://e- jurnal.unisda.ac.id/index.php/ujmc/article/vie w/1653 Hermanto, K., & Ruskartina, E. (2018a). Optimasi Rute Truk Pengangkut Sampah di Kota Sumbawa Besar Shift II Menggunakan GVRP. Jurnal UJMC , 4 (2), 15–23.
Hermanto, K., & Ruskartina, E. (2018b). Usulan Rute Optimal Distribusi Sampah Shift I Kota Sumbawa Besar Menggunakan Metode GVRP. Eigen Mathematics Journal , 01 (02),
7–12. Hermanto, Koko. 2015.”Model Matematika Generalized  Vehicle  Routing  Problem  Dan
Ekstensinya  Studi  Kasus:  Pendistribusian Kertas  Karton.  Tesis. Universitas  Gajdah Mada.
Indroyono Gitosudarmono, Manajemen Pemasaran. Yogyakarta: BPEE , 2000.
Irwan  Iftadi,  Wakhid  Ahmad  Jauhari,  dan  Beny Nugroho.  “Peranca ngan  Peta  Evakuasi Menggunakan  Algoritma  Floyd-Warshall untuk  Penentuan  Lintasan  Terp endek:  Studi Kasus”.Makalah.2011.
Jayanti, Ni Ketut Dewi Ari. 2014.” Penggunaan Algoritma Floyd Warshall Dalam Masalah Jalur Terpendek Pada Penentuan Tata Letak Parkir”.STIMIK STIKOM Bali. Bali.
Maulidya, R dan Kusuma ningrum.
2013.”Perbaikan Sistem Distribusi dan
Tranportasi dengan menggunakan distribution requitment planning (DRP) dan Algoritma Djikstra” . Studi kasus : Depot Pertamina Tasikmalaya. Ju rnal Teknik industry ,pp ISSN.
Hamin, Ismaillia Nur. (2017).Identifikasi Alternatif Pengadaan Bahan Baku di PDAM
Kabupaten Boyolali. [Online]. http://www.etd.eprints.ums.ac.id /
1743
Saputra, Ragil. 2011.” Sistem Informasi Geografis
Pencarian Rute Optimum Obyek Wisata
Kota Yogyakarta Dengan Algoritma Floyd-
Warshall”.Matematika, Vol 14. No 1: Jurnal Matematika.
Sari, Pipit.2017 .” Metode Vehicle Routing Problem
(Vrp) Dalam Mengoptimalisasikan Rute
Distribusi Air Minum PT.Smu ”. Jurnal
SemNas :147-153.
Siang,Jong Jek.2014.”Riset Operasi dalam pendekatan  Algoritmis”.  Yogyakarta:  Andi
Offset. Tramizi.  2005."Optimasi  usaha  Tani  dalam
Pemanfaatan  Air  Irigasi  Embung  Leubuk Aceh
besar," Jurnal Teknik Pertanian .