Jurnal Sains Komputer & Informatika (J-SAKTI) Volume (2) No.2 September 2018, pp. 121 - 129 ISSN:2548-9771/EISSN:2549-7200 http://tunasbangsa.ac.id/ejurnal/index.php/jsakti

## Penentuan Rute Terpendek Jalur Distribusi Air Artesis Menggunakan Kruskal
Diah Ayu Retnani Wulandari 1 , Fajrin Nurman Arifin 2 1,2 Fakultas Ilmu Komputer, Universitas Jember Jl. Kalimantan No.37 Jember 68121 Indonesia, (0331)326935/(0331)326911 diah.retnaniw@unej.ac.id, fajrin.pssi@unej.ac.id
Abstract
Water flow distribution to home residents from the artesian well is affected by infrastructure. The more houses that distributed makes decreased amount  supply of artesian water in every house. the longer of pipe leight and many branches  traversed makes decrease of water supply because  there  will  be  many  possible  pipeline  leaks.  The  more  pipes  used  make  the  more expensive  infrastructure  cost.  This  problem  occurs  in    Jubung  area.  These  problems  is  one variation of the minimum Spanning Tree problems. This problem can be solved by the shortest path  optimization  route.  It  uses  network  method  by  implementing  graph  theory  through kruskal algorithm. The first step is determined the nodes and sides. Nodes represent house and the  sides  represents  the  connecting  pipes  between  houses.  Kruskal  is  chosen  because  the kruskal  focuses  on  the  side  and  the  graph  is  incomplete.  focus  of  this  study  is    the  length optimation of the connecting pipe that is represented by side. In the pipe infrastructure figure map  is  representing  of  an  incomplete  graph  because  there  are  several  nodes  that  are  not connected  to  all  nodes  because  it  is  adapted  to  the  contour  of  the  land  that  is  not  possible traversed the pipe. The results is there are several paths that are changed, especially the side to connect between node 1-4, 4-12, 19-20, 21-6 dispensed because forming cycles. The result of this research is kruskal can make decreasing  infrastrukture cost Rp.7.535.500 with length of 201,5 meter so can save Rp.4.401.000 from Rp Rp.11.936.500.
Keywords : kruskal, graf, network,minimum Spanning Tree,research operations

## Abstrak
Pendistribusian  aliran  air  dari  artesis  sumur  bor  ke  rumah  penduduk  dipengaruhi  oleh infrastruktur.  Semakin  banyak  rumah  yang  dialiri  air  maka  semakin  berkurangnya  jumlah pasokan  air  tiap  rumah.  Semakin  banyak  pipa  yang  digunakan  maka  biaya  infrastruktur semakin  mahal.  Permasalahan  ini  terjadi  pada  daerah  Jubung.  Permasalahan  ini  dapat diselesaikan melalui rekomendasi pengambilan keputusan optimasi pencarian jalur terpendek rute  aliran  air. Permasalahan  ini  termasuk  permasalahan  dalam  minimum  Spanning  Tree. Penelitian ini menggunakan metode jaringan atau network pada bidang riset operasi dengan mengimplementasikan teori graf melalui algoritma kruskal. Langkah awal adalah menentukan node  dan  sisi.  Node  merepresentasikan  rumah  penduduk  dan  busur  merepresentasikan  pipa penghubung antar rumah. Algoritma kruskal dipilih karena algoritma kruskal berfokus pada sisi  dan  graf  tidak  lengkap.  Fokus  pada  penelitian  ini  adalah  optimasi  panjang  pipa penghubung  yang  direpresentasikan  dengan  sisi.  Pada  gambar  peta  infrastruktur  pipa  yang telah dibangun diketahui bahwa gambar tersebut merupakan graf tidak lengkap karena ada beberapa node yang tidak  saling terhubung semua hal ini karena disesuaikan dengan kontur tanah yang tidak memungkinkan dilalui pipa. Hasil perhitungan ini adalah ada beberapa jalur yang  dirubah  terutama  sisi  penghubung  node  1-4,  4-12,  19-20,  21-6  ditiadakan  karena membentuk  siklus.  Hasil  penggunaan  pipa  sebelum  menggunakan  algoritma  kruskal  adalah Rp.11.936.500 dengan panjang 340 meter dan setelah menggunakan algoritma kruskal adalah Rp.7.535.500 dengan panjang 201,5 meter sehingga dapat menghemat Rp.4.401.000.
Kata kunci : kruskal, graf, network,minimum Spanning Tree, riset operasi
Jurnal Sains Komputer & Informatika (J-SAKTI) Volume (2) No.2 September 2018, pp. 121 - 129 ISSN:2548-9771/EISSN:2549-7200 http://tunasbangsa.ac.id/ejurnal/index.php/jsakti

## 1. PENDAHULUAN
Air  bor  adalah  air  yang  berasal  dari  pembuatan  sumur  dengan  alat bantu  bor  untuk  memperoleh  sumber  air  artesis.  Semakin  cepatnya perkembangan  penduduk  dan  semakin  sempitnya  lahan  hijau  menjadikan sumber  air  semakin  sedikit  [1][2].  Masalah  air  bersihpun  semakin  banyak ditemui. Pada saat ini air bersih yang diperoleh oleh masyarakat berasal dari dua jenis sumber yaitu sumur bor dan PDAM. Penggunaan air artesis  banyak sekali diterapkan oleh masyarakat karena dapat menghemat listrik dan tidak dibatasi seperti penggunaan air PDAM. Pada pendistribusiannya penggunaan air  dari  sumur  bor  yang  mengalirkan  air  dari  sumber  mata  air  ke  rumah rumah  penduduk  membutuhkan  alat  penghubung  berupa  pipa. Pendistribusian  ini  sangat  mempengaruhi  pasokan  air  bersih  kerumah rumah penduduk. Semakin berkembangnya penduduk maka semakin banyak rumah  yang  harus  dialiri  air  bersih  sehingga  akan  berdampak  semakin berkurangnya jumlah pasokan air. Semakin jauh jarak rumah dengan sumber air  atau  semakin  banyaknya  cabang  yang  dilalui  maka  akan  mempengaruhi jumlah  pasokan  air  yang  semakin  kecil  kerumah  rumah  penduduk  karena akan  banyak  kemungkinan  terjadinya  kebocoran  pipa  dan  semakin banyaknya  salura  pipa  yang  dibangun  maka  akan  semakin  mahal  biaya pembangunan,  pengembangan  dan  pemeliharaan  infrastruktur  air  bersih menggunakan sumur bor. Permasalahan itu yang sering ditemui dibeberapa tempat didaerah jember kususnya daerah Jubung seperti yang terlihat pada gambar 1 denah peta pipa sumur bor .

## Gambar 1. Denah Peta Pipa Air Bor
Pada  gambar  satu  terlihat  ada  23  titik  rumah  penduduk  yang terhubung  dengan  panjang  340  meter  pipa  penghubung.  Pada  gambar  1 terlihat  bahwa  banyak  sekali  rumah  yang  tersaluri  air  dari  banyak  saluran pipa akibat  pengembangan  pipa dari areal rumah penduduk baru,  ada jalur yang  memiliki  banyak  cabang  dan  ada  yang  sedikit  cabangnya  sehingga
Jurnal Sains Komputer & Informatika (J-SAKTI) Volume (2) No.2 September 2018, pp. 121 - 129 ISSN:2548-9771/EISSN:2549-7200 http://tunasbangsa.ac.id/ejurnal/index.php/jsakti
terjadi ketidakseimbangan saluran air bersih dari sumur bor. Permasalahan aliran  air  bersih  dari  sumur  bor  yang  ada  dijember  ini  maka  dibutuhkan suatu  penyelesaian  berupa  rekomendasi  pengambilan  keputusan  pencarian jalur  terpendek  rute  pipa  air  bersih.  Pada  penelitian  ini  menggunakan metode network yang merupakan salah satu metode dari riset operasi.
Riset  operasi  adalah  salah  satu  bidang  ilmu  yang  ada  pada  teknologi informasi  untuk  menyelesaikan  permasalahan  permasalahan  yang  ada diseputar produksi. Permasalahan yang diselesaikan adalah tentang optimasi produksi  seperi  mencari  keuntungan  yang  besar  atau  penggunaan  biaya minimal yang dikeluarkan untuk produksi terkait penggunaan sumber daya, optimasi permasalahan jaringan. Salah satu optimasi jaringan adalah mencari rute  terpendek  yang  merupakan  salah  satu  permasalahan  di  minimum Spanning Tree . Metode ini untuk menyelesaikan permasalahan dalam analisa jaringan  untuk  menentukan  sisi  atau  busur  yang  menghubungkan  antar simpul atau  node secara efisien untuk memperoleh total minimum panjang sisi (atau busur). Pada metode ini tidak diperkenankan atau dihidarkan jalan berulang yang menyebabkan terjadinya looping atau siklus dari node satu ke node yang lain.   Permasalahan ini banyak sekali mengimplementaskan teori graf  dengan  menggunakan  salah  satu  algoritmanya  adalah  kruskal  [4]. langkah  langkah  yang  umum  dilakukan  pada  permasalahan  minimum Spanning  Tree adalah  memilih  salah  satu  simpul  sembarang  yang  memiliki bobot  terkecil  kemudian  dihubungkan  ke  node  terdekat  atau  terpendek berikutnya  untuk  dimasukkan  kedalam  satu  kelompok  setelah  itu  langkah langkah  tersebut  di  ulang  hingga  semua  node  terhubung  dan  tanpa  ada looping  [3]  Pada  permasalahan  dikehidupan  sehari  hari  dapat  diselesaikan dengan  menggunakan  logika  matematika,  salah  satunya  graf.  graf  dapat digunakan  untuk  merepresentasikan  permasalahan  dalam  bentuk  diskrit. graf  merepresentasikan  sebuah  object  dengan  menggunakan  bulatan  atau node dan sisi sebagai penghubung antar node [4].
Pada  penelitian  sebelumnya  tentang  jaringan  aliran  air  PDAM  [5] membahas  bahwa  jaringan  aliran  air  dapat  direpresentasikan  sebagai  graf, dimana  rumah  sebagai  verteks  sedangkan  pipa  sebagai  sisi  [5].  Perbedaan dengan  penelitian  ini  bobot  sisi  dilihat  dari  panjang  pipa  yang  terhubung antar  rumah  dan  sumber  air  sehingga  tahapan  awal  adalah  menganalisis biaya dari bentuk pipa panjang pipa dan banyak pipa yang digunakan untuk menyalurkan air sumur bor. Pada penelitian ini juga memperhatikan struktur tanah yang akan dilalui pipa dan hanya merekonstruksi pipa yang sudah ada tanpa membuat jalur pipa baru sehingga node dan sisi diperoleh dari denah. Ketika ada rute terpendek namun belum ada jalur pipa akhirnya ditiadakan karena  kemungkinan  tidak  dilewati  akibat  dari  kontur  tanah  yang  tidak memungkinkan dilalui pipa.
Algoritma  kruskal  merupakan  algoritma  yang  menitik  beratkan  pada bobot  dari  sisi  bukan  simpul  sehingga  cocok  digunakan  untuk  kasus  yang memiliki banyak simpul dari pada jumlah sisi dan semua simpul tidak saling
Jurnal Sains Komputer & Informatika (J-SAKTI) Volume (2) No.2 September 2018, pp. 121 - 129 ISSN:2548-9771/EISSN:2549-7200 http://tunasbangsa.ac.id/ejurnal/index.php/jsakti
terhubung  dengan  simpul  lainnya  atau  graf  tidak  lengkap  dengan  kata  lain algoritma kruskal digunakan untuk pencarian sisi dengan memberikan bobot disetiap  sisi  [1].  Pada  kasus  ini  jumlah  simpul  lebih  sedikit  dari  jumlah  sisi namun setiap simpul ada yang tidak saling terhubung satu dengan yang lain, ada beberapa simpul yang tidak saling terhubung dengan simpul lainnya dan pada  kasus  ini  menitik  beratkan  pada  pencarian  sisi  karena  sisi merepresentasikan  pipa  yang  digunakan  sehingga  dipilihlah  menggunakan algoritma kruskal.

## 2. METODOLOGI PENELITIAN
Pada peneltian ini menggunakan salah satu metode pada riset operasi yaitu metode jaringan. Tahap-tahap dalam Riset Operasi yaitu pembentukan model  dengan  mentransformasikan  analisa  situasi  kedalam  persamaan logika matematika. Tahapan yang dilalui adalah:
a. Identifikasi analisa situasi
Tahapan  awal  pada  penelitian  ini  adalah  identifikasi  masalah  melalui hasil  analisa  situasi.  Kegiatan  yang  dilakukan  adalah  pengumpulan  data berupa data primer dan sekunder. Data primer didapat dari hasil wawancara dan  survey  yang  bertujuan  memperoleh  permasalahan  kondisi  lapangan secara nyata dan variabel yang mempengaruhi permasalahan tersebut. data data yang diperoleh adalah data peta jalur pipa sumur air bor dan data pipa jalur  sumur  bor.  Data  sekunder  diperoleh  melalui  tahapan  studi  literatur untuk  mengetahui  metode  yang  digunakan  dalam  menyelesaikan  masalah. Pada  tahapan  pengumpulan  data  ini  diperoleh  data  untuk  menentukan variabel keputusan dan tujuan.
1) Variabel keputusan pada penelitian ini adalah node dari rumah rumah penduduk yang dialiri sumur bor.
2) Tujuan  (objective).  Tujuannya  adalah  untuk  menentukan  jalur terpendek agar setiap rumah dialiri air dari sumur bor
3) Pembobotan  pada  penelitian  ini  adalah  menggunakan  jarak  setiap titik  rumah  yang  disebut  dengan  node  dan  biaya  pipa  yang dibutuhkan untuk menghubungkan setiap rumah.

## b. Pembentukan Model
Pada penelitian ini pembentukan model menggunakan metode network yaitu  pada  permasalahan  di  Minimum Spanning  Tree dengan  algoritma kruskal.
c. Mencari Penyelesaian Masalah
Pada tahap ini implementasi algoritma kruskal untuk menentukan rute terpendek  kemudian  hasil  dari  analisa  perhitungan  tersebut  digunakan sebagai  alat  untuk  pengambilan  keputusan.  Pada  tahapan  penyelesaian permasalahan object direpresentasikan dalam bentuk graf.
Jurnal Sains Komputer & Informatika (J-SAKTI) Volume (2) No.2 September 2018, pp. 121 - 129 ISSN:2548-9771/EISSN:2549-7200 http://tunasbangsa.ac.id/ejurnal/index.php/jsakti
pada  mencari  pohon  rentang  minimum  dari  graf  G  dengan  algoritma  yang ditemukan Kruskal, mula-mula semua garis dalam G diurutkan berdasarkan bobotnya dari kecil ke besar. Kemudian pilih garis dengan bobot terkecil [3], tetapi  tidak  membentuk  loop  dengan  garis-garis  yang  sudah  dipilih terdahulu.
Misalkan  G  adalah  graf  mula-mula  dengan  n  titik,  T  adalah  Pohon Merentang  Minimum  E  himpunan  semua  garis  G.  Secara  formal,    algoritma yang ditemukan Kruskal dapat dinyatakan sebagai berikut [6]:
1.  Isi T dengan semua titik-titik G tanpa garis 2.  m = 0
3.  Selama m < (n-1) lakukan :
a. Tentukan garis e elemen E dengan bobot minimum. Jika ada beberapa e dengan sifat tersebut, pilih salah satu secara sembarang
b. Hapus e dari E
c. Jika e ditambahkan ke T tidak menghasilkan sirkuit, maka :
1) Tambahkan e ke T
2) m = m + 1
Tahapan  berikutnya  setelah  penentuan  rute  terpendek  adalah  analisa hasil perhitungan untuk mengetahui perubahan panjang pipa dan perubahan biaya pemasangan pipa.

## 3. HASIL DAN PEMBAHASAN
a.  Jalur  Pipa  Pendistribusian  Air  Bor  tanpa  Menggunakan  Algoritma Kruskal
Gambar  2. Saluran pipa sumur bor awal
Pada gambar 2 merupakan saluran pipa sumur bor awal sesuai dengan analisis  sitasi  hasil  wawancara  dan  survey  terdapar  23  rumah  dengan panjang  340  meter.    Pada  gambar  2  terlihat  banyak  beberapa  titik  rumah
Jurnal Sains Komputer & Informatika (J-SAKTI) Volume (2) No.2 September 2018, pp. 121 - 129 ISSN:2548-9771/EISSN:2549-7200 http://tunasbangsa.ac.id/ejurnal/index.php/jsakti
yang  dilalui  banyak  saluran  Dalam  hal  ini  merupakan  gambaran  jalur  pipa dalam pendistribusian air bor di daerah Jubung tanpa menggunakan algritma kruskal,  yang  awalnya  pajang  pipanya  340  meter.  Pada  gambar  2  terlihat banyak node yang dialiri banyak jalur seperti pada titik 20 terhubung dengan 4 titik yaitu titik 19,7,21,22, selain itu ada titik titik yang terjadi perputaran ( looping ) yaitu titik 20, 4, 9, dan 11 yang ditandai dengan bulatan berwarna kuning.  Hal  itu  menyebabkan  pemborosan  infratruktur  pipa  dan menyebabkan susahnya mendeteksi kerusakan pipa.
b. Langkah – Langkah Pencarian Menggunakan Algoritma Kruskal
Pada  gambar  3  ini  memberikan  bobot  pada  tiap  garis  diantara  dua node. Tahap berikutnya memilih garis  dengan  bobot yang paling minimum. Mencari panjang pipa yang paling pendek diantara pipa-pipa yang lain. Dan ditemukan pipa berukuran 3 meter diantara titik 8 dan 10.

## Gambar 3. Langkah awal algoritma kruskal
Tahap  berikutnya  adalah  mencari  dan  tandai  pipa  yang  ukurannya pendek dan lebih besar dari pipa pertama. Dan ditemukan pipa berukuran 4 meter.  Pada  gambar  4  lakukan  cara  yang  sama  pada  langkah-langkah selanjutnya.
Gambar 4. Langkah kedua
Langkah 1 Langkah 2
Jurnal Sains Komputer & Informatika (J-SAKTI) Volume (2) No.2 September 2018, pp. 121 - 129 ISSN:2548-9771/EISSN:2549-7200 http://tunasbangsa.ac.id/ejurnal/index.php/jsakti
Gambar 5. Langkah keseluruhan dalam algoritma kruskal
Jurnal Sains Komputer & Informatika (J-SAKTI) Volume (2) No.2 September 2018, pp. 121 - 129 ISSN:2548-9771/EISSN:2549-7200 http://tunasbangsa.ac.id/ejurnal/index.php/jsakti
Pada  gambar  lima  adalah  pengurutan  garis  dari  yang  terkecil  hingga yang  terbesar  sampai  semua  node  terlewati  sehingga  membentuk  seperti pohon.  Pada  tahap  ini  dipilih  garis  dengan  bobot  yang  tidak  memiliki kemungkinan terjadi looping atau perulangan atau  perputaran seperti pada node 4,9,11,20. Pada gambar enam merupakan hasil dari algoritma kruskal. Pada  gambar  enam  sudah  tidak  ada  lagi  sisi  yang  menyebabkan kemungkinan  terjadinya looping atau  perulangan.  Ada  beberapa  sisi  yang dibuang. Sisi yang dibuang adalah sisi yang menghubungkan node 1-4, 4-12, 19-20,  21-6.  Dalam  hal  ini  merupakan  gambaran  jalur  pipa  dalam pendistribusian  air  bor  di  daerah  Jubung  menggunakan  algritma  kruskal, yang hasilnya panjang pipa semakin minimum menjadi 201,5 meter.
Gambar 6. peta denah pipa sumur bor setelah melalui perhitungan algoritma kruskal
Hasil  implementasi  pada  algoritma  kruskal  adalah  penggunaan  pipa sebelum  menggunakan  algoritma  kruskal  adalah  11.936.500,-  dan  setelah menggunakan  algoritma  kruskal  adalah  Rp.  7.535.500,-  sehingga  dapat menghemat  Rp.  4.401.000,-.    Biaya  ini  dihitung  dari  panjangnya  pipa  dan banyaknya jenis pipa yang digunakan. Ada tiga jenis pipa yaitu pipa panjang, pipa tee dan pipa elbow.
4.  SIMPULAN
Dalam penelitian ini dapat disimpulkan bahwa algoritma kruskal  dapat memberikan  solusi  yang  optimal  dalam  memecahkan  sebuah  masalah.  Hal tersebut  dapat  ditunjukkan  pada  panjang  pipa  yang  awalnya  340  meter
Langkah 14
Jurnal Sains Komputer & Informatika (J-SAKTI) Volume (2) No.2 September 2018, pp. 121 - 129 ISSN:2548-9771/EISSN:2549-7200 http://tunasbangsa.ac.id/ejurnal/index.php/jsakti
menjadi 201,5 meter dan  jumlah pipa dapat dihemat sebesar Rp. 4.401.000,-. Pada  penelitian  ini  tidak  diperhitungkan  jumlah  perbandingan  jumlah  sisi dan nodenya sehingga pada penelitian berikutnya dalam mengimplementasikan  algoritma  untuk  menentukan  rute  terpendek  dapat memperhatikan  perbandingan  jumlah  sisi  dan  node  atau  simpul  untuk memperoleh hasil yang lebih akurat.

## ACKNOWLEDMENT
Penelitian  ini  merupakan  hasil  keluaran  dari  mata  kuliah  sistem  operasi. Persembahan  rasa  terimakasih  saya  berikan  kepada  rekan  satu  tim pengampu mata kuliah sistem operasi dan mahasiswa mahasiswa saya yang telah  menempuh  mata  kuliah  ini,  terutama  Kharisma  Ahmad  P,  Alifatur Rigasari, Risky Meidina, Anugraha Praysti I selaku tim surveyor pada paper ini.

## DAFTAR PUSTAKA
[1]  Hayu  W.,  Yuliani,  Dan  Sam,  M.,  “Pembentukan  Pohon  Merentang Minimum Dengan Algoritma Kruskal”, Jurnal Scientific Pinisi, Volume 3, Nomor 2, , Hlm. 108-115, Oktober 2017
[2]  Lufira,  R.  D.,  Suhardjono,  S.,  Dan  Marsudi,    S.,  “Optimasi  Dan  Simulasi Sistem  Penyediaan  Jaringan  Air  Bersih  Di  Kecamatan  Kademangan Kabupaten Blitar”, Vol 3, No 1, Jurnal Pengairan, Http://Jurnalpengairan.Ub.Ac.Id, Universitas Brawijaya, Malang,  2012
[3]  Nelfiyanti,  Dan  Dermawan  D.,  “Penentuan  Rute  Distribusi  Bbm  Yang Optimal  Menggunakan  Metode  Minimal Spanning  Tree (Mst)  Dan Algoritma Heuristik Di Pt.Telkomsel Area Kabupaten Pelalawan, Jurnal Teknik Industri – Universitas Hung Hatta, Vol. 1, No. 1, Halaman 58-69, Issn : 2302-0318 ,  Juni 2012
[4]  Sam  M.,  Dan  Yuliani,    “Penerapan  Algoritma  Prim  Untuk  Membangun Pohon  Merentang  Minimum  (Minimum Spanning  Tree )  Dalam Pengoptimalan Jaringan Transmisi Nasional Provinsi Sulawesi Selatan. Jurnal  Dinamika”,  Vol.  07,  No.  1,  Halaman  50-61,  Issn  2087  –  7889, April, 2016
[5]  Wattimena  A.Z,  Dan  Lawalata  S.,  “  Aplikasi  Algoritma  Kruskal  Dalam Pengotimalan  Panjang  Pipa  Kruskal  Algorithm  Application  On Optimlaizing  Pipes  Network”,  Jurnal  Barekeng,  Vol.  7,  No.  2,  Hal.  13  – 18, 2013
[6]  Zakiah  N,  Desniarti,  Samosir  B.S.  2015.  Minimum Spanning  Tree Determination  Program  Using  Kruskal  Algorithm  On  Visual  Basic  6.0. International  Journal  Of  Science  And  Research  (Ijsr),.  Volume  4,  Issue 12, ISSN (Online): 2319-7064, December, 2015.