PENENTUAN ALIRAN MAKSIMUM PADA JARINGAN PENDISTRIBUSIAN GAS MENGGUNAKAN ALGORITMA EDMONDS KARP - Tantri, Eliana; Helmi, Helmi; Yudhi, Yudhi (BIMASTER : Buletin Ilmiah Matematika, Statistika dan Terapannya, 2025)
PT. Livina Aurora Cemerlang merupakan perusahaan gas elpiji yang mendistribusikan gas non-subsidi ke beberapa pangkalan. Perusahaan melakukan pendistribusian gas dengan jumlah permintaan pengiriman yang berbeda-beda untuk setiap pangkalan, keterbatasan kapasitas kendaraan dan lokasi pangkalan yang tersebar dengan jarak lumayan jauh dari satu pangkalan ke pangkalan lain. Sehingga perusahaan memerlukan strategi agar pendistribusian dapat dilakukan secara efisien dengan mengetahui nilai aliran maksimum. Permasalahan yang akan dibahas pada penelitian ini yaitu masalah jaringan pendistribusian gas yang direpresentasikan dengan graf berarah, dengan setiap busurnya mempunyai bobot. Oleh karena itu, tujuan dari penelitian ini menentukan aliran maksimum pada jaringan pendistribusian gas elpiji dengan mempertimbangkan kendala kapasitas setiap busur, kendala aliran di simpul sumber dan simpul tujuan menggunakan Algoritma Edmonds Karp pada jaringan pendistribusian gas elpiji dimana pencarian lintasan penambahnya menggunakan Algoritma Breadth First Search (BFS). Tahap-tahap dalam pencarian aliran maksimum yaitu membuat jaringan pendistribusian ke bentuk graf berarah, tahap kedua memulai dengan menetapkan nilai aliran awal menjadi 0 di semua busur. Tahap ketiga mengidentifikasi lintasan penambah yaitu jalur berarah yang menghubungkan simpul awal dan simpul tujuan menggunakan Algoritma BFS, tahap keempat menentukan kapasitas sisa minimum busur pada lintasan penambah yang diperoleh, kapasitas sisa minimum digunakan untuk mengoptimalkan aliran pada lintasan penambah. Proses ini dilakukan hingga tidak ditemukan lagi lintasan penambah dan diperoleh nilai aliran maksimum pada jaringan pendistribusian gas. Hasil pencarian aliran maksimum menggunakan Algoritma Edmonds Karp pada jaringan pendistribusian gas elpiji 5,5 Kg diperoleh 61 tabung gas sedangkan pada jaringan pendistribusian gas elpiji 12 Kg diperoleh 53 tabung gas dengan 5 lintasan penambah.