Optimasi Aliran Pengunjung pada Jaringan Labirin Menggunakan Pendekatan Maximum Flow: Studi Komparatif Algoritma Ford-Fulkerson, MFPC-Greedy, dan Hochbaum Pseudoflow

ALYA AQILA M. Optimasi Aliran Pengunjung pada Jaringan Labirin Menggunakan Pendekatan Maximum Flow: Studi Komparatif Algoritma Ford-Fulkerson, MFPC-Greedy, dan Hochbaum Pseudoflow (dibimbing oleh Prof. Agustinus Ribal, S.Si., M.Sc.. PhD). Latar Belakang. Masalah aliran maksimum pengunjung merupakan salah satu permasalahan yang menggabungkan optimasi dan teori graf yang direpresentasikan dalam jaringan labirin. Kapasitas sisi dari suatu jaringan labirin dihitung menggunakan model persamaan yang didasarkan pada konsep aliran pejalan kaki. Aliran maksimum digunakan untuk menentukan jumlah maksimum aliran yang dapat dikirim dari titik sumber ke titik tujuan. Masalah ini akan diselesaikan dengan algoritma Ford-Fulkerson, MFPC-Greedy, dan Hochbaum Pseudoflow. Tujuan. Penelitian ini bertujuan memberikan pemodelan struktur labirin ke dalam jaringan untuk menerapkan, membandingkan, dan mengevaluasi performa dari ketiga algoritma dalam menyelesaikan masalah aliran maksimum. Metode. Penelitian ini dibagi ke dalam 5 tahapan, yakni (1) Memodelkan struktur labirin menjadi jaringan aliran yang terdiri atas 25 titik dan 29 titik; (2) Menetapkan parameter dan menghitung kapasitas pada setiap sisi jaringan; (3) Menerapkan ketiga algoritma pada dua model jaringan labirin; (4) Membandingkan dan mengevaluasi performa ketiga algoritma; (5) Menyimpulkan hasil perbadingan yang diperoleh. Hasil. Algoritma Ford-Fulkerson memberikan hasil yang akurat tetapi membutuhkan lebih banyak iterasi terutama pada jaringan yang mempunyai lebih banyak titik, kemudian algoritma MFPC-Greedy memberikan jumlah iterasi yang lebih sedikit namun solusi yang dihasilkan tidak menjamin nilai optimal, dan Hochbaum Pseudoflow menunjukkan performa iterasi yang lebih stabil sekaligus memberikan hasil yang akurat. Kesimpulan. Berdasarkan hasil penelitian, algoritma Hochbaum Pseudoflow menunjukkan performa terbaik dan stabil dalam menyelesaikan masalah aliran maksimum pengunjung pada kedua jaringan labirin yang diuji, baik dari segi nilai aliran maksimum yang diperoleh, jumlah iterasi, dan kompleksitas penyelesaian dibandingkan dengan algoritma Ford-Fulkerson dan MFPC-Greedy.