PENERAPAN ALGORITMA SUCCESSIVE SHORTEST PATH DAN ALGORITMA CAPACITY SCALING DALAM PENYELESAIAN MINIMUM COST FLOW PROBLEM

Abstract

Network flow adalah sebuah graf berarah yang tiap sisinya memiliki kapasitas atau bobot dan pada sisi tersebut terdapat arus (flow) yang mengalir antara dua simpul yang mengapit sisi tersebut. Minimum cost flow problem merupakan model permasalahan pencarian biaya minimum yang digunakan untuk mendistribusikan suatu barang dari produsen menuju ke konsumen dalam suatu aliran jaringan. Minimum cost flow problem adalah masalah penentuan arus distribusi agar biaya yang dikeluarkan minimum. Penelitian ini menggunakan data primer dari PT. Amita Bara Sejahter Jember. Data tersebut terdiri dari 50 simpul dan 54 sisi. Simpul 1 merupakan Depo dan merupakan source (simpul awal), sedangkan simpul 2 sampai simpul 50 merupakan sink (simpul tujuan), dan sisi diasumsikan sebagai jalan dengan bobot sisi sebagai biaya distribusi dan kapasitas maksimum pengiriman. Jumlah aliran tidak oleh melebihi kapasitas maksimum pengirimannya. Hasil penelitian berupa rute, total biaya minimum, dan running time program. Penerapan algoritma successive shortest path dan algoritma capacity scaling pada data pendistribusian gas LPG 3 Kg PT. Amita Bara Sejahtera Jember menghasilkan total biaya minimum algoritma successive shortest path sebesar Rp 326.206,-, dan total biaya minimum algoritma capacity scaling sebesar Rp 326.525,-. Total biaya minimum yang dihasilkan algoritma successive shortest path relatif lebih kecil dari pada algoritma capacity scaling sehingga dapat dikatakan bahwa algoritma successive shortest path lebih baik dari pada algoritma capacity scaling. Sedangkan, jika dilihat dari running time yang diperoleh, capacity scaling lebih baik daripada algoritma successive shortest path.