Perbandingan Algoritma Kruskal dan Sollin dalam Mengoptimalkan Rute Distribusi Beras Perum Bulog Cabang Jember

Abstract

Ketersediaan beras sebagai komoditas pangan utama sangat penting untuk memenuhi kebutuhan konsumsi harian masyarakat. Perum Bulog Cabang Jember sebagai salah satu produsen beras menghadapi tantangan dalam perencanaan rute distribusi beras ke berbagai daerah di Jember. Oleh karena itu, perlu dilakukan optimasi rute distribusi untuk meminimalkan jarak tempuh. Salah satu model matematika untuk mengoptimalkan rute distribusi adalah minimum spanning tree (MST). Penelitian ini menggunakan model MST untuk mengoptimalkan rute distribusi beras dengan menerapkan algoritma Kruskal dan Sollin. Algoritma Kruskal menyusun edges berdasarkan bobot dan menghubungkan titik tanpa membentuk siklus, sementara algoritma Sollin menghapus sisi-sisi graf yang tidak membuat graf terputus. Dalam penelitian ini akan dicari rute optimal pada pendistribusian beras Perum Bulog Cabang Jember. Permasalahan dalam penelitian ini yaitu mencari minimum spanning tree untuk distribusi beras agar menempuh jarak seminimal mungkin dengan menggunakan algoritma Kruskal dan Sollin. Terdapat 30 titik distribusi dan 42 sisi. Diasumsikan jalan penghubung antar lokasi distribusi sebagai sisi/bobot yang berupa jarak (km). Data yang telah diperoleh dibentuk menjadi graf terhubung dan diselesaikan menggunakan algoritma Kruskal dan Sollin. Penyelesaian permasalahan ini dilakukan dengan menggunakan Python. Hasil penerapan MST menggunakan algoritma Kruskal dan Sollin menunjukkan bahwa kedua algoritma menghasilkan panjang total MST yang sama, yaitu 53,31 km dengan 30 titik dan 29 sisi. Perbedaannya terletak pada waktu komputasi, algoritma Sollin lebih cepat dibandingkan algoritma Kruskal dengan selisih waktu 0,0377 detik. Penyelesaian MST ini memberikan solusi optimal dalam meminimalkan panjang total jalur yang menghubungkan semua titik dalam jaringan distribusi, tetapi hanya berfokus pada minimisasi jarak antara titik-titik tersebut tanpa mempertimbangkan faktor lain seperti rute kembali dan tanpa adanya pembagian area yang memungkinkan distribusi dapat dikirimkan dalam beberapa tahap. Namun, ketika diterapkan pada masalah riil, pemilihan rute tidak hanya mengutamakan jarak minimum antara titik-titik distribusi, tetapi juga memperhitungkan rute kembali. Berdasarkan model graf yang diperoleh, pemilihan rute optimal pada terapan permasalahan riil dilakukan dengan membagi pengiriman menjadi 2 subgraf. Pengiriman subgraf pertama terdiri dari 24 titik dan 24 sisi dengan jarak tempuh sebesar 49,76 km. Pengiriman subgraf kedua terdiri dari 7 titik dan 7 sisi dengan jarak tempuh sebesar 18,28 km. Dengan pembagian rute ini, jarak tempuh total yang dihasilkan yaitu 68,04 km.