JTERA (Jurnal Teknologi Rekayasa), Vol. 6, No. 2, Desember 2021, Hal. 237-246 Terakreditasi “ Peringkat 3” oleh Kemenristek/BRIN, Nomor SK: 85/M/KPT/2020 DOI: 10.31544/jtera.v6.i2.2021.237-246
Diterima: 29 Oktober 2021; Direvisi: 30 November 2021; Disetujui: 8 Desember 2021 JTERA, Vol. 6, No. 2, Desember 2021 © 2021 JTERA (Jurnal Teknologi Rekayasa), Politeknik Sukabumi

## Analisis Pendistribusian Gas LPG 3 Kg dengan Metode Minimum Spanning Tree
Dinda Habibah Azzahra 1# , Aulia Fashanah Hadining 2 , Billy Nugraha 3
1,2 Program Studi S-1 Teknik Industri, Fakultas Teknik, Universitas Singaperbangsa Karawang Jl. HS Ronggo Waluyo, Kecamatan Telukjambe Timur, Kabupaten Karawang - 41361, Jawa Barat, Indonesia
3 Program dan Jurusan D-1 Administrasi Perkantoran, Akademi Komunitas Presiden Jababeka Education Park, Jl. Ki Hajar Dewantara Kota Jababeka, Bekasi - 17550, Jawa Barat, Indonesia
# dindahabibaha@gmail.com

## Abstrak
Salah  satu  hal  penting  dalam  pendistribusian  adalah  jalur  dan  jarak  yang  optimal  agar  distribusi  yang  dilakukan lebih  efektif  dan  efisien.  Pada  penelitian  ini,  metode spanning tree algoritma  Kruskal  dan  algoritma  Prim diimplementasikan untuk membantu dalam menentukan jarak optimal pada pendistribusian gas LPG 3 Kg. Penggunaan metode minimum spanning tree membutuhkan data titik awal dan tujuan, serta jarak yang akan ditempuh pada setiap titiknya. Dalam penelitian ini berfokus pada jarak pendistribusian yang ditempuh untuk mendistribusikan gas LPG 3 kg. Objek dalam penelitian kali ini adalah pangkalan gas LPG 3 Kg berlokasi di Kota Cirebon yang memiliki 50 tabung gas untuk didistribusikan setiap harinya. Setelah perhitungan dilakukan dengan cara manual dan dengan bantuan software POM QM, dihasilkan jarak pendistribusian sebesar 18.100 meter. Dengan adanya optimasi ini dihasilkan pengurangan jarak sebesar 10.900 meter. Maka dengan begitu jarak yang ditempuh lebih optimal dan dapat mengurangi total biaya pengeluaran pada bagian transportasi.
Kata kunci: minimum spanning tree , algoritma Kruskal, algoritma Prim, jarak optimal, distribusi

## Abstract
One of the important things in distribution is the optimal path and distance so that the distribution is carried out more  effectively  and  efficiently.  In  this  study,  the  Kruskal  algorithm  spanning  tree  method  and Prim's  algorithm  are implemented to assist in determining the optimal distance for the distribution of 3 Kg LPG gas. The use of the minimum spanning tree method requires data on the starting and destination points, as well as the distance to be traveled at each point. This study focuses on the distribution distance traveled to distribute 3 kg LPG gas. The object of this research is the  3  Kg  LPG  gas  base  located  in  Cirebon  City  which  has  50  gas  cylinders  to  be  distributed  every  day.  After  the calculation  is  done  manually  and  with  the  help  of  POM  QM  software,  the  resulting  distribution  distance  is  18,100 meters. This optimization resulted in a distance reduction of 10,900 meters. So that way the distance traveled is more optimal and can reduce the total cost of spending on the transportation department.
Keywords: minimum spanning tree, Kruskal algorithm, Prim algorithm, optimal distance, distribution

## I. P ENDAHULUAN
Salah satu strategi pemerintah untuk mengurangi penggunaan  minyak  tanah  di  Indonesia  adalah dengan mengkonversi penggunaan minyak tanah ke dalam  gas Liquified  Petroleum  Gas (LPG)  3  Kg. Maka penggunaan gas tersebut hanya diperuntukan untuk  warga  miskin  dan  pedagang  kecil.  Dengan begitu  pemerintah  menyiapkan  penyaluran  gas kepada  seluruh  masyarakat  Indonesia  [1]. Pemeritah  bekerjasama  dengan  Pertamina  untuk menyalurkan gas kepada masyarakat dan membuat
beberapa sub-sub agen serta distributor gas LPG 3 Kg  untuk  lebih  banyak  menyalurkan  kepada masyarakat  [2].  Namun  terdapat  beberapa  kendala dalam  menyalurkan  gas  ke  masyarakat.  Salah satunya  yaitu  kurang  efektifnya  jalur  distribusi. Maka, untuk mencegah kejadian tersebut, dilakukan pengoptimalan  jalur  transportasi  dengan  bantuan metode-metode optimasi yang sudah ada. Salah satu metode  optimasi  yang  dapat  digunakan  adalah metode minimum  spanning  tree .  Metode  ini  dapat membantu  untuk  menghindari  jalan  berulang  yang akan  dilalui  untuk  mendistribusikan  produk  [3].
Untuk  mempermudah  melakukan  penentuan  jalur efektif  pada  metode minimum  spanning  tree , peneliti  terdahulu  melakukan  penelitian  dan memiliki  perkembangan  untuk  mendapatkan algoritma yang dapat digunakan. Pada tahun 1956, Joseph  Kruskal  salah  seorang  ilmuan  terdahulu yang menemukan algoritma dengan nama algoritma Kruskal. Kemudian ilmuan lainnya Robert C. Prim (1957)  dan  Georges  Sollin  (1961)  menemukan algoritma  dengan  nama  algoritma  Prim  [4]. Algoritma  Prim merupakan  algoritma yang berawalan  dengan node tunggal  dan  selanjutnya tumbuh menjadi sebuah pohon [5].
Beberapa  penelitian  serupa  sebelumnya  telah dilakukan,  seperti  penelitian  Priyono,  dkk  yang bertujuan  untuk  menentukan  lintasan  terpendek pada effective call salesman di PT. BSP Purwokerto dengan  menggunakan  metode minimum  spanning tree algoritma  Kruskal.  Hasil  menunjukan  bahwa jarak yang ditempuh setelah melakukan perhitungan dengan  metode minimum  spanning  tree algorima Kruskal  adalah  sejauh  14.110  meter,  sedangkan sebelum  melakukan  perhitungan  dengan  metode minimum  spanning  tree algoritma  Kruskal  jarak yang ditempuhnya adalah sejauh 16.660 meter [6]. Penelitian  terdahulu  selanjutnya  adalah  penelitian yang di teliti oleh A. T. S. Aji, dkk dengan tujuan untuk  mencari  jalur  terpendek  yang  harus  dilalui kurir  untuk  mengirim  barang  dengan  metode assignment dan networking dengan  hasil  jarak optimum  yang  didapatkan  adalah  34  Km  [7]. Penelitian  lain  yang  disusun  oleh  Fatimah,  dkk bertujuan  untuk  menentukan  lintasan  yang mengarah  ke  pusat  perbelanjaan  di  Kota  Palopo menggunakan  metode minimum  spanning  tree algoritma  semut  dengan  data  jarak  antar  8  pusat perbelanjaan di Kota Palopo dan mendapatkan jarak minimum yang  diperoleh  adalah  sejauh  4,21  Km [8].  Selanjutnya  penelitian  yang  dilakukan  oleh  N. A.  Subidyo,  dkk  dengan  tujuan  untuk  mencari penyelesaian minimum  spanning  tree terpendek untuk  mendistribusikan  naskah  USBN  SD/MI  di Kabupaten  Sragen  dengan  metode minimum spanning  tree algoritma  Kruskal.  Hasil  jarak terpendek  yang  diperoleh  untuk  mendistribusikan naskah  USBN  SD/MI  dengan  perhitungan manual dan bantuan software TORA yaitu sejauh 112,2 Km [9].  Penelitian  selanjutnya  dilakukan  oleh  F. Annisa,  dkk  yang  bertujuan  untuk  melihat pengimplementasian dari metode minimum spanning  tree algoritma  Kruskal  dalam  sistem jaringan  listrik  di  Kota  Langsa  agar  dapat meminimumkan kabel listrik yang digunakan. Hasil yang  diperoleh  yaitu  adanya  perbedaan  panjang kabel  dan  total  sisi  yang  digunakan  untuk  sistem jaringan  listrik  sebelum  menggunakan  metode
minimum  spanning  tree algoritma  Kruskal  dan setelah  menggunakannya.  Panjang  kabel  listrik sebelum  menggunakan  metode minimum  spanning tree algortima  Kruskal  adalah  sepanjang  8.834 meter  dengan  total  sisi  40,  sedangkan  setelah menggunakan  metode spanning  tree algoritma Kruskal adalah sepanjang 7.581 meter dengan total sisi 34 [10].
Pemecahan  masalah  yang  dilakukan  pada penelitian ini adalah mengimplementasikan metode minimum  spanning  tree algoritma  Kruskal  dan algoritma Prim untuk membantu dan memberi saran perbaikan  di  pangkalan  gas  3  Kg  Sukandi.  Tujuan dari penelitian ini adalah mengetahui jarak dan jalur optimal  untuk  meminimalisir  terjadinya  jalur looping atau jalur berulang dari pendistribusian gas 3  Kg  Sukandi  dengan  mengggunakan  metode minimum  spanning  tree .  Dengan  meminimalisir terjadinya  jalur lopping atau  jalur  berulang,  maka diharapkan  dapat  mengurangi  biaya  pengeluaran untuk  keperluan  trasportasi  dan  mempersingkat waktu  untuk  pendistribusian  yang  dilakukan. Pembaruan  yang  dilakukan  dalam  penelitian  ini adalah menggunakan dua algoritma yaitu algoritma Kruskal  dan  algoritma  Prim  untuk  membantu  dan memvalidasi jalur dan jarak optimal pendistribusian yang  dilakukan.  Dua  algoritma  yang  digunakan memiliki  cara  penyelesaian  masalah  yang  berbeda namun  memiliki  tujuan  yang  sama  yaitu  untuk mengetahui jarak dan jalur yang optimal yang akan dilalui. Gap antara  penelitian  terdahulu  dengan penelitian  ini  adalah  terletak  pada  penggunaan algoritma  yang  digunakan,  dimana  penelitian terdahulu  hanya  menggunakan  satu  algoritma sedangkan  penelitian  ini  menggunakan  dua algoritma  dan  objek  penelitian  ini  dilakukan  pada pendistribusian  pangkalan  gas  3  Kg  Sukandi. Walaupun  sudah  menggunakan  dua  algoritma, namun untuk mengurangi kesalahan yang dilakukan pada  peorangan  atau human  error dilakukan perhitungan dengan bantuan software POM-QM for windows .

## II. M ETODE P ENELITIAN
Metode minimum  spanning  tree merupakan sebuah  metode  yang  diguanakan  untuk  lebih mengoptimalkan  jarak  agar  dapat  meminimalkan biaya  yang  dikeluarkan. Minimum  spanning  tree dapat  diaplikasikan  pada  bidang  transportasi, energi,  jaringan  komunikasi,  sampai  peningkatan akurasi  diagnostik  untuk  penyakit  Alzheimer  [11]. Algoritma Prim dan Kruskal sampai saat ini masih sering  digunakan  dalam  membantu  mencari  jalur efektif  yang  tidak  menimbulkan  jalur looping . Dengan  melihat  tujuan  dari  penelitian  ini  untuk
mencari  jalur  efektif  tanpa  adanya  jalur looping (berulang-ulang),  maka  dengan menggunakan algoritma  Kruskal  dan  Prim  merupakan  alternatif terbaik.  Hal  ini  karenakan  dari  penelitian sebelumnya  memiliki  kriteria  dalam  perhitungan yang  dapat  menemukan  jalur  efektif, tanpa  adanya looping dan  jarak  terpndek.    Penelitian  ini dilakukan secara sistematis maka untuk memperjelas alur penelitian yang dilakukan berikut merupakan  rangkaian  alur  penelitian  yang dilakukan dilapangan.

## A. Identifikasi Masalah
Permasalahan yang diangkat pada penelitian ini adalah  jalur  distribusi  yang  pendistribusian pangkalan gas 3 Kg Sukandi agar jalur yang dilalui saat  pendistribusian  tidak  terjadinya  jalur  berulang dan  membantu  mengurangi  waktu  pendistribusian serta  meminimalisir  pengeluaran  transportasi berupa  bahan  bakar.  Identifikasi  masalah  pada penelitian  ini  diawali  dengan  adaya  studi  literatur untuk menunjang referensi-referensi dari penelitian sebelumnya  dan  studi  lapangan  yang  dilakukan  di pangkalan  gas  3  Kg  Sukandi  yang  terletak  di Komplek  Taman  Evakuasi  Indah  Kota  Cirebon, 45135.

## B. Pengumpulan dan Pengolahan Data
Tahapan  pengambilan  data  yang  dilakukan berasal  dari  data  primer  dan  data  sekunder.  Data primer  yang  dimaksud  adalah  jalur  distribusi  yang dilalui  pada  saat  pendistribusian  gas  3  Kg  yang didapatkan dari wawancara yang dilakukan dengan pemilik  pangkalan  gas  3  Kg  Sukandi  [5]. Sedangkan  data  sekundernya  adalah  studi  literatur dari  peneliti  terdahulu  untuk  menunjang  referensi- referensi  pendukung  yang  berkaitan  dengan  jalur distribusi  dan  metode  yang  digunakan.  Teknik pengambilan sampel dalam penelitian ini menggunakan  metode non-probability  sampling yaitu  sebuah  metode  pengambilan  sampel  tidak menggunakan  peluang  yang  sama  pada  per  unsur populasi  yang  akan  dipilih  menjadi  sampel  [12]. Teknik yang digunakan dari non-probability adalah pusposive  sampling karena  dalam  penelitian  ini hanya  meneliti  gas  LPG  tabung  3  Kg  dan  hanya meneliti  50  tabung  sampel  yang  di  distribusikan secara rutin di pangkalan gas 3 Kg Sukandi. Setelah mendapatkan  data  yang  dibutuhkan  tahap selanjutnya adalah pengolahan data dengan metode minimum  spanning  tree algoritma  Kruskal  dan algoritma  Prim  serta  dengan  bantuan software POM-QM [13].
C. Melakukan  Perhitungan  Metode  Minimum Spanning  Tree  Algoritma  Kruskal  dan Alogoritma Prim
Penggunaan  metode minimum  spanning  tree bertujuan mencari jarak minimum dan optimal dari titik  awal  ke  titik  tujuan.  Langkah-langkah  untuk perhitungan spanning  tree algoritma  Kruskal sebagai berikut [10]:
1. Setiap sisi diurutkan pada setiap graf T dari sisi yang  memiliki  jarak  atau  bobot  yang  paling kecil sampai yang paling besar.
2. Memilih graf terkecil  dengan  acuan  sisi  yang terdapat pada langah ke-1.
3. Memilih  sisi  selanjutnya  dengan  jarak  atau bobot terkecil dan harus membentuk sirkuit di T.
4. Lanjutkan langkah 2 sebanyak n – 2 kali sampai semua  sisi  terpilih  dan  membentuk  sirkuit. Setelah itu akan didapatkan jarak minimun yang optimal.
Adapun  langkah-langkah  menggunakan  metode minimum  spanning  tree algoritma  Prim sebagai berikut [14]:
1. Memilih graf dengan  jarak  terkecil,  dengan menempatkan ke T.
2. Memilih  jarak  terkecil  dan  miliki  sisi  yang mendekati simpul T dengan catatan sirkuit dapat terbentuk di T.
3. Menyambungkan langkah 2 sejumlah n – 2 kali.
Jumlah  langkah-langkah  keseluruhan  dalam algoritma  Prim yaitu  1  +  ( n -  2)  = n –  1, merupakan  sebanyak  jumlah graf di  dalam spanning tree .
Langkah-langkah  yang  dibutuhkan  untuk menentukan  keseluruhan minimum  spanning  tree pada sembarang graf yang terhubung dengan bobot T sebagai berikut [15]:
1. Memilih  sembarang minimum  spanning  tree T, salah satu minimum spanning tree dari G. Pakai T untuk menguji semua edge dari G. Misal edge e di G. Selidiki apakah e di T atau ada f P (e, T) dimana w = w untuk semua edge yang akan  dipilih.  Jika  tidak  demikian,  maka edge tersebut dihapus dari G.
2. Misal  g  adalah edge yang  tidak  terhapus  di  G. Untuk  setiap edge g  yang  tidak  ada  di  T, tentukan kelas equivalen -nya (dinotasikan X(g)) yaitu  himpunan  yang  terdiri  dari  g  dan edge dengan  bobot  yang  sama  pada  P  (g,  T).  Jika terdapat  irisan  pada  kelas equivalen ,  tentukan kelas transitif-nya, yaitu gabungan dari beberapa kelas equivalen .  Tentukan  kelas  singleton-nya yaitu {e}, jika edge e T dan e X (g). Edge e ini  digunakan  pada  setiap minimum  spanning tree dari graf G.
3. Menentukan  anggota  himpunan  yang  terpilih dari  kelas equivalen X(g).  Dimulai  dengan  T
keseluruhan  dan  memindahkan  semua  anggota himpunan  dari  X(g)  untuk  mendapatkan  suatu subgraf H. Untuk setiap anggota himpunan dari X(g),  bentuk  kesatuan  dengan  H  dan  uji keterhubungannya.  Jika  terhubung,  maka anggota  himpunan  ini  merupakan  anggota himpunan terpilih dari kelas equivalen X(g). 4. Kombinasikan  secara  bebas  anggota  himpunan terpilih dari setiap kelas equivalen X(g) dengan mengalikan  banyaknya  anggota  himpunan terpilih  dari  setiap  kelas equivalen X(g)  untuk mendapatkan  semua minimum  spanning  tree yang ada dalam graf G.
Berikut  merupakan  gambaran  langkah-langkah penentuan minimum  spanning  tree dalam  bentuk flowchart yang dapat dilihat pada Gambar 1.
D. Melakukan Perhitungan Software POM-QM
Langkah-langkah yang dilakukan untuk melakukan  perhitungan  pada software POM-QM adalah sebagai berikut [3]:
1. Membuka software POM-QM  yang  sudah terpasang di windows .
2. Memilih  metode minimum  spanning  tree pada bagian kiri aplikasi.
Gambar 1. Flowchart langkah-langkah penentuan minimum spanning tree
3. Masukan data yang telah didapatkan sebelumnya  mengenai jarak dan titik awal serta tujuan pendistribusian.
4. Klik solve pada taskbar yang  tersedia,  akan muncul jaringan serta hasil jarak terpendek yang dihasilkan.
5. Analisis  dan  bandingkan  perhitungan manual dan perhitungan software POM-QM.

## E. Menarik Kesimpulan
Setelah  melakukan  perhitungan  dan  pengolahan data  maka  dibuat  beberapa  kalimat  hipotesis kesimpulan  penelitian  yang  dapat  membantu memberi  saran  memecahkan  masalah  yang  terjadi di  pangkalan  gas  3  Kg  Sukandi  yang  berkaitan dengan jalur pendistribusian yang dilakukan.

## III. H ASIL DAN P EMBAHASAN
Data  pendistribusian  yang  didapatkan  dari pangkalan gas 3 Kg adalah hasil observasi langsung dan wawancara dengan pemilik. Pendistribusian gas hanya dilakukan pendistribusian di daerah Cirebon seperti yang dapat di lihat pada Tabel 1. Gambar 2 menunjukan jaringan minimum spanning tree yang merupakan titik awal dan tujuan dari pendistibusian gas 3 Kg.
Tabel 1. Data pendistribusian pangkalan gas 3 kg
Sukandi Titik Awal - Titik Tujuan Titik Jarak (meter) Evakuasi - Bukepin 1,2 3770 Evakuasi - Perjuangan 1,3 1700 Evakuasi - Sutomo 1,9 3400 Bukepin - Perjuangan 2,3 4190 Perjuangan - Kalikoa 3,4 1610 Kalikoa - Pilang Raya 4,5 4530 Pilang Raya - Sutomo 5,9 3700 Pilang Raya - Samadikun 5,6 3190 Samadikun - Kebonpring 6,7 2670 Kebonpring - Petratean 7,8 240 Petratean - Sutomo 8,9 1520
Gambar 2. Jaringan minimum spanning tree pendistribusiaan gas 3 Kg Sukandi
Tidak YA Mulai Pilih  sembarang Minimum Spanning Tree T, salah satu Minimum Spanning Tree dari G

## Tentukan equivalen
Tentukan anggota himpunana yang terpilih  dari kelas equivalen
Kombinasikan  bebas himpunan yang terpilih Apakah Hasil Sudah Sesuai? Menarik kesimppulan Perhitungan Selesai 1 9 8 7 6 5 4 3 2 3700 2760
Pendistribusian  yang  dilakakukan  pangkalan  gas 3 Kg tersebut mencapai jarak hingga 29.000 meter atau 29 Km. Oleh karena itu, untuk meminimalkan jarak  pendistribusian  dan  agar  dapat  mengurangi biaya pengiriman, serta mempersingkat waktu yang dibutuhan  maka  digunakan  perhitungan  dengan metode minimum spanning tree alogritma Prim dan Kruskal.
Langkah-langkah  untuk  mencari jarak  terpendek dari pendistribusian gas 3 Kg dengan menggunakan algoritma  Prim  ditunjukkan  Gambar  3  sampai Gambar 11.
Gambar  3  menunjukan  pemilihan  jarak terpendek yang berasal dari titik awal pendistribusian  gas  3  Kg  dengan  memilih  jarak antara node 1  dan node 3.  Jarak  terpendek  kedua yang dipilih setelah node 1 dan node 3 yang dilihat pada  Gambar  3  adalah  antara node 3  dan node 4 dan  jaringan  yang  saling  terhubung  yang  dapat dilihat  pada  Gambar  4.  Gambar  5  menunjukan pemilihan  jarak  terpendek  ketiga  yang  dipilih selanjutnya  yaitu  jarak  antara node 1  dan node 2. Gambar  6  menunjukan  pemilihan  jarak  terpendek selanjutnya  yaitu  jarak  antara node 1  dan node 9 karena  menunjukkan  jarak  terpendek  yang  ada dibandingkan dengan jarak-jarak lainnya dari node yang  sudah  dipilih.  Gambar  7  menunjukan pemilihan  jarak  terpendek  selanjutnya  yaitu  jarak antara node 9 dan node 8 karena menunjukkan jarak terpendek  yang  ada  dibandingkan  dengan  jarak- jarak lainnya dari node yang sudah dipilih. Gambar 8 menunjukan pemilihan jarak terpendek selanjutnya  yaitu  jarak  antara node 8  dan node 7 karena  menunjukkan  jarak  terpendek  yang  ada dibandingkan dengan jarak-jarak lainnya dari node yang  sudah  dipilih.  Gambar  9  menunjukan pemilihan  jarak  terpendek  selanjutnya  yaitu  jarak antara node 7 dan node 6 karena menunjukkan jarak terpendek  yang  ada  dibandingkan  dengan  jarak- jarak lainnya dari node yang sudah dipilih. Gambar 10  menunjukan  pemilihan  jarak  terpendek selanjutnya  yaitu  jarak  antara node 6  dan node 5 karena  menunjukkan  jarak  terpendek  yang  ada dibandingkan dengan jarak-jarak lainnya dari node yang  sudah  dipilih.  Gambar  11  merupakan  hasil dari  jaringan minimum  spanning  tree dengan menggunakan algortima Prim yang pada pangkalan gas 3 Kg Sukandi.
Gambar 3. Iterasi 1 algoritma Prim dengan memilih node 3 yang memiliki jarak terpendek
Gambar 4. Iterasi 2 algoritma Prim dengan memilih node 4 dibandingkan node 2 yang memiliki jarak lebih pendek
Gambar 5. Iterasi 3 algoritma Prim dengan memilih node 2 yang memiliki jarak lebih pendek dibandingkan node 5
Gambar 6. Iterasi 4 algoritma Prim dengan memilih node 9 karena memiliki jarak terpendek dibandingkan dengan node 5
1 9 8 7 6 5 4 3 2 3700 2760 1 9 8 7 6 5 4 3 2 3700 2760 1 9 8 7 6 5 4 3 2 3700 2760 1 9 8 7 6 5 4 3 2 3700 2760
Gambar 7. Iterasi 5 algoritma Prim memilih node 8 karena jarak terpendek dari semua node yang belum terpilih
Gambar 8. Iterasi 6 algoritma Prim dengan memilih node 7 karena jaraknya yang lebih pendek dibandingkan node 5
Gambar 9. Iterasi 7 algoritma Prim dengan memilih node 6 karena merupakan jarak terpendek dibandingkan dengan node lainnya
Gambar 10. Iterasi 8 algoritma Prim memilih jarak antara node 6 menuju node 5
Gambar 11. Hasil jaringan minimm spanning tree algoritma Prim
Selanjutnya  adalah  perhitungan  menggunakan metode minimum spanning  tree Kruskal.  Metode minimum  spanning  tree algortima  Kruskal dapat diasumsikan  dengan  cara  terlebih  dahulu  memilih graf berurutan dari jarak atau bobot yang terkecil ke jarak  atau  bobot  yang  terbesar  [2].  Perhitungan minimum  spanning  tree algoritma  Kruskal  dan algoritma  Prim  dimulai  Tabel  2  yang  merupakan urutan  jarak  terpendek  dari  pendistribusian  gas  3 Kg yang telah diurutkan dari data yang didapatkan sebelumnya  dan  dilanjutkan  dengan  membuat jaringan-jaringan lintasan pendistribusian.
Gambar  12  menunjukan  jaringan  jarak terpendek dari pendistrbusian yang dilakukan yaitu node 8  dan node 7.  Gambar  13  menunjukan jaringan  jarak  terpendek  kedua  dari  pendistrbusian yang  dilakukan  yaitu node 8  dan node 9.  Gambar 14 menunjukan jaringan jarak terpendek ketiga dari pendistrbusian  yang  dilakukan  yaitu node 3  dan node 4.  Gambar  15  menunjukan  jaringan  jarak terpendek  keempat  dari  pendistrbusian  yang dilakukan  yaitu node 3  dan node 1.  Gambar  16 menunjukan  jaringan  jarak  terpendek  kelima  dari pendistrbusian  yang  dilakukan  yaitu node 7  dan node 6.  Gambar  17  menunjukan  jaringan  jarak terpendek  keenam  dari  pendistrbusian  yang dilakukan  yaitu node 6  dan node 5.  Gambar  18 menunjukan  jaringan  jarak  terpendek  ketujuh  dari pendistrbusian  yang  dilakukan  yaitu node 1  dan node 9.  Gambar  19  menunjukan  jaringan  jarak terpendek  kedelapan  dari  pendistrbusian  yang dilakukan  yaitu node 1  dan node 2.  Dan  dapat dilihat  juga  pada  Gambar  19  tergambar  jaringan atau  jalur  yang  akan  dilewati  oleh  pendistribusian pangkalan gas 3 Kg Sukandi.
1 9 8 7 6 5 4 3 2 3700 2760 1 9 8 7 6 5 4 3 2 3700 2760 1 9 8 7 6 5 4 3 2 3700 2760 1 9 8 7 6 5 4 3 2 3700 2760 1 9 8 7 6 5 4 3 2 2760
Tabel 2. Urutan jarak terpendek pendistribusian
Titik awal - Titik tujuan Titik Jarak (dalam meter) Kebonpring - Petratean 7,8 240 Petratean - Sutomo 8,9 1520 Perjuangan - Kalikoa 3,4 1610 Evakuasi - Perjuangan 1,3 1700 Samadikun - Kebonpring 6,7 2670 Pilang Raya - Sutomo 5,6 3190 Evakuasi - Sutomo 1,9 3400 Pilang Raya - Sutomo 5,9 3700 Evakuasi - Bukepin 1,2 3770 Bukepin - Perjuangan 2,3 4190 Kalikoa - Pilang Raya 4,5 4530
Gambar 12. Iterasi 1 algoritma kruskal memilih node 8 dan node 7 karena merupakan jarak terpendek
Gambar 13. Iterasi 2 algoritma kruskal memilih node 8 dan node 9
Gambar 14. Iterasi 3 algoritma kruskal memilih node 3 dan node 4
Gambar 15. Iterasi 4 algoritma kruskal dengan memilih node 1 node 3
Gambar 16. Iterasi 5 algoritma kruskal dengan memilih jarak antara node 7 dan node 6
Gambar 17. Iterasi 6 algoritma kruskal dengan memilih node 6 dan node 5
Gambar 18. Iterasi 7 algoritma kruskal memilih node 1 dan node 9
Gambar 19. Iterasi 8 algoritma kruskal dengan memilih node 1 dan node 2 dan jaringan akhir pendistribusian
1 9 8 7 6 5 4 3 2 3700 2760 1 9 8 7 6 5 4 3 2 3700 2760 1 9 8 7 6 5 4 3 2 3700 2760 1 9 8 7 6 5 4 3 2 3700 2760 1 9 8 7 6 5 4 3 2 3700 2760 1 9 8 7 6 5 4 3 2 3700 2760 1 9 8 7 6 5 4 3 2 3700 2760 1 9 8 7 6 5 4 3 2 3700 2760
Gambar 20. Hasil perhitungan software minimun spanning tree 1
Gambar 21. Hasil perhitungan software minimun spanning tree 2
Untuk melakukan validasi dari hasil perhitungan yang  telah  dilakukan  secara  manual,  maka dilakukan  perhitungan  dengan  menggunakan software POM  QM  yang  dapat  di  lihat  pada Gambar  20  dan  Gambar  21.  Gambar  20  dan Gambar 21 menjelaskan hasil yang didapatkan dari software POM  QM sebesar  18.100  meter.  Hal  ini menandakan  bahwa  perhitungan  manual  dan software memiliki  hasil  yang  sama  baiknya.  Dari hal  ini  dapat  disimpulkan  bahwa  tidak  adanya kesalahan  dalam  melakukan  perhitungan  secara manual.

## IV. K ESIMPULAN
Setelah  melakukan  penelitian  ini  dengan menggunakan  metode minimum  spanning  tree algoritma  kruskal dan  algoritma  prim. Terbukti dapat  membantu  untuk  mengoptimalkan  jarak pendistribusian gas 3 Kg. Hal ini dapat mengurangi jarak  sebesar  10.900  meter,  yang  pada  awalnya sebelum  dilakukan  perhitungan  adalah  sebesar 29.000  meter.  Selain  itu  setelah  dilakukan
perhitungan dengan menggunakan manual spanning  tree melalui  bantuan  validasi,  yaitu software POM QM. Maka didapatkan jarak efektif yang  ditempuh  untuk  pendistribusian  gas  3  Kg adalah 18.100 meter dengan jalur efektif yang telah dipaparkan  di  atas.  Dengan  tujuan  agar pendistribusian  gas  3  Kg  dapat  lebih  optimal  dan mengurangi  pengeluaran  yang  disebabkan  oleh transportasi.  Lintasan  yang  dapat  dilewati  dalam pendistribusian gas 3 Kg dapat dilihat pada Gambar 11 atau Gambar 19 yang dimana menunjukan jalur- jalur  optimal  yang  telah  diperhitungkan.  Untuk peneliti  selanjutnya  dapat  lebih  teliti  dalam menentukan  jaringan minimum  spanning  tree dan jarak yang ditempuh setiap tujuannya.

## R EFERENSI
[1]   B.  Nugraha,  "Pengembangan  Sumber  Daya Manusia:  Deskripsi  Teoretis  tentang  Kinerja Pegawai,  Penilaian  Kinerja  Pegawai  dan Pemeliharaan  SDM,  Banyumas:  CV.  Pena
Persada," 2021.
[2]   B.  A.  Picunang,  S.  Dampang,  V.  Efelina  and  B. Nugraha,  "Penentuan  Harga  Bahan  Bakar  Gas Kendaraan Menggunakan Simulasi Monte Carlo," JTERA (Jurnal Teknologi Rekayasa), vol. 5, no. 1, pp. 135-150, 2020.
[3]   M.  D.  R.  Fauzi,  W.  Wahyudin  and  B.  Nugraha,
"Optimalisasi Penentuan Jalur Diistribusi
Terpendek  Menggunakan  Spanning  Tree  dan Nearest  Neighbor," JTERA  (Jurnal  Teknologi Rekayasa), vol. 6, no. 1, pp. 121-130, 2021.
[4]   N.  J.  Triami,  Yundari  and  F.  Fran,  "Minimum Spanning  Tree  pada  Jaringan  Fiber  Optic  di Universiitas  Tanjungpura," Bimaster  :  Buletin Ilmiah  Matematika,  Statistika  dan  Terapannya, vol. 9, no. 1, pp. 223-230, 2020.
[5]   G. Agnia, D. Herwanto, I. Hoerunisa, B. Nugraha and R. P. Sari, "Optimize the Time and Network on  the  Distribution  of  Tempe  Industry  by  Using the Approach of the Assignment and Networking," Jurnal Serambi Engineering, vol. 6,
no. 2, pp. 1670-1682, 2021.
[6]   Priyono, "Algoritma Kruskal Menentukan Lintasan  Terpendek  Efektif  Call  Salesman," Fusioma  (Fundamental  Scientific  Journal  of Mathematics) : Jurnal Ilmiah Matematika Dasar, vol. 1, no. 1, pp. 25-32, 2021.
[7]   A.  T.  S.  Aji,  R.  P.  Sari  and  D.  Dede,  "Analisis Optimalisasi  Penempatan  dan  Efisiensi  Jarak Perjalanan  Kurir  Ke  Berbagai  Tujuan  dengan Metode Assignment dan Networking," Barometer, vol. 6, no. 2, pp. 343-351, 2021.
[8]   Fatimah and M. Sam, "Aplikasi Algoritma dalam Menentukan Pohon Merentang Minimum (Minimum  Spanning  Tree)  terhadap  Lintasan yang  Mengarah  ke  Pusat  Perbelanjaan  di  Kota Palopo," Infinity Jurnal Matematika & Aplikasinya, vol. 1, no. 1, pp. 1-7, 2020.
[9]   N.  A.  Sudibyo,  T.  Purwanto  and  D.  Rahmadi, "Minimum Spanning Tree pada  Distribusi Bahan Naskah  USBN  SD/MI  di  Kabupaten  Sragen," Riemann  :  Research  of  Mathematics  and Mathematics  Education, vol.  2,  no.  2,  pp.  64-69,
2020.
[10]  F.  Annisa  and  F.  Muliani,  "Penerapan  Algoritma Kruskal  dalam  Sisrem  Jaringan  Listrik  di Kecamatan  Langsa  Baro," Jurnal  Gamma-Pi  :
Jurnal  Matematika  Terapan  dan  Pendidikan Matematika, vol. 2, no. 2, pp. 5-9, 2020.
[11]  G.  D.  Rembulan,  J.  A.  Luin,  V.  Julianto  and  G.
Septorino,  "Optimalisasi  Panjang  Jaringan  Pipa Air  Bersih  di  DKI  Jakarta  Menggunakan Minimum  Spanning  Tree," Jurnal  Intech  Teknik Industri  Universitas  Serang  Raya, vol.  6,  no.  1, pp. 75-87, 2020.
[12]  Sugiyono, Metode Penelitian Kuantitatif, Kualitatif, dan R&D, Bandung: Alfabeta, 2017.
[13]  G.  A.  Sari,  D.  Herwanto  and  B.  Nugraha, "Optimalisasi  Waktu  Kerja  dan  Jaringan Pendistribusian  Makanan  Ringan  Menggunakan Model  Assignment  dan  Hungarian," Inaque  : Journal  of  Industrial  and  Quality, vol.  9,  no.  1, pp. 81-95, 2021.
[14]  N. Yannuansa, J. W. Leksono, A. Mutrofin and A. Samudra,  "Keoptimuman  Jaringan  Listrik  di Perumahan  Pulo  Asri  dengan  Algoritma  Prim," Discovery : Jurnal Ilmu Pengetahuan, vol. 5, no. 1, pp. 38-44, 2020.
[15]  T.  Hartati,  F.  Ubaidillah  and  A.  Kamsyakawuni, "Penentuan Semua Minimum Spanning Tree Graf Terhubung Berbobot,"
Majalah Ilmiah
Matematika dan Statistika, vol. 15, no. 2, pp. 49- 60, 2015.
[16]  Wamiliana,  M.  Usman,  Warsito,  Warsono  and  J. I.  Daoud,  "Using  Modification  of  Prim's Algorithm  and  GNU  Octave  and  to  Solve  the Multiperiods  Installation  Problem," International Islamic University Malaysia Engineering Journal, vol. 21, no. 1, pp. 100-112, 2020.
[17]  S.  Lailiyah,  Kusaeri  and  W.  Y.  Rizki, "Identifikasi  Proses  Berpikir  Siswa  dalam Menyelesaikan Masalah Aljabar dengan
Menggunakan  Representasi  Graf," Jurnal  Riset Pendidikan Matematika, vol.  7, no. 1, pp. 25-44, 2020.
[18]  S.  A.  Sholikhatin,  A.  B.  Prasetyo  and  A. Nurhopipah,  "Implementasi  Algoritma  Kruskal dan Algoritma Prim suatu Graph dengan Aplikasi Berbasis Dekstop," Jurnal Resistor, vol. 3, no. 2, pp. 83-93, 2020.