PENENTUAN POHON RENTANG MINIMUM BERDASARKAN KONDISI GEOGRAFIS SUATU WILAYAH DENGAN ALGORITMA PRIM STUDI KASUS: JARINGAN LISTRIK DISTRIBUSI PRIMER KOTA SAMARINDA

Hadiyanto, Ir. A. Rida Ismu Windyarto

2011 | Tesis | S2 Teknik Elektro

Penentuan pohon rentang minimum banyak digunakan untuk menyelesaikan permasalahan optimasi yaitu permasalahan yang menuntut pencarian solusi minimum. Dalam jaringan distribusi listrik, minimum spanning tree (MST) digunakan untuk mencari panjang minimum kabel agar sistem jaringan listrik menjadi lebih optimal. Bobot minimum suatu MST jaringan listrik distribusi primer sangat dipengaruhi oleh kondisi geografis suatu wilayah berupa data kontur. Data kontur merupakan data spasial yang mengandung informasi ketinggian permukaan bumi suatu wilayah. Untuk menentukan MST jaringan listrik distribusi primer diperlukan suatu algoritma yang mampu menghasilkan solusi optimal. Dalam penelitian ini algoritma yang digunakan adalah algoritma prim. Algoritma prim merupakan sebuah algoritma dalam teori graf untuk mencari MST dari sebuah graf berbobot dengan menitikberatkan pada pemilihan bobot minimum berdasarkan simpul yang diambil. Penelitian ini dilakukan dengan cara merancang model graf jaringan listrik distribusi primer sesuai dengan data yang diperoleh. Dalam mencari bobot minimum untuk tiap-tiap sisi graf jaringan harus memasukkan parameter elevasi, tinggi titik/simpul, serta jarak antar titik/simpul. Selanjutnya dari graf tersebut dilakukan perhitungan dan simulasi oleh komputer untuk mendapatkan MST jaringan listrik distribusi primer menggunakan algoritma prim dengan bantuan program ArcView GIS 3.3 melalui script avenue. Algoritma prim termasuk dalam kategori algoritma yang baik atau efisien, karena kompleksitas waktunya berbentuk polinomial dalam n, dengan n adalah ukuran jumlah simpul atau sisi. Berdasarkan hasil pengujian terlihat bahwa algoritma prim memiliki kemampuan dalam menentukan MST jaringan listrik distribusi primer yang jauh lebih baik jika didasarkan pada kondisi geografis suatu wilayah. Selain itu grafik waktu komputasi algoritma prim dalam menghasilkan MST dengan berdasarkan data kontur maupun yang tidak berdasarkan data kontur bersifat kuadratik.

Determination of the minimum spanning tree are widely used to solve optimization problems of finding solutions to problems that require minmum. In the electricity distribution network, minimum spanning tree (MST) is used to find the minimum length of cable for electricity network system becomes more optimal. Minimum weight of a MST primary distribution power network is strongly influenced by the geographical conditions of a region in the form of contour data. Contour data is spatial data that contains information of the earth surface elevation of an area. To determine the primary distribution grid MST needed an algorithm that can produce optimal solutions. In this research the algorithm used is algorithm Prim. Prim's algorithm is an algorithm in graph theory to find the MST of a weighted graph with emphasis on the selection of minimum weight based on the node is taken. This research was done by designing a model of primary distribution power network graph in accordance with the data obtained. In finding the minimum weight for each side of the network graph should include parameters elevation, high point / node, and the distance between points / nodes. Furthermore, the graph is done by computer calculation and simulation to get the electricity distribution network primary MST using Prim's algorithm with the help of ArcView GIS 3.3 program through the avenue script. Prim's algorithm included in the category of good or efficient algorithms, because the shape of polynomial time complexity in n, where n is a measure of the number of vertices or sides. Based on the test results have shown that the algorithm Prim MST ability to determine the primary distribution grid is much better if based on the geographical conditions of a region. In addition, Prim's algorithm graph computation time in generating the MST based on the data that is not based on the contour and contour data are quadratic.

Kata Kunci : pohon rentang minimum, algoritma prim, kontur, kompleksitas waktu.