PENERAPAN ALGORITMA CLONING-BASED DAN ALGORITMA EDMONDS-KARP DALAM PENYELESAIAN MAXIMUM FLOW PROBLEM

Abstract

Network Flow adalah sebuah graf berarah yang tiap sisinya memiliki kapasitas dan terdapat arus yang mengalir antara dua simpul yang mengapit sisi tersebut. Salah satu aplikasi network flow adalah maximum flow. Maximum flow merupakan sebuah model yang dapat digunakan untuk mengetahui nilai maximum seluruh arus didalam sebuah sistem jaringan. Maximum flow memiliki tujuan untuk memaksimalkan jumlah aliran yang mengalir pada sebuah network yang hanya memiliki satu source (sumber) dan satu sink (tujuan). Penelitian ini menggunakan data sekunder berupa data jaringan distribusi listrik wilayah distribusi kebasen 11 kota Tegal. Jaringan tersebut terdiri dari 46 simpul dan 64 sisi. Simpul 1 merupakan gardu induk dan merupakan source (simpul awal), sedangkan simpul 2 sampai simpul 46 diasumsikan sebagai tiang listrik yang menghubungkan kabel satu dengan yang lain, dan sisi diasumsikan sebagai kabel yang menghubungkan antar tiang listrik. Simpul 46 merupakan sink (simpul tujuan). Serta terdapat kapasitas masing-masing kabel yang digunakan untuk membatasi jumlah aliran yang melewati kabel tersebut. Jumlah aliran tidak boleh melebihi kapasitasnya. Hasil penelitian ini berupa maximum flow, running time, dan lintasan maximum flow. Penerapan algoritma cloning based dan algoritma edmonds karp pada data jaringan distribusi listrik wilayah distribusi kebasen 11 kota Tegal dengan melakukan sepuluh kali percobaan, maximum flow yang dihasilkan algoritma edmonds karp lebih besar dari pada algoritma cloning based. Karena pada algoritma cloning based tidak ada aturan untuk memulai lintasan awal. Sedangkan pada algoritma edmonds karp lintasan awal merupakan lintasan terpendek. viii Sehingga dapat dikatakan bahwa algoritma edmonds karp lebih baik dari pada algoritma cloning based. Sedangkan running time yang diperoleh algoritma cloning based lebih kecil daripada algoritma edmonds karp. Jika dilihat dari running time yang diperoleh, algoritma cloning based lebih baik daripada algoritma edmonds karp