Pemodelan Graf Berbobot untuk Penentuan Prioritas Jarak dan Estimasi Waktu Distribusi MBG dari SPPG ke Sekolah Mitra di Medan Tuntungan Menggunakan Algoritma Dijkstra

Evelyn Silalahi; Alvin  Hafiz; Suvriadi  Panggabean

doi:10.29303/griya.v6i2.1232

Evelyn Silalahi Universitas Negeri Medan
Alvin Hafiz
Suvriadi Panggabean

DOI: https://doi.org/10.29303/griya.v6i2.1232

Keywords: algoritma dijkstra, graf berbobot, distribusi logistik, makan bergizi gratis, openstreetmap

Abstract

Program Makan Bergizi Gratis (MBG) membutuhkan sistem distribusi yang tepat waktu dan efisien dari Satuan Pelayanan Pemenuhan Gizi (SPPG) ke sekolah-sekolah mitra guna menjaga kualitas dan kehangatan makanan. Penelitian ini bertujuan untuk memodelkan graf berbobot dalam menentukan prioritas jarak dan mengestimasi waktu distribusi MBG dari SPPG Simpang Selayang ke 10 sekolah dasar di Kecamatan Medan Tuntungan. Metode kuantitatif diterapkan dengan mengimplementasikan Algoritma Dijkstra pada jaringan jalan nyata berbasis OpenStreetMap (OSM). Data koordinat lokasi dikumpulkan melalui web scraping dan divalidasi menggunakan bounding box administratif. Untuk memberikan gambaran operasional yang lebih realistis, analisis sensitivitas dilakukan pada tiga skenario kecepatan rata-rata, yaitu 20, 30, dan 40 km/jam. Hasil komputasi menunjukkan bahwa SD NEGERI 065012 menjadi prioritas distribusi pertama dengan jarak rute terpendek (1,219 km), sedangkan SD N 060972 berada pada prioritas terakhir (5,763 km). Pada skenario kecepatan moderat (30 km/jam), rata-rata waktu tempuh distribusi ke seluruh sekolah adalah 6,4 menit. Penelitian ini menyimpulkan bahwa penerapan Algoritma Dijkstra berbasis jaringan jalan OSM terbukti lebih efektif dan realistis dalam mengoptimalkan rute distribusi dibandingkan perhitungan jarak garis lurus (Haversine), sehingga dapat menjadi acuan pengambilan keputusan logistik yang efisien bagi pengelola program MBG.

References

Amin, A., & Hendrik, B. (2025). Analisis Penerapan Algoritma Dijkstra dalam Optimasi Penentuan Rute: Sebuah Kajian Literatur Sistematis. Journal of Education Research, 6(1), 100–106.

Ariyani, H. D., Nafillah, K., Nindita, K., Ngatmin, & Rahayu, S. T. (2026). Pemodelan Graf Berarah Berbobot untuk Optimasi Penentuan Rute Terpendek Antar Kampus Polimarin Berbasis Algoritma Dijkstra. Euler : Jurnal Ilmiah Matematika, Sains Dan Teknologi, 14(1), 151–162.

Aziizah, D. U., Widzayanto, L. A., Muarifudin, & Ripan. (2026). Optimalisasi Rantai Pasok Pangan Lokal dalam Program Makan Bergizi Gratis (MBG): Studi Kasus Integrasi UMKM dan Satuan Pelayanan Pemenuhan Gizi (SPPG) di Kab. Kendal. Takuana: Jurnal Pendidikan, Sains, Dan Humaniora, 5(1), 240–254. https://doi.org/10.56113/takuana.v5i1.475

Baidawi, T., Kuswara, H., Wahyudi, E., & Haryanto. (2025). Optimasi Rute Distribusi Logistik Menggunakan Algoritma Genetika Berbasis Google Maps Api Untuk Efisiensi Biaya Operasional. Conten : Computer and Network Technology, 5(2), 57–65.

Cahya, M. D., Hatmoko, B. D., & Agus, I. (2026). Penentuan Rute Terpendek Pengiriman Barang pada PT AMSA menggunakan Algoritma Dijkstra. Merkurius : Jurnal Riset Sistem Informasi Dan Teknik Informatika, 4(3), 116–127.

Hakim, R. R. Al, Satria, M. H., Arief, Y. Z., Pangestu, A., Jaenul, A., Hertin, R. D., & Nugraha, D. (2022). Aplikasi Algoritma Dijkstra dalam Penyelesaian Berbagai Masalah. Expert: Jurnal Manajemen Sistem Informasi Dan Teknologi, 8(1), 42–47.

Herdiana, D. (2025). Implementasi Kebijakan Makan Bergizi Gratis ( MBG ): Faktor-faktor Pendorong dan Penghambat. Madani : Jurnal Ilmiah Multidisipline, 3(2), 470–478.

Jaiman, F., Fallo, D. Y. A., & Banung, F. L. (2025). Analisis Pemahaman Mahasiswa Informatika dalam Menyelesaikan Rute Terpendek Menggunakan Algoritma Dijkstra dengan Graf Berbobot. Jurnal Kridatama Sains Dan Teknologi, 7(01), 508–518.

Kaylla, M. R., Aulis, H. S., Salsabila, Z. Z., & Rohimi, I. A. (2026). Distribusi Pasokan Bahan Pangan Pada Program Makan Bergizi Gratis (MBG) Daerah Sarijadi. Sinergi : Jurnal Ilmiah Multidisiplin, 2(2), 1570–1584.

Maulana, M. D., Hendra, A., Joefrie, Y. Y., Anshori, Y., & Lamasitudju, C. A. (2024). Penerapan Algoritma Dijkstra Untuk Menentukan Rute Terpendek Dalam Distribusi Darah Di Palang Merah Indonesia Kota Palu Berbasis Mobile. The Indonesian Journal of Computer Science (IJCS), 13(6), 10098–10110.

Nasir, R., Baso, B. T., R.S, A., Amrillah, R., & Plaikari, R. P. (2026). Implementasi Kebijakan Program Makan Bergizi Gratis (MBG) di Sekolah: Analisis Tata Kelola, Akuntabilitas, dan Koordinasi Aktor. JIIP (Jurnal Ilmiah Ilmu Pendidikan), 9(2), 2548–2553.

Nissa, A., Candra, M., Humairoh, T., & Gusyuliandari, S. (2025). Kebijakan Makanan Bergizi Gratis : Analisis Ekonomi Politik dan Dampaknya terhadap Kesejahteraan Masyarakat Studi Kasus : SMP Negeri 4 Tanjungpinang. Socius: Jurnal Penelitian Ilmu-Ilmu Sosial, 2(11), 33–37.

Oetomo, D. S., Ramdhani, R. F., & Abdi, A. P. (2022). Penentuan rute pengiriman produk dengan meminimalkan biaya transportasi menggunakan metode saving matrik dan nearest neighbour di PT. Aisyah Berkah Utama. Jurnal Sains Dan Teknologi Keilmuan Dan Aplikasi Teknologi Industri, 22(1), 130–145.

Oktaviani, P., Dalnis, I. P., & Wirdianto, E. (2025). Usulan Rute Pendistribusian Gas LPG Menggunakan Algoritma Dijkstra dan Algoritma Genetika Pada Model CGVRP. Jurnal Rekayasa Sistem Industri, 14(1), 131–145.

Qomarrullah, R., Suratni, S, L. W., & Sawir, M. (2025). Dampak Jangka Panjang Program Makan Bergizi Gratis Terhadap Kesehatan Dan Keberlanjutan Pendidikan. Indonesian Journal of Intellectual Publication (IJI PUblication), 5(2), 130–137.

Rahmah, H. A., Anggraini, A., Nilasari, Y. P., & Salsabilla, E. P. (2025). Analisis Efektivitas Program Makan Bergizi Gratis Di Sekolah Dasar Indonesia Tahun 2025. Integrative Perspectives of Social and Science Journal (IPSSJ), 2(2), 2855–2866.

Reza, I. F. (2025). Urgensi Penjaminan Mutu Dalam Pelaksanaan Program Makan Bergizi Gratis. Jurnal Analisis Kebijakan, 9(2), 67–72.

Rufus, E. C., Riyadi, R. R., Hasibuan, D. N., Christian, E., & Pranatawijaya, V. H. (2024). Penerapan Algoritma Dijkstra Dalam Menentukan Rute Terpendek Untuk Jasa Pengiriman Barang Di Palangka Raya. JATI (Jurnal Mahasiswa Teknik Informatika), 8(3), 3387–3391.

Safutra, N. I., Fole, A., Gunawan, A., Hafid, M. F., Ahmad, A., & Herdianzah, Y. (2024). Perencanaan Jalur Evakuasi Kebakaran Yang Efisien Untuk Fasilitas Perawatan Rumah Sakit Dengan Menggunakan Algoritma Dijkstra. Jurnal Rekayasa SIstem Industri (JRSI), 9(2), 44–58.

Serang, A. E., Bolang, A. S. L., & Lapian, S. L. H. V. J. (2025). Evaluasi Kualitatif Logistik dan Distribusi dalam Program Makan Siang Bergizi Gratis: Studi Kasus Instrumental di Sekolah Menengah Atas Negeri, Kota Bitung, Indonesia. Jurnal Promotif Preventif, 8(6), 1807–1814.

Silitonga, Y. L., Indra, Z., & Purba, D. P. (2025). Implementasi Algoritma Heuristik Dalam Penyelesaian Masalah Travelling Salesman Problem Pada Optimasi Jalur Pengiriman Makanan Untuk Layanan Online Menggunakan Python. JATI (Jurnal Mahasiswa Teknik Informatika), 9(1), 298–304.

SP, M. I., & Sembiring, A. C. (2024). Implementasi Algoritma Djikstra Dalam Penyusunan Rute Distribusi Bahan Bakar Minyak Di Kabupaten Asahan. JURITI PRIMA (Junal Ilmiah Teknik Industri Prima), 7(2), 1–6.

Tambunan, K. A. H., Nababan, R., Siagian, R. A., Naiborhu, R., Harianti, S., & Jamaluddin. (2025). Tinjauan Kritis Tentang Program Makan Bergizi Gratis Terhadap Produktivitas Belajar Siswa. Katalis Pendidikan: Jurnal Ilmu Pendidikan Dan Matematika, 2(2), 21–31.

Wahyudi, R., Alfin, M., Henrydunan, J. B., & Harliana, P. (2024). Penerapan Algoritma Dijkstra Untuk Optimasi Ke Empat Gerbang Kampus Menggunakan Python. JATI (Jurnal Mahasiswa Teknik Informatika), 8(6), 12073–12078.

Wijayanti, R., Khusniyah, D., Dilia, M. H. H., Fitri, W. A., & Suhardi. (2025). Sistem Distribusi MBG di SMP Falatehan Contoh Praktik Pembelajaran Sistem Kolaborasi yang Efektif di Sekolah. Jurnal Pengabdian Masyarakat Dan Riset Pendidikan, 4(1), 1234–1241.