## Rute Usulan Pendistribusian LPG Menggunakan Model Clustered
Generalized Vehicle Routing Problem (CGVRP)
dan Algoritma Dijkstra
Koko Hermanto  1 , Iksan Adiasa 2 Salman Altarisi 3 , Ridho Rabani 4 dan Muhammad Amirul 5 1,2,3,4,5 Jurusan Teknik Industri, Fakultas Teknik, Universitas Teknologi Sumbawa, Jl. Raya Olat Maras ds. Batu Alang Kec. Moyo Hulu Kab. Sumbawa NTB, 84371, Indonesia Email: koko.hermanto@uts.ac.id 1 , iksan.adiasa@uts.ac.id 1 , altarisisalman@gmail.com 3 , qidoy46@gmail.com 4 , muhamadamirul815@gmail.com 5
DOI: 10.20961/performa.19.1.41858

## Abstrak
Salah satu aspek penting dalam menjalankan aktifitas dan memengaruhi keberhasilan sistem perindustrian adalah model transportasi dan distribusi yang diterapkan oleh industri tersebut. Didukung dengan meluasnya permintaan konsumen atas produk yang dihasilkan ke berbagai pelosok daerah, menjadikan masalah transportasi dan distribusi menjadi poin utama  dalam  pengembangan  perusahaan.  Untuk  mengetahui  penerapan  model  transportasi  distribusi  yang  dapat diusulkan  terhadap  rute  transportasi  distribusi  Liquid  Petroleum  Gas  (LPG)  pada  PT.  Javarko  yang  berdiri  di  kota Sumbawa  Besar,  maka  dapat  diusulkan  dengan  menggunkan  model  Clustered  Generalized  Vehicle  Routing  Problem (CGVRP)  dan  algoritma  Dijkstra.  Dimana  pada  model  CGVRP  toko-toko  (vertek)  tujuan  dikelompokan  berdasarkan kelurahan dan kapasitas armada kendaraan. Sehingga  diperoleh total jarak untuk kendaraan pertama adalah sebesar 14.410 km dengan rute distribusi gudang (0)→ UD. Fatimah (10) → Primart (5) → UD. Dua Putra (6) → UD.Hana (2) → UD. Bayu Rejeki (9) →  UD.Irma (1) → UD. Mandiri (7). Sedangkan jarak yang diperoleh untuk kendaraan kedua adalah sebesar 11.120 k m dengan rute pendistribusian . gudang (0) → UD. Dua satu (13) → UD. → Berlian Indah (12) → UD. Citra (11) → UD. Gonofit (3) → UD. Adiit Daputra (15) → UD. Yeyen Lengas (14) → gudang (0).

## Kata kunci: Rute terpendek, Distribusi LPG, CGVRP, Algoritma Dijkstra

## Abstract
The  most  important  aspect  of  carrying  out  activities  and  influencing  the  success  of  the  industrial  system  is  the transportation and distribution model adopted by the industry. Supported by widespread consumer demand for products produced  to  various  regions  of  the  region,  making  transportation  and  distribution  problems  a  major  point  in  the development of the company. To find out the application of the distribution transportation model that can be proposed for the transportation route of the Liquid Petroleum Gas (LPG) distribution at PT. Javarko, which stands in the city of Sumbawa Besar, can be proposed using the Clustered Generalized Vehicle Routing  Problem (CGVRP) model and the Dijkstra algorithm. Where in the CGVRP model the shops (vertices) of destination are grouped based on the urban vilage and vehicle fleet capacity. So that the total distance obtained for the first vehicle is 14.410 km with warehouse distribution routes (0) → UD. Fatimah (10), → Primart (5), → UD. Dua Putra (6), → UD. Hana (2), → UD. Bayu Rejeki (9), → UD. Irma (1), → UD. Mandiri (7). While the distance obtained for the second vehicle is 11.120 km by the distribution route. warehouse (0) → UD. Two one (13) → UD. → Berlian Indah (12) → UD. Citra (11) → UD. Gonophytes (3) → UD. Adiit Daputra (15) → UD. Yeyen Lengas (14) → warehouse (0).
Keywords: shortest route, LPG Distribution, CGVRP, Dijkstra's Algorithm

## 1. Pendahuluan
Berdasarkan kebijakan PT. Pertamina (persero) kabupaten Sumbawa yang telah dikeluarkan sejak awal tahun  2007  lalu,  bahwa  akan  dilakukan  penarikan  minyak  tanah  di  pulau  Sumbawa,  guna  mengurangi ketergantungan masyarakat terhadap minyak tanah. Apabila harga minyak tanah dalam negeri dipertahankan, maka pemerintah harus mengeluarkan dana APBN yang sangat besar untuk memberikan subsidi. Sementara itu,  cadangan  minyak  bumi  Indonesia  sudah  semakin  menipis.  Beberapa  manfaat  yang  diperoleh  dengan menjalankan program konversi minyak tanah ke LPG ( Liquid Petroleum Gas ) adalah berdasarkan kesetaraan nilai kalori, subsidi LPG lebih rendah dari pada subsidi minyak tanah, penghematan subsidi dapat mencapai 15-20  triliyun  rupiah.  Program  konversi  minyak  tanah  ke LPG merupakan  program  prioritas  nasional  dan merupakan  pelaksanaan  dari  Peraturan  Presiden  RI  Nomor  104  Tahun  2007.  Untuk  Kabupaten  Sumbawa
sudah dilakukan pendistribusian paket tabung LPG dan perlengkapannya, untuk rumah tangga dan usaha mikro sejak bulan November 2018, sebanyak 83.204 paket (Sumbawa 2019).
PT.  Javarko  merupakan  sebuah  perusahaan  yang  bergerak  dalam  bidang  distribusi  tabung LPG . Perusahaan  ini  didirikan  sejak  tahun  2008    terletak  dikabupaten  Sumbawa,  Nusa  Tenggara  Barat.  Jalur distribusi PT. Javarko saat ini telah meluas hingga tersebar ke berbagai desa terutama di kabupaten Sumbawa. Selama ini proses pendistribusian tabung LPG yang dilakukan  dengan mengandalkan pengalaman sopir dalam menentukan toko-toko tujuan yang akan dikunjungi dan pihak sopir belum melakukan  analisa secara heuristik dalam  menentukan  rute  optimal  pendistribusian,  sehingga  belum  diketahui  apakah  rute  yang  selama  ini digunakan sudah optimal atau tidak, dimana dapat berpengaruh secara langsung dalam  mengoptimalkan biaya dan waktu pendistribusian. Oleh karena itu perlu dilakukan analisa terhadap rute pendistribusian yang selama ini dilakukan agar tetap bersaing dalam mendistribusikan tabung LPG dengan tepat sasaran dan waktu yang optimal  serta  dengan  harga  yang  lebih  terjangkau,  salah  satu  strategi  dalam  mewujudkannya  ialah  dengan menekan biaya yang ada.
Salah  satu  biaya  yang  paling  sering  dikeluarkan  adalah  biaya  pendistribusian  dan  transportasi. Transportasi dapat didefinisikan sebagai perpindahan barang komoditas atau produk dari stau tempat ketempat yang lain, atau dari tempat asal (gudang) ke tempat tujuan (konsumen). Oleh sebab itu, dalam kajian ini penulis akan membahas tentang bagaimana cara pendistribusian barang atau jasa dengan tujuan meminimalkan jarak transportasi. Permasalahan transportasi membahas persoalan pendistribusian suatu komoditas atau produk dari beberapa sumber ke beberapa tujuan, dimana tujuannya mengoptimalkan biaya pendistribusian yang terjadi. Manajemen  transportasi  dan  distribusi  meliputi  aktivitas  fisik  seperti  menyimpan  dan    mengirim  produk, maupun aktivitas non fisik misalnya aktivitas pengolahan informasi kepada konsumen. Fungsi distribusi dan transportasi  pada  dasarnya  adalah  mendistribusikan  produk  dari  lokasi  produk  tersebut  diproduksi  atau disimpan (gudang) sampai sampai konsumen (Queeny 2015).
Dalam  mendistribusikan  produk  keberbagai  desa    ataupun  kota  salah  satu  aktivitas  operasional  dari perusahaan  tentunya  memerlukan  biaya  transportasi  yang  tidak  sedikit  jumlahnya.  Tidak  jarang  ditemukan konsumen yang mengeluh  akan tingginya harga produk yang ditetapkan produsen untuk dipasarkan. Hal itu disebabkan penambahan berupa biaya-biaya pada harga produk tersebut. Salah satunya ialah biaya operasional yang dihasilkan dari aktivitas transfortasi dan distribusi produk. Tingginya harga produk yang ditetapkan hal ini umunya disebabkan oleh biaya produk yang dihasilkan agar produsen tidak jatuh dibawah break even point . Tingginya harga produk menjadi penyebab konsumen kita tidak loyal dan memilih untuk mencari produsen lain atau mencari barang-barang substitusi. Ditambah dengan banyaknya pesaing untuk produk sejenis.  Oleh karena itu diperlukan perencanaan yang matang agar biaya tersebut dapat dibuat  seefisien mungkin sehingga menjadi suatu keunggulan kompetitif.
Model  pendistribusian  yang  dilakukan  beberapa  kendaraan  berangkat  dari  satu  gudang  menuju  ke kesemua konsumen yang ada dan kembali lagi ke gudang disebut dengan pemodelan vehicle routhing problem ( VRP )  (Lin  and  Jia-zhen  2009).  Sedangkan  pendistribusian  yang  ditugaskan  untuk  satu  kendaraan  disebut dengan trapeling  salesment  problema ( TSP )  (Gupta  and  Panwar 2013).  Perkembangan   model VRP adalah general vehicle routhing problem ( GVRP ) yaitu model pendistribusiannya sama dengan model VRP , hanya saja vertek tujuan pendistribusian dikluster/dikelompokan berdasarkan definisi yang telah ditentukan. Adapun varians dari metode GVRP adalah cluster general vehicle routhing problem ( CGVRP ) (Pop, Kara, and Marc 2012).
Selama  ini  proses  pendistribusian  gas LPG yang  dilakukan  oleh  PT.  Javarko  masih  mengandalkan pengalaman  sopir  truk  dalam  menentukan  atau  memutuskan  rute  pendistribusiannya.  Pada  penelitian  ini, peneliti  mengusulkan  menggunakan  metode heuristic ,  dimana    masalah  transportasi  dimodelkan  ke  model Clustered  Generalized  Vehicle  Routing  Problem ( CGVRP )    Dalam  hal  ini  metode  yang  akan  diuji  untuk mengefisienkan  jarak  pendistribusian  tabung LPG pada  PT.  Javarko  antara  lain  menggunakan  metode Dijkstra.  Adapun  penelitian-penelitian  sebelumnya  pada  persoalan  pendistribusian  dengan  menggunakan model CGVRP telah  dilakukan  oleh    Hermanto  &  Ruskartina  (2018)  yaitu  menentukan  rute  terpendek pendistribusian  samapah,  Hermanto  &  Ermayanti  (2019)  yaitu  menentukan  rute  terpendek  pendistribusian antar  jemput  siswa  sekolah  dan  penelitian  yang  dilakukan  oleh  Hermanto  (2015)  yaitu  menentukan  rute terpendek  pendistribusian  kertas  hanya  saja  pada  penelitian  ini  mengkolaborasikan  model CVGRP dengan metode  progra  linier integer 0-1.  Selain  untuk  menentuka  rute  terpendek,  program  linier integer 0-1  juga digunakan  untuk  menyusun  jadwal  seperti  yang  dilakukan  oleh  Hermanto  (2020)  dalam  menyusun  jadwal satpol  PP.  Selain  itu,  beberapa  penelitian  tentang  pendistribusian LPG pernah  dilakukan  oleh  Meilani  and
Iswara  (2018),  penentuan  rute  terpendek  dengan  menggunakan  model VRP dengan  algoritma  Clarke  dan Wright Savings Matrix. Rofiq et al. (2016) pernah menentukan rute terpendek pendistribusian LPG dengan menngunakan  program  linier integer .  Sutoni  and  Asilah  (2018)  juga  pernah  melakukan  penelitian  tentang penentuan rute terpendek pendistribusian LPG dengan menggunakan model TSP dengan algoritma heuristic . Menyadari akan pentingnya pendistribusian yang tepat dengan biaya yang minimal, maka peneliti ingin mengkaji  pendistribusian  pada  PT.  Javarko  dalam  mencari  solusi  agar  distribusi  produk  merata  dan  tepat dengan tetap memperhatikan kapasitas kendaraan dan jumlah permintaan setiap toko. peneliti menggunakan model  transportasi  untuk  mengolah  data  mencari  biaya  pendistribusian  produk  dengan  pemilihan  pola  rute distribusi yang tepat pada pendistribusian yang optimal.

## 2. Metode Penelitian

## 2.1 Model distribusi
Pada penelitian ini permasalahan pendistribusian di modelkan ke model General vehicle routing problem yang dinotasikan dengan GVRP . Model GVRP merupakan perkembangan dari model vehicle routing problem ( VRP ). Model GVRP dapat didefiniskan sebagai salah satu model pendistribusian yang didefinisikan sebagai masalah mencari rute terpendek yang direpresentasikan dengan sebuah graph berarah 𝐺 = ( 𝑉 , 𝐴 ) dengan V= {0, 1, 2, … , 𝑛 } sebagai himpunan vertek dan 𝐴 = {( 𝑖 , 𝑗 )| 𝑖 , 𝑗 ∈ 𝑉 , 𝑖 ≠ 𝑗 } himpunan edge 𝐶𝑖𝑗 bernilai nonnegative untuk setiap edge ( 𝑖 , 𝑗 ) ∈ 𝐴 ,  himpunan vertek dibagi menjadi 𝑘 + 1 himpunan bagian tak kosong saling bebas, yang disebut dengan kluster 𝑉 0 , 𝑉 1 , …., 𝑉 𝑘 (i.e. 𝑉 = 𝑉 0 ∪ 𝑉 1 ∪ …. 𝑉 𝑘 dan 𝑉 𝑙 ∩ 𝑉 𝑙 = ∅ untuk semua  , 𝑝 ∈ {0, 1, … , 𝑘 }  dan 𝑙 ≠ 𝑝 ).  Varian  dari GVRP didefinisikan  sebagai  masalah  umum  kluster  rute  kendaraan  atau clustered generalized vehicle routing problem yang dinotasikan sebagai CGVRP , dimana semua vertek  setiap kluster harus dikunjungi secara berurutan dalam rute kendaraan. Dengan demikian tujuan CGVRP adalah untuk menentukan koleksi biaya minimum dari 𝑚 tur kendaraan yang berawal dan berakhir di depot sehingga vertek dari tiap graph dikunjungi tepat satu kali dengan melakukan lintasan Halmiton pada tiap vertek, serta muatan masing-masing  kendaraan  tidak  melebihi  kapasitas 𝑄 .  Ilustrasi CGVRP dan  solusi  layak  yang  merupakan lanjutan dari masalah GVRP (Pop, Kara, and Marc 2012).
Gambar 1. Contoh Solusi Layak CGVRP
Gambar 1 menjelaskan salah satu contoh solusi layak CGVRP dari suatu masalah pendistribusian barang yang dilakukan oleh dua armada kendaraan distribusi yang identik dengan kapasitas masing-masing kendaraan Q =  25  unit.  Kendaraan  pertama  pendistribusiannya  dimulai  dari  gudang  (0)  menuju  vertek  3  dimana permintannya 4 unit kemudian ke vertek 2 dengan permintaan 5 unit, selanjutnya menuju ke vertek 1 dimana permintaannya 3 unit, merupakan vertek-vertek yang ada di kluster 1 dengan total jumlah permintaan 12 unit. Selanjutnya  kendaraan  pertama  menuju  vertek  4  dimana  jumlah  permintaannya  5  unit  selanjutnya  menuju
vertek  5  dengan  jumlah  permintaan  5  unit,  adalah  vertek-vertek  yang  berada  di  kluster  2  dengan  jumlah permintaan  9  unit,  selanjutnya  kendaraan  pertama  tersebut  kembali  lagi  ke  gudang.  Sama  halnya  dengan kendaraan kedua yang ditugaskan di kluster 5, kluster 4 dan kluster 3.

## 2.2 Algoritma Dijkstra
Prinsip algoritma Dijkstra dalam menentukan rute terpendek dari suatu persoalan pendistribusian yang telah implementasikan ke graph adalah pada waktu penentuan rute yang akan dipilih, akan dianalisis setiap bobot (pada penelitian ini, bobot didefiniskan sebagai jarak) dari vertek yang belum dipilih, lalu dipilih vertek dengan bobot yang paling kecil. Apabila ada bobot yang lebih kecil melalui vertek tertentu, maka bobot akan dapat berubah, artinya rute lintasan akan berubah. Algoritma Dijkstra akan berhenti ketika semua simpul sudah terlewati.
Dimisalkan: 𝑉(𝐺) = {𝑣 1 , 𝑣 2 , … , 𝑣 𝑛 } ; 𝐿 =Himpunan vertek-vertek ∈ 𝑉(𝐺) yang telah terpilih dalam jalur rute terpendek; 𝐷(𝑗) =jumlah bobot rute terpilih terkecil dari 𝑣 1 ke 𝑣 𝑗 ; 𝑤 (𝑖,𝑗) =bobot edge dari vertek 𝑣 1 ke 𝑣 𝑗 ; 𝑤 ∗ (1, 𝑗) =Jumlah bobot rute terkecil dari 𝑣 1 ke 𝑣 𝑗 . Maka algoritma Dijkstraa menentukan rute terpendek adalah sebagai berikut (Siang 2014):
1. Inisialisasi: 𝐿 = { }; 𝑉 = {𝑣 1 , 𝑣 2 , … , 𝑣 𝑛 } . 2. Untuk 𝑖 = 2, 3, … , 𝑛 , lakukan 𝐷(𝑖) =  𝑊(1, 𝑗) . 3. Selama 𝑣 𝑛 ∉ 𝐿 (𝑣 𝑛 belum merupakan titik permanen), lakukan: a. Pilih 𝑣 𝑛 ∈ 𝑉 − 𝐿 vertek bukan permanen) dengan 𝐷(𝑘) terkecil. 𝐿 = 𝐿 ∪ {𝑣 𝑘 } (jadikan 𝑣 𝑘 menjadi titik permanen)
b. Untuk  setiap 𝑣 𝑗 ∈ 𝑉 − 𝐿 lakukan:  jika 𝐷(𝑘) + 𝑊(𝑘, 𝑗) < 𝐷(𝑗) maka  ganti 𝐷(𝑗) dengan 𝐷(𝑘) + 𝑊(𝑘, 𝑗)

## 2.3 Langkah-langkah Penelitian
Adapun langkah-langkah pada penelitian ini guna memberikan rute usulan pendistribusian tabung L PG ukuran 3 kg oleh PT. Javarko adalah sebagai berikut:
1. Menentukan lokasi penelitian
Ditetapkan proses pendistribusian tabung LPG ukuran 3 kg dilakukan di kota Sumbawa Besar, Kabupaten Sumbawa, Provinsi Nusa Tenggara Barat.
2. Menentukan sampel data
Sampel data yang diperlukan adalah jumlah, kapasitas dan jenis armada, jumlah permintaan tabung LPG ukuran  3  kg  setiap  toko-toko  distributor,  lokasi  toko-toko  distributor,  serta  jarak  antar  toko-toko distributor dan jarak dari gudang ke setiap toko-toko distributor tersebut.

## 3. Penyusunan model CGVRP
Pembentukan  kluster pada penyususnan model CGVRP pada  penelitian  ini  berdasarkan  kelurahan dan kapasita setiap armada.
4. Penyelesaian model
Model  pendistribusian  yang  telah  disusun  ke  model CGVRP tersebut  selanjutnya  ditentukan  rute pendistribusian yang optimal dengan menggunakan algoritma Dijkstra

## 3. Hasil dan Pembahasan
Pendistribusian tabung LPG ukuran 3 kg oleh PT. Javarko dilakukan setiap hari yang didistribusikan ke 15 toko di kecamatan Sumbawa dengan menggunkan 2 armada truk yang masing- masing memiliki kapasitas sebesar 560 tabung LPG ukuran 3 kg atau setara dengan kapasitas 5 ton muatan. Data 15 toko tujuan tersebut beserta    jumlah  rata-rata  permintaan    tabung LPG ukuan  3  kg  dan  alamat  toko  tujuan  pendistribusian PT.Javarko disajikan dalam tabel 1.
Adapun sebaran vertek gudang dan toko-toko tujuan pendistribusian tabung LPG ukuran 3 kg oleh PT. Javarko  di  kecamatan  Sumbawa  dapat  dilihat  pada  gambar  3.  Selanjutnya  setiap  vertek-vertek  tersebut ditentukan  edge  penghubung  antar  vertek  mengikuti  jalur  distribusi  yang  tersedia,  sehingga  dengan menggunakan google map dapat ditentukan jarak setiap vertek seperti disajikan pada gambar 2.
Tabel 1. List Toko Tujuan Distribusi Nama toko Kode Toko Jumlah Permintaan (Tabung) Alamat Gudang PT. Javarko 0 0 Jln. Cendrawasih No. 148, brang biji, Kec. Sumbawa, UD.Irma 1 25 Seketeng Kec. Sumbawa, Kab. Sumbawa, NTB, 84313 UD.Hana 2 12 Jln. Gurami, RT.02/RW.03, seketeng, Kec. Sumbawa UD.Gonofit 3 9 Jln. Tongkol, Uma Sima, Kec. Sumbawa, NTB, 84313 Toko Cendana 4 20 Jln. Kaharuddin No.9 Sumbawa Besar Primart 5 10 Jln. Sudirman No.43 Rt 4 Rw 1 UD. Dua Putra 6 150 Jln. Sudirman Rt.1 Rw.2 UD. Mandiri 7 10 Jln. Prate, RT.02/RW.03, Samapuin, Seketeng, UD. Panji 8 100 Jln. Puncak Ngegas Rt 3 Rw 7 Kelurahan Pekat UD. Bayu Rejeki 9 100 Jln. Dalam Loka Rt. 1 Rw 1Kelurahan Seketeng UD. Fatimah 10 25 Jln. Dr Wahidinn Rt 1 Rw 1 N0. 47 Seketeng UD.Citra 11 20 Jln. Manggis No 11 Uma Sima Sumbawa UD.Berlian Indah 12 300 Jln. Manggis No. 22 Rt 1 Rw 5 Kelurahan Brang Biji UD. Dua Satu 13 35 Jln. Cendrawasih No.28 b UD. Yeyen Lengas 14 30 Jln. Lintas Sebewe, Moyo Utara UD. Adiit Daputra 15 50 Jln. Lintas Pungkit, Moyo Utara
Gambar 2. Sebaran Lokasi Toko-toko Tujuan Pendistribusian LPG oleh PT. Javarko
Selanjutnya setiap toko dikelompokan atau di kluster berdasarkan kelurahan masing-masing dengan tetap memperhatikaan kapasitas truk yaitu total jumlah permintaan tidak melebihi kapasitas truk yaitu 560 tabung LPG ukuran 3 kg. Apabila jumlah permintaan melebihi kapasitas truk maka harus dibentuk kelompok baru. Sedangkan penelitian yang pernah dilakukan oleh Osaba (2020), kluster didefinisikan sebagai provinsi. Jumlah permintaan  tabung LPG ukuran  3  kg  setiap  toko  ( 𝑑 𝑖 ),  Jumlah  permintaan  tabung LPG ukuran  3  kg  setiap kluster ( 𝑞 𝑖 ), penglusteran setiap toko tujuan dan penugasan armada pendistribusian disajikan pada tabel 2.
Tabel 2. Jumlah Permintaan, Pengelompokan Toko dan Tugas Armada
Kelurahan (kode) Toko (kode) Permintaan per toko (Tabung) Jumlah Permintaan perlurah (Tabung) Tugas Armada Seketeng ( 𝑉 1 ) UD. Irma (1) 25 332
Truk 1
UD. Hana (2)
12 Primartm (5) 10 UD. Dua Putra (6) 150 UD. Mandiri (7) 10 UD. Bayu Rejeki (9) 100 UD. Fatimah (10) 25 Kerato ( 𝑉 3 ) Toko Cendana (4) 20 20 Pekat ( 𝑉 4 ) UD. Panji (8) 100 100 Uma sima ( 𝑉 2 ) UD. Gonofit (3)
9
29 Truk 2 UD. Citra (11) 20 Brang Biji ( 𝑉 5 ) UD. Berlian Indah (12) 300 335 UD. Dua satu (13) 35 Moyo ( 𝑉 6 ) UD. Yeyen Lengas (14) 30 80 UD. Adiit Daputra (15) 50
Berdasarkan pengklusteran yang telah ditetapkan dan jumlah permintaan setiap toko yang disajikan pada tabel 2, dan vertek gudang dan vertek toko-toko tujuan yang telah ditandai seperti pada gambar 1 di atas, maka berdasakan definisi graph isomorfik (Ilhamsyah, 2017) maka dapat disusun kombinasi solusi rute terpendek pendistribusian tabung LPG ukuran 3  kg  di  kecamatan  Sumbawa  yang dilakukan  oleh  PT. Javarko  dengan menggunakan model CGVRP. Model CGVRP tersebut dapat dilihat pada gambar 4 sebagai berikut.
Gambar 3. Rute-rute Distribusi Gas LPG 3 kg dengan Model CGVRP
Berdasarkan jalur rute distribusi yang tersedia pada gambar 4, maka dengan menggunakan google map dapat ditentukan jarak gudang kesetiap toko, jarak masing-masing toko dalam kluster dan jarak antar vertek antar kluster yang ditugaskan pada masing-masing truk dengan satuan kilo meter (km), jarak-jarak tersebut disajikan pada tabel 3.
Tabel 3. Jarak gudang ke toko dan jarak antar konsumen (km)
Kode Toko 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 1 4600 0
2 3800 900 0
3 3100 - - 0
4 3700 2800 2200 - 0 5
3900 1000 350 - 1700 0
6 4600 750 160 - 2100 270 0 7 4900 2000 1300 - 2700 1400 1200 0 8 3900 1300 600 - 1700 240 500 1200 0 9 4000 1200 500 - 1800 160 450 1100 120 0
10 180 4400 3600 - 3500 3500 3600 4500 3700 3600 0 11 3200 - - 2100 - - - - - - - 0 12 1600 - - 1600 - - - - - - - 1700 0 13 220 - - 2900 - - - - - - - 3000 1400 0 14 13000 - - 11000 - - - - - - - 12000 13000 14000 0 15 10000 - - 7200 - - - - - - - 7500 8300 8600 4400 0
Terlihat  pada  tabel  3  terdapat  beberapa  vertek  tidak  ditentukan  jarak  penghubungnya,  salah  satu contohnya toko 1 dan toko 3. Hal ini dikarenakan kedua toko tersebut dikunjungi oleh truk yang berbeda, dapat dilihat pada gambar 4. Tahapan selanjutnya adalah menentukan rute usulan pendistribusian tabung LPG ukuran 3 kg di PT. Javarko dengan menggunakan algoritma Dijkstra berdasarkan model distribusi CGVRP yang telah
disusun  pada  gambar  1.  Proses  pendistribusian  dilakukan  oleh  dua  armada  kendaraan/truk,  dimana  truk pertama peneliti menugaskan untuk mendistribusi ke toto-toko di kelurahan Seketeng ( 𝑉 1 ), Kerato ( 𝑉 3 ), Pekat ( 𝑉 4 ), sedangkan truk kedua ditugaskan ke toko-toko di kelurahan Uma sima ( 𝑉 2 ), Brang Biji ( 𝑉 5 ), Moyo ( 𝑉 6 ). Pada artikel ini akan dijelaskan pengaplikasian algoritma Dijkstra pada pendistribusian yang dilakukan oleh truk  pertama,  dimana  jarak  terpendek  setelah  gudang  adalah  UD.  Fatimah  (10)  yang  berada  pada    kluster Seketeng ( 𝑉 1 ) maka dilakukan analisa perhitungan Algoritma Dijkstra pada truk Pertama pada kluster Seketeng ( 𝑉 1 ) terlebih dahulu. Analisa perhitungan tersebut dapat dilihat pada tabel 4 sebagai berikut.
Tabel 4. Penerapan Algoritma Dijkstra pada Pendistribusian Truk pertama Iteras i D(0) D(1) D(2) D(5) D(6) D(7) D(9) D(10) L 1 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ {0} 2 - Min {∞, 0+4.600=4. 600} Min {∞, 0+3.800} = 3.800 Min {∞, 0+3.900}= 3.900 Min {∞, 0+4.600} = 4.600 Min {∞, 0+4.900} = 4.900 Min {∞, 0+3.900} = 3.900 Min {∞, 0+180} = 180 {0,10} 3 - Min {4.600, 180+4.400 }=4.580 Min {3.800, 180+3.600 }=3.780 Min {3.900, 180+3.500 }=3.680 Min {4.600, 180+3.600 }=3.780 Min {4.900, 180+4.50 0}=4.680 Min {3.900, 180+3.600 }=3.780 - {0, 10, 5} 4 - Min {4.580, 3.680+1.00 0}=4.580 Min {3.780, 3.680+350 }=3.780 - Min {3.780, 3.680+270 }=3.780 Min {4.680, 3.680+1.4 00}=4.68 0 Min {3.780, 3.680+160 }=3.780 - {0, 10, 5,6} 5 - Min {4.580, 3.780+750 }=4.530 Min {3.780, 3.780+750 }=3.780 - - Min {4.680, 3.780+14 00}=4.68 0 Min {3.780, 3.780+450 }=3.780 - {0, 10, 5,6,2} 6 - Min {4.530, 3.780+900 }=4.530 - - - Min {4.680, 3.780+1.3 00}=4.68 0 Min {3.780, 3.780+500 }=3.780 - {0, 10, 5,6,2,9 } 7 - Min {4.530, 3.780+1.20 0}=4.530 - - - Min {4.680, 3.780+1.1 00}=4.68 0 - - {0, 10, 5,6,2,9 ,1} 8 - - - - - Min {4.680, 4.530+2.0 00}=4.68 0 - - {0, 10, 5,6,2,9 ,1,7}
Berdasarkan tabel 4, diperoleh rute pendistribusian pada truk pertama pada kluster Sketeng ( 𝑉 1 ) adalah vertek 0 → vertek 10 → vertek 5 → vertek 6 → vertek 2 → vertek 9 → vertek 1 → vertek 7. Pada kluster 1 diperoleh vertek terakhir yang dikunjungi adalah vertek 7, maka akan ditentukan apakah jarak terpendek mengunjungi vertek 8 di kluster 4 atau vertek 4 di kluster 4 di kluster 3. Berdasarkan tabel 3 jarak terpendek setelah vertek 7 adalah vertek 8 di kluster 4, selanjutnya mengunjugi vertek 4 di kluster 3 dan terakhir truk kembali ke gudang. Dengan cara yang sama diterapkan pada kendaraan kedua diperoleh rute truk kedua adalah vertek 0 → vertek 13 → vertek 12 → vertek 11 → vertek 3 → vertek 15 → vertek 14 → vertek 0. Perhitungan jarak tempuh dengan menggunakan model CGVRP dan algoritma Dijksta pada permasalahan pendistribusian LPG 3 ukuran kg PT. Javarko dapat dilihat pada tabel 5 sebagai berikut.
Tabel 5. Perhitungan Jarak Rute Usulan
No. Armanda Kendaraan Rute Jarak Tempuh (km) 1. Truk pertama gudang (0)→ UD. Fatimah (10) → Primart (5) → UD. Dua Putra (6) → UD.Hana (2) → UD. Bayu Rejeki (9) →  UD.Irma (1) → UD. Mandiri (7) → UD. Panji (8) → (4) Toko Cendana (4) → gudang (0) 180 + 3500 + 270 + 160 + 500 + 1200 + 2000 + 1200 + 1700 + 3700 = 14410 2. Truk kedua gudang (0) → UD. Dua satu (13) → UD.  Berlian Indah (12) → UD. Citra (11) → UD. Gonofit (3) → UD. Adiit Daputra (15) → UD. Yeyen Lengas (14) → gudang (0) 220 + 1400 +1700 + 2100 + 4400 + 1300 = 11.120 Total 25.530
Sehingga dapat dimodelkan solusi layak pendistribusian gas LPG 3 kg oleh PT Javarko di kecamatan Sumbawa ke model CGVRP seperti pada gambar 4 berikut.
Gambar 4. Solusi layak model CGVRP pendistribusian LPG PT. Javarko

## 4. Simpulan
Penerapan  model CGVRP dan algoritma  Dijkstra  untuk  menentukan  rute  terpendek  usulan  pada pendistribusian LPG ukuran  3  kg  pada  PT.  Javarko,  diperoleh  total  jarak  untuk  kendaraan  pertama  adalah sebesar 23.640 km dengan rute distribusi gudang (0)→ UD. Fatimah (10) → Primart (5) → UD. Dua Putra (6) → UD.Hana (2) → UD. Bayu Rejeki (9) →  UD.Irma (1) → UD. Mandiri (7) → UD. Panji (8) → (4) Toko Cendana (4) → gudang (0). Sedangkan jarak yang diperoleh untuk kendaraan kedua adalah sebesar 14410 km dengan rute pendistribusian. gudang (0) → UD. Dua satu (13) → UD.  Berlian Indah (12) → UD. Citra (11) → UD. Gonofit (3) → UD. Adiit Daputra (15) → UD. Yeyen Lengas (14) → gudang (0). Dimana total jarak pendistribusian dari kedua kendaraan adalah 25.530 km.

## Ucapan Terima Kasih
Peneliti  mengucapkan  terima  kasih  kepada  tim reviewer jurnal  Performa,  dan  kepada  pimpinan  PT. Javarko kota Sumbawa Besar yang telah memberikan informasi mengenai data-data yang diperlukan dalam penyusunan penelitian ini.

## Daftar Pustaka
Gupta, Saloni, and Poonam Panwar. 2013. “Solving Travelling Salesman Problem Using Genetic Algorithm.” International Journal of Advanced Research in Computer Science and Software Engineering 3(6): 143–47.
Hermanto, Koko. 2015. “Model Matematika Generalize Vehicle Routing Problem Dan Eksistensinya Studi Kasus: PT. Papertech Indonesia Unit II Magelang.” Universitas Gadjah Mada. http://etd.repository.ugm.ac.id/home/detail_pencarian/83358.
Hermanto, Koko, and Tita Dwi Ermayanti. 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/view/1653.
Hermanto, Koko, and Eki Ruskartina. 2018. “Optimasi Rute Truk Pengangkut Sampah Di Kota Sumbawa Besar Shift II Menggunakan GVRP.” Jurnal UJMC 4(2): 15–23.
Hermanto, Koko, Ryan Suarantalla, and Sahdan. 2020. “Aplikasi Program Linier Integer 0-1 Untuk Menyususn Jadwal Usulan Piket Satpol PP.” Barekeng 14(1): 91–99.
https://ojs3.unpatti.ac.id/index.php/barekeng/article/view/1338/1435. Ilhamsyah. 2017. “MATH Unesa.” Analisis Sistem Antrian Pada Loading Dock Bongkar Barang DI PT KAMADJAJA LOGISTICS GUDANG K-66 CONTRACT LOGISTIC NESTLE 2(6): 20–26. Lin, Li, and Huo Jia-zhen. 2009. “Multi-Objective Flexible Job-Shop Scheduling Problem in Steel Tubes Production.” Systems Engineering - Theory & Practice 29(8): 117–26.
http://dx.doi.org/10.1016/S1874-8651(10)60063-4. Meilani, Difana, and Arefa Iswara. 2018. “Aplikasi Penentuan Rute Distribusi LPG 3 Kg.” Jurnal Optimasi Sistem Industri 17(2): 208.
Osaba, Eneko. 2020. “Benchmark Dataset for the Asymmetric and Clustered Vehicle Routing Problem with Simultaneous Pickup and Deliveries, Variable Costs and Forbidden Paths.” Data in Brief 29(105142): 1–6. https://doi.org/10.1016/j.dib.2020.105142.
Pop, Petricâ C., Imdat Kara, and Andrei Horvat Marc. 2012. “New Mathematical Models of the Generalized Vehicle Routing Problem and Extensions.” Applied Mathematical Modelling 36(1): 97–107. Queeny, Fheby. 2015. “Penerapan Model Transportasi Dan Distribusi Vogel’s Approximation Method (Vam) Dan Modified Distribution (Modi) Pada Pt. Hastura Nazwa Utama Di Bantaeng.” Universitas Hasanudin Makasar.
Rofiq, Anang May et al. 2016. “Optimalisasi Distribusi LPG 3 Kg Menggunakan Metode Linear Programming Pada PT Suka Damai Abadi Jember.” Artikel Ilmiah Mahasiswa 2016 : 1–8. https://repository.unej.ac.id/bitstream/handle/123456789/78200/Anang May Rofiq.pdf?sequence=1.
Siang, Jong Jek. 2014. Riset Operasi Dalam Pendekatan Algoritmis . 2nd ed. ed. FI. Sigit Suyantoro. Yogyakarta: C.V Andi Offset.
Sumbawa, Humas Bupati. 2019. “Bupati Buka Sosialisasi Konversi Minyak Tanah Ke Gas LPG .”
SumbawaKab . http://www.sumbawakab.go.id/read/5106/bupati-buka-sosialisasi-konversi-minyak- tanah-ke-gas- LPG .html.
Sutoni, Akhmad, and Nur Asilah. 2018. “Penentuan Jarak Pendistribusian Gas LPG 3 Kg Dengan Metode Algoritma Heuristik.” Jurnal Media Teknik dan Sistem Industri 2(2): 37.
( Akhir  halaman genap )