Jurnal Riset Rumpun Matematika dan Ilmu Pengetahuan Alam (JURRIMIPA) Vol.
No.
2 Oktober 2023 e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 284-292 DOI: https://doi.
org/10.
55606/jurrimipa.
Penerapan Algoritma Boruvka Pada Jaringan Listrik (Studi Kasus Pada Kelurahan Tanjung Pinggir Kecamatan Siantar Martob.
Novita Sari Saragih Universitas Negeri Medan Email: novita.
saragih@mhs.
Mulyono Universitas Negeri Medan Email: mulyono_mat@yahool.
Abstract.
This research was conducted in Tanjung Pinggir.
Siantar Martoba District to determine the optimization of electrical installations using the Boruvka algorithm to find a minimum spanning tree node with a minimum number of 3 consecutive nodes.
Edges that do not form a circuit.
Based on data obtained from PT.
PLN (Perser.
UP3 Pematangsiantar, then a picture of the installed network graph is obtained.
The results obtained for the electrical installation diagram were obtained by using Python and the 2,591 meter Boruvka algorithm to obtain a minimum spanning tree.
In this case, the electricity distribution cable is reduced by 41 meters compared to the previous total installation of 2,632 meters.
Keywords: Graph.
Boruvka Algorithm.
Python.
Minimum Spanning Tree.
Abstrak.
Penelitian ini dilakukan di Tanjung Pinggir Kecamatan Siantar Martoba untuk mengetahui optimalisasi instalasi listrik menggunakan algoritma Boruvka untuk mencari simpul pohon merentang minimal dengan jumlah minimal 3 simpul berturut-turut.
Tepi yang tidak membentuk sirkuit.
Berdasarkan data yang diperoleh dari PT.
PLN (Perser.
UP3 Pematangsiantar, kemudian didapatkan gambar graf jaringan yang Hasil yang diperoleh untuk diagram instalasi listrik diperoleh dengan menggunakan Python dan algoritma Boruvka 2.
591 meter untuk mendapatkan pohon merentang minimum.
Dalam hal ini, kabel distribusi listrik berkurang 41 meter dibandingkan total pemasangan sebelumnya sebanyak 2.
632 meter.
Kata kunci: Graf.
Algoritma Boruvka.
Python.
Minimum Spanning Tree.
LATAR BELAKANG
Teori Graf merupakan salah satu cabang matematika yang memiliki banyak manfaat selama ini.
Graf digunakan untuk merepresentasikan suatu objek dan hubungan antara objekobjek tersebut.
Representasi dapat menggunakan titik, bulatan atau noktah untuk merepresentasikan objek, sedangkan hubungan antar objek direpresentasikan dengan garis.
Masalah dapat dijelaskan lebih sederhana dengan merepresentasikannya secara graf.
Minimum Spanning Tree (MST) merupakan sebuah permasalahan graf yang sudah banyak diterapkan baik secara langsung maupun tidak langsung dalam kehidupan sehari-hari.
Masalah pohon merentang minimum hampir mirip dengan masalah jalur terpendek, yaitu menghubungkan semua simpul dalam jaringan sehingga diperoleh total panjang rute minimum (Efendi dkk.
, 2.
Received Juni 30, 2023.
Revised Juli 18, 2023.
Accepted Agustus 03, 2023 * Novita Sari Saragih, novita.
saragih@mhs.
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 284-292 Banyak struktur dapat diwakili oleh graf.
Saat ini graf dapat digunakan untuk mengoptimalkan jaringan listrik.
Jaringan listrik akan direpresentasikan dalam bentuk graf terhubung, tidak berarah, dan berbobot.
Maka dapat dipresentasikan tiang listrik sebagai simpul .
, sedangkan kabel listrik yang terpasang sebagai sisi .
Graf hasil representasi akan dianalisis dengan menerapkan Pohon Merentang (Spanning Tre.
Dalam mengelola daya dalam jumlah besar, efisiensi menyeluruh perlu dilakukan untuk memastikan ketersediaan setiap komponen yang dialokasikan.
Dalam pekerjaan pembangunan yang dianggap cukup andal dan berkualitas baik, tingkat harga yang lebih rendah dapat menjamin proses pengumpulan dan pendistribusian listrik ke kota-kota kecil dan daerah terpencil (Tania dkk.
, 2.
Dengan adanya energi listrik di setiap kehidupan manusia merupakan keharusan dalam roda kehidupan.
Menjadi ketergantungan akan ketersediaan energi listrik semakin meningkat, meninjau keberlangsungan berbagai macam kegiatan sehari-hari, contohnya mesin cuci, lampu, kipas, dll.
Tanjung pinggir adalah salah satu kelurahan di kecamatan Siantar Martoba Kota Pematangsiantar Provinsi Sumatera Utara.
Masalah distribusi jaringan listrik dialami oleh Kelurahan Tanjung Pinggir.
Berkaitan dengan semakin padat pemukiman sehingga memunculkan banyak bidang yang harus diminimumkan tanpa mengurangi fungsinya.
Ibaratnya kabel jaringan listrik yang akan dipasang harus optimal, dalam arti panjang kabel yang terpasang haruslah minimal dan dapat mengalirkan listrik ke seluruh pemukiman yang Pemasok listrik PLN yang menyuplai listrik ke kelurahan Tanjung Pinggir adalah PT.
PLN (Perser.
UP3 Pematangsiantar.
Seiring bertambahnya jumlah pemukiman rumah baru yang ada di Kelurahan Tanjung Pinggir, sehingga kebutuhan listrik yang akan di distribusikan semakin meningkat.
Akan tetapi berdasarkan pantauan distribusi tenaga listrik PT.
PLN
(Perser.
UP3 Pematangsiantar di kelurahan Tanjung Pinggir menunjukkan permasalahan bahwa panjang kabel distribusi listrik yang terpasang di setiap pemukiman rumah tidak efisien hingga melebihi 2.
500 meter.
Maka dengan demikian pihak PT.
PLN (Perser.
UP3 Pematangsiantar perlu memperhatikan, dan mengukur dengan tepat, agar tidak ada persediaan kabel listrik yang terbuang percuma, yang dapat mengakibatkan kabel tidak efisien dan pengeluaran dana yang besar.
PENERAPAN ALGORITMA BORUVKA PADA JARINGAN LISTRIK
(STUDI KASUS PADA KELURAHAN TANJUNG PINGGIR KECAMATAN SIANTAR MARTOBA)
Dalam permasalahan jaringan listrik, minimum spanning tree dapat digunakan untuk mendapatkan solusi pada suatu jaringan listrik yang membutuhkan biaya minimum dalam penggunaan kabel.
Pengerjaan manual dapat digunakan untuk menentukan minimum spanning tree akan tetapi membutuhkan waktu yang lama.
Maka, untuk menentukan minimum spanning tree pada penelitian, algoritma yang digunakan yaitu algoritma Modifikasi dari algoritma Prim dan algoritma Kruskal yang menggunakan konsep hamiltonian path (Afrianti dkk.
, 2.
Berdasarkan penelitian Dani Nur Afandi .
yang berjudul Penerapan Algoritma Boruvka Metode Contracted Graph Dalam Menentukan Minimum Spanning Tree, menyimpulkan bahwa Algoritma Boruvka metode Contracted Graph dapat menemukan solusi yang optimal pada jaringan pipa PDAM yang telah di analisis (Afandi, 2.
Penelitian yang sudah pernah dilakukan oleh Miftahul Khoiriah .
, perbandingan penyelesaian minimum spanning tree menggunakan empat algoritma yang setiap algoritma memiliki fase yang berbeda dalam menentukan pohon merentang minimum.
Kemungkinan terbesar untuk menentukan pohon merentang minimum dapat diperoleh pada algoritma Boruvka.
Tahap pertama algoritma Boruvka adalah menentukan hutan, dengan ketentuan tidak mempertimbangkan bobot sisi-sisi yang dipilih sebelum mendapatkan pohon merentang minimum (Khoiroh, 2.
Sehingga penulis sangat tertarik untuk melakukan penelitian terhadap algoritma Boruvka.
Penulis menggunakan bantuan bahasa pemrograman Python untuk menghindari kesalahan pada saat proses pemodelan yang dilakukan oleh human error.
Berdasarkan latar belakang yang telah diuraikan di atas, maka penulis tertarik untuk melakukan penelitian dengan judul AuPenerapan Algoritma Boruvka pada Jaringan Listrik (Studi Kasus pada Kelurahan Tanjung Pinggir Kecamatan Siantar Martob.
Ay.
KAJIAN TEORITIS
Teori graf berawal pada tahun 1736 ketika L.
Euler mempertimbangkan masalah jembatan Kynigsberg.
Euler menemukan jawaban atas pertanyaan dari pertanyaan ini dengan memodelkan pertanyaan sebagai graf.
Teori graf mempelajari konsep-konsep yang berkaitan dengan himpunan simpul dan himpunan sisi.
Graf biasa dilambangkan dengan adalah pasangan himpunan yang terdiri dari suatu himpunan tidak kosong dari elemen yang disebut dengan simpul .
dan himpunan pasangan tidak berurutan dari simpul (Riswan, 2.
JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
yang disebut sisi .
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 284-292 Sebuah graf berisikan dua buah himpunan yaitu himpunan berhingga tak kosong yang diperoleh dari objek-objek yang disebut simpul dan himpunan berhingga .
ungkin yang elemen-elemennya disebut sisi sedemikian sehingga setiap elemen dalam merupakan pasangan tak berurut dari simpul-simpul di dan himpunan disebut himpunan sisi Himpunan (Budayasa, 2.
Dari pengertian tersebut dapat diartikan bahwa tidak boleh kosong, sementara Maka, suatu graf bisa saja tidak mempunyai sisi satu buah pun, akan tetapi harus memiliki simpul, minimal satu.
Dan graf yang hanya memiliki satu simpul dan tidak memiliki sisi disebut graf trivial.
Graf dapat dikelompokkan dalam beberapa jenis:
Berdasarkan ada atau tidak ada sisi pada suatu graf.
Graf sederhana .
imple grap.
, graf yang tidak mengandung gelang maupun sisi ganda.
Graf tak sederhana .
nsimple grap.
, graf yang mengandung sisi ganda atau Beberapa istilah yang sering digunakan dalam graf, yaitu:
Bertetangga (Adjacen.
Dua simpul dan dalam graf dikatakan bertetangga (Adjacen.
bila dan keduanya terhubung langsung dengan sebuah sisi.
Dengan kata lain adalah sebuah sisi pada graf.
Bersisian .
Untuk sembarang sisi , sisi dikatakan bersisian dengan simpul dan simpul .
Gelang .
Loop adalah sisi yang menghubungkan sebuah simpul yang sama.
Siklus (Cycl.
Siklus atau sirkuit adalah lintasan yang diawali dan diakhiri pada simpul yang Terhubung (Connecte.
Simpul dan simpul dikatakan terhubung jika terdapat lintasan dari Jika terdapat lintasan berarah dari dan lintasan berarah dari ke , maka kedua simpul tersebut dikatakan terhubung kuat .
trongly connecte.
Dan apabila hanya terdapat lintasan berarah dari saja disebut terhubung lemah .
eakly PENERAPAN ALGORITMA BORUVKA PADA JARINGAN LISTRIK
(STUDI KASUS PADA KELURAHAN TANJUNG PINGGIR KECAMATAN SIANTAR MARTOBA)
Subgraf dan Komplemen Subgraf Misalkan adalah graf adalah sebuah graf.
adalah subgraf dari Sedangkan komplemen dari subgraf sedemikian sehingga simpul yang anggota-anggota terhadap graf adalah himpunan bersisian dengannya.
Graf berbobot (Weighted Grap.
Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga .
Pohon adalah graf tak berarah terhubung yang tidak memiliki sirkuit.
Dengan kata lain, adalah pohon, maka tidak boleh berupa himpunan kosong namun Pohon merentang .
panning tre.
adalah subgraf yang memuat semua simpul .
dan berbentuk pohon.
Dengan kata lain, sebuah pohon merentang adalah subgraf yang memuat semua simpul-simpul dan sisi-sisi yang terhubung sehingga membentuk suatu pohon dan mencakup semua simpul dalam graf asli.
Jika adalah graf berbobot, maka jumlah bobot semua sisi di adalah bobot perentang Setiap bobot yang berbeda, pohon perentangnya berbeda juga.
Pohon merentang minimum .
inimum spanning tre.
dikatakan demikian apabila pohon merentangnya berbobot Algoritma Boruvka adalah salah satu algoritma minimum spanning tree (MST) yang digunakan untuk mencari solusi MST dalam graf tak berarah.
Algoritma ini pertama kali ditemukan oleh Otakar Boruvka pada tahun 1926.
Algoritma Boruvka menggunakan pendekatan iteratif untuk mencari MST dalam graf.
Algoritma ini memulai dengan membuat setiap simpul sebagai komponen terpisah dan memperbarui komponen dengan memilih busur terpendek dalam setiap komponen.
Proses ini dilakukan berulang hingga hanya terdapat satu komponen yang mencakup seluruh simpul dalam graf.
JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 284-292
METODE PENELITIAN
Jenis penelitian ini adalah studi kasus.
Data yang digunakan adalah data jaringan distribusi listrik yang diperoleh dari Kelurahan Tanjung Pinggir dengan mengambil data jarak antara rumah dengan tiang listrik untuk mengetahui panjang kabel listrik yang dibutuhkan dalam distribusi listrik.
Prosedur yang dilakukan dalam melakukan penelitian ini adalah sebagai berikut:
Melakukan studi literatur teori dasar graf yang mendukung pembahasan.
Mengambil data yang merupakan peta jaringan distribusi listrik yang telah terpasang di Kelurahan Tanjung Pinggir dari PT.
PLN (Perser.
UP3 Pematangsiantar.
Mengubah data yang awalnya berbentuk peta menjadi data dalam bentuk graf terhubung berbobot.
Mengidentifikasi data.
Yang menjadi bobot adalah panjang kabel listrik.
Panjang kabel listrik sebagai sisi.
Rumah sebagai simpul.
Mengolah data yang telah diubah untuk menentukan minimum spanning tree dengan Algoritma Boruvka.
Menggunakan bahasa pemrograman Python untuk memeriksa minimum spanning Menarik kesimpulan.
HASIL DAN PEMBAHASAN
Penelitian ini dilakukan di Kecamatan Siantar Martoba yang berlokasi di Kelurahan Tanjung Pinggir dan waktu yang dibutuhkan untuk penelitian kurang lebih selama dua bulan.
Penelitian ini menggunakan data yang diperoleh dari PT.
PLN (Perser.
UP3 Pematangsiantar.
Data tersebut mencakup informasi mengenai jalur kabel distribusi listik di Kelurahan Tanjung Pinggir, yang merupakan salah satu Kelurahan yang terletak di Kecamatan Siantar Martoba.
Jaringan distribusi listrik yang digunakan di Kelurahan Tanjung Pinggir adalah jaringan distribusi primer dengan pola radial, karena menggunakan Saluran Udara Tegangan Menengah (STUM) yang merupakan pola umum digunakan di daerah Kelurahan Tanjung Pinggir.
PENERAPAN ALGORITMA BORUVKA PADA JARINGAN LISTRIK
(STUDI KASUS PADA KELURAHAN TANJUNG PINGGIR KECAMATAN SIANTAR MARTOBA)
Dari data yang diperoleh, rumah diidentifikasi sebagai simpul.
Panjang kabel listrik sebagai sisi, dan bobot dalam satuan meter.
Jumlah total Panjang kabel listrik yang dipasang di Kelurahan Tanjung Pinggir adalah sepanjang 2.
632 meter, yang terdiri dari 190 simpul dan 191 sisi.
Langkah -langkah untuk menentukan Minimum Spanning Tree dari data distribusi listrik di Kelurahan Tanjung Pinggir menggunakan Python melaluai Google Colab:
Buka Google Colab .
ttps://colab.
Buat notebook baru dengan mengklik tombol " Notebook" atau "File" > "New NotebookAy.
Input coding yang dapat digunakan untuk menentukan Minimum Spanning Tree.
Input data distribusi jaringan listrik.
Klik ikun run untuk menjalankan program.
JURRIMIPA - VOLUME.
NO.
OKTOBER 2023
e-ISSN: 2828-9390.
p-ISSN: 2828-9382.
Hal 284-292 Selanjutnya program akan menampilkan out put Minimum Spanning Tree.
Berdasarkan perhitungan manual Minimum Spanning Tree pada graf distribusi listrik menggunakan algoritma Boruvka, di peroleh 189 jalur, 190 simpul dan Panjang kabel 2.
Maka penggunaan kabel listrik lebih hemat 41 meter.
Sebelum dioptimalkan panjang kabel yang digunakan 2.
632 meter, 191 jalur, dan190 simpul.
Penggunaan Python untuk menentukan Minimum Spanning Tree menghasilkan Minimum Spanning Tree dengan jumlah jalur yang sama dengan jumlah jalur yang diperoleh dari penghitungan manual.
KESIMPULAN
Berdasarkan hasil penelitian dan pembahasan mengenai penerapan Algoritma Boruvka pada jaringan listrik dalam menentukan Minimum Spanning Tree pada Kelurahan Tanjung Pinggir Kecamatan Siantar Martoba, maka dapat diambil kesimpulan:
Sebelum dilakukan pengolahan data terdapat 191 jalur, 190 simpul dan panjang kabel 632 meter.
Setelah dilakukan penerapan Algoritma Boruvka untuk menentukan Minimum Spanning Tree menghasilkan 189 jalur, 190 simpul dan Panjang kabel 2.
Maka penggunaan kabel listrik lebih hemat 41 meter.
Untuk penghitungan Minimum Spanning Tree dengan Algoritma Boruvka dan Python melalui Google Colab dapat menentukan jarak paling minimum pada pendistribusian listrik di Kelurahan Tanjung Pinggir Kecamatan Siantar Martoba.
PENERAPAN ALGORITMA BORUVKA PADA JARINGAN LISTRIK
(STUDI KASUS PADA KELURAHAN TANJUNG PINGGIR KECAMATAN SIANTAR MARTOBA)
DAFTAR REFERENSI
Afandi.
Penerapan Algoritma Boruvka Metode Contracted Graph Dalam Menentukan Minimum Spanning Tree(Studi Kasus: PDAM Gunungkidul wilayah Wiladeg dan Tunggu.
Afrianti.
Effendi, & Welyyanti.
Menentukan Minimum Spanning Tree Menggunakan Algoritma Modifikasi Dari Algoritma Prim Dan Kruskal Dalam Perencanaan Rute Wisata Yang Efisien.
Jurnal Sains dan Matematika Unpam, 3.
, 103Ae110.
Budayasa.
, .
Teori Graf dan Aplikasinya.
Unesa Universitas Press.
Surabaya.
Diestel.
Graph Theory.
Dalam Springer.
Springer.
Efendi.
Susilo.
, & Prasetyo.
Perbandingan Algoritma Boruvka Dan Algoritma Sollin Pada Optimasi Kebutuhan Kabel Fiber Optik Universitas Bengkulu.
Journal Scientific and Applied Informatics, 4.
, 175Ae181.
Khoiroh.
Keefektifan penggunaan algoritma boruvka, algoritma prim, algoritma kruskal, dan algoritma sollin dalam menentukan pohon merentang minimum.
Mulki.
Suhaedi.
, & Permanasari.
Optimasi Jaringan Distribusi Listrik dengan Pohon Rentang Minimum Menggunakan Bahasa Pemrograman Python.
Bandung Conference Series:
Mathematics, 2.
Munir.
Matematika Diskrit.
Dalam Informatika Bandung .
Informatika Bandung.
Rahayuningsih.
Teori Graph dan Penerapannya.
Riswan.
Penentuan Jarak Minimum dalam Suatu Jaringan Listrik dengan Algoritma Prim dan QM for Windows (Studi Kasus Pada Perumahan Nelayan di Kota Palop.
Al-Khwarizmi:
Jurnal Pendidikan Matematika dan Ilmu Pengetahuan Alam, 6.
, 77Ae88.
https://doi.
org/10.
24256/jpmipa.
Tania.
Firza.
, & Cahyadi.
Penerapan Minimum Spanning Tree Pada Pengoptimalan Jaringan Listrik Di Perumahan Depok Indah I.
Bulletin of Applied Industrial Engineering Theory, 2.
VanderPlas.
Python Data Science Handbook.
Wibison.
Matematika Diskrit .
Graha Ilmu JURRIMIPA - VOLUME.
NO.
OKTOBER 2023