Perbandingan Branch and Bound dan Nearest Neighbour Heuristic Pada CVRP Distribusi MBG SPPG Mangunsari Semarang

Nurizal Dwi Priandani; Fajar Rohman Hariri; Nadia Roosmalita Sari

doi:10.30865/json.v8i1.9739

Authors

Nurizal Dwi Priandani UIN Maulana Malik Ibrahim https://orcid.org/0000-0002-0418-7373
Fajar Rohman Hariri UIN Maulana Malik Ibrahim
Nadia Roosmalita Sari UIN Sayyid Ali Rahmatullah

DOI:

https://doi.org/10.30865/json.v8i1.9739

Keywords:

MBG, Optimasi, Rute, Distribusi, Branch-and-Bound, Nearest Neighbor Heuristic

Abstract

Program Makan Bergizi Gratis (MBG) merupakan kebijakan strategis pemerintah Indonesia untuk memperkuat pembangunan sumber daya manusia menuju Visi Indonesia Emas 2045. Sistem distribusi MBG menuntut perencanaan logistik yang presisi agar makanan dapat diterima oleh setiap sekolah secara tepat sasaran, efektif, dan tepat waktu. Pada penelitian ini, permasalahan distribusi dimodelkan sebagai Capacitated Vehicle Routing Problem (CVRP). Studi kasus dilakukan pada distribusi MBG di SPPG Mangunsari Kota Semarang yang melibatkan 1 depot, 17 sekolah penerima, 2 kendaraan distribusi, dengan kapasitas maksimum 1.000 paket makanan pada setiap kendaraan. Penelitian ini membandingkan kinerja algoritma Branch and Bound (BnB) dan Nearest Neighbor Heuristic (NNH) menggunakan lima metrik evaluasi, yaitu total jarak tempuh, total operasi komputasi (jumlah operasi yang dihitung), rerata waktu komputasi, panjang rute maksimum, dan keseimbangan jarak rute distribusi. Hasil pengujian menunjukkan bahwa BnB menghasilkan total jarak yang lebih efisien 14% yaitu sebesar 26,31 km, sedangkan NNH menghasilkan total jarak sebesar 30,59 km. Dari sisi total komputasi dan rerata waktu komputasi, NNH 99,99% lebih sedikit langkah komputasi dan 96,78% lebih cepat daripada BnB. Selain itu, NNH juga menunjukkan keunggulan pada keseimbangan jarak rute distribusi antar kendaraan dimana NNH menghasilkan selisih jarak antarkendaraan 98,91% lebih rendah dengan rute terpanjang yang dihasilkan NNH 15,75% lebih pendek dibandingkan dengan BnB. Dengan demikian, BnB lebih sesuai digunakan ketika efisiensi total jarak menjadi prioritas, sedangkan NNH lebih sesuai digunakan ketika efisiensi proses komputasi dan pemerataan jarak rute distribusi distribusi menjadi pertimbangan utama. Adapun hasil penelitian ini hanya terbatas pada kasus distribusi MBG di SPPG Mangunsari Kecamatan Gunungsari – Kota Semarang dan belum dapat digeneralisasi untuk seluruh distribusi MBG pada Kota Semarang.

References

[1] Anonim, “UU No. 59 Tahun 2024,” Undang-undang (UU) Nomor 59 Tahun 2024. Accessed: Apr. 27, 2026. [Online]. Available: https://peraturan.bpk.go.id/Details/299728/uu-no-59-tahun-2024

[2] Badan Pemeriksa Keuangan, “Perpres No. 83 Tahun 2024,” Peraturan Presiden (Perpres) Nomor 83 Tahun 2024. Accessed: Apr. 27, 2026. [Online]. Available: https://peraturan.bpk.go.id/Details/295857/perpres-no-83-tahun-2024

[3] Badan Pemeriksa Keuangan, “Perpres No. 115 Tahun 2025,” Peraturan Presiden (Perpres) Nomor 115 Tahun 2025. Accessed: Apr. 27, 2026. [Online]. Available: https://peraturan.bpk.go.id/Details/343430/perpres-no-115-tahun-2025

[4] Badan Gizi Nasional, “Petunjuk Teknis Tata Kelola Penyelenggaraan Program Makan Bergizi Gratis,” Badan Gizi Nasional. Accessed: Apr. 27, 2026. [Online]. Available: https://www.bgn.go.id/juknis/lB1PKg-petunjuk-teknis-tata-kelola-penyelenggaraan-program-makan-bergizi-gratis%5D

[5] Badan Gizi Nasional, “Pedoman Umum Sistem dan Tata Kelola badan Gizi Nasional Untuk Program Makan Bergizi Gratis” Badan Gizi Nasional. Accessed: May 12, 2026. [Online]. Available: https://www.bgn.go.id/juknis/LEP9KP-pedoman-umum-sistem-dan-tata-kelola-badan-gizi-nasional-untuk-program-makan-bergizi-gratis

[6] MBG Kota Semarang, “MBG Kota Semarang — Dasbor.” Accessed: Apr. 27, 2026. [Online]. Available: https://si-manggis.vercel.app/sppg_aktif.html

[7] P. Toth and D. Vigo, Vehicle Routing: Problems, Methods, and Applications. SIAM, 2014.

[8] D. R. Morrison, S. H. Jacobson, J. J. Sauppe, and E. C. Sewell, “Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning,” Discrete Optim., vol. 19, pp. 79–102, 2016.

[9] A. S. Fukunaga, “A branch-and-bound algorithm for hard multiple knapsack problems,” Ann. Oper. Res., vol. 184, no. 1, pp. 97–119, 2011.

[10] S. Tanaka and K. Tierney, “A branch and bound approach for large pre-marshalling problems,” Eur. J. Oper. Res., vol. 278, no. 1, pp. 211–225, 2019.

[11] Z. Wang and Q. Zeng, “A branch-and-bound approach for AGV dispatching and routing problems in automated container terminals,” Comput. Ind. Eng., vol. 166, p. 107968, 2022.

[12] B. Pamuk, T. Oncan, and I. K. Altinel, “An efficient branch-and-bound algorithm for the one-to-many shortest path problem with additional disjunctive conflict constraints,” Eur. J. Oper. Res., vol. 324, no. 2, pp. 398–413, 2025.

[13] F. Theurich, A. Fischer, and G. Scheithauer, “A branch-and-bound approach for a Vehicle Routing Problem with Customer Costs,” EURO J. Comput. Optim., vol. 8, no. 3, 2020.

[14] S. Dhanasekar, S. K. Dash, and N. Uthaman, “A Branch and Bound Algorithm to Solve Travelling Salesman Problem (TSP) with Uncertain Parameters,” Math. Stat., vol. 10, no. 2, pp. 358–365, 2022.

[15] S. P. Revika, J. Nurhakiki, B. Naysabilla, and S. S. B. Ginting, “Systematic Literature Review: Penerapan Metode Branch and Bound dalam Optimalisasi Produksi,” BILANGAN, vol. 3, no. 3, pp. 141–155, 2025.

[16] F. A. A. Situnggang and N. Napitupulu, “Implementation of Branch and Bound Algorithm to Solve the Travelling Salesman Problem at PT Jasa Harapan Barat,” J. Math., vol. 1, no. 1, pp. 1–7, 2023.

[17] E. Sanggala and M. A. Bisma, “Penyelesaian Capacitated Vehicle Routing Problem (CVRP) dengan Nearest Neighbour (Studi Kasus: Russian CVRP Instances),” JUTIN J. Tek. Ind. Terintegrasi, vol. 8, no. 3, pp. 2586–2599, 2025, doi: 10.31004/jutin.v8i3.46463.

[18] I. Masudin, R. F. Sa’diyah, D. M. Utama, D. P. Restuputri, and F. Jie, “Capacitated Vehicle Routing Problems: Nearest Neighbour vs. Tabu Search,” Int. J. Comput. Theory Eng., vol. 11, no. 4, pp. 76–79, 2019, doi: 10.7763/IJCTE.2019.V11.1246.

[19] E. E. Rosyida, Sugianto, and I. B. Efendi, “Capacitated Vehicle Routing Problem (CVRP) with Sweep and Nearest Neighbor Algorithm,” Sinergi Int. J. Logist., vol. 2, no. 1, pp. 17–29, 2024.

[20] F. Liu, C. Lu, L. Gui, Q. Zhang, X. Tong, and M. Yuan, “Heuristics for Vehicle Routing Problem: A Survey and Recent Advances,” ArXiv Prepr., 2023.

[21] A. S. Hameed, H. M. B. Alrikabi, A. A. Abdul-Razaq, H. K. Nasser, M. L. Mutar, and H. H. Katea, “A Detailed Review of the Capacitated Vehicle Routing Problem: Model, Computational Complexity, Solutions, and Practical Applications,” J. Internet Serv. Inf. Secur., vol. 15, no. 1, pp. 218–235, 2025, doi: 10.58346/JISIS.2025.I1.014.

[22] K. Buyukozdemir, A. Bas, K. Yildiz, and B. C. Uslu, “A Review of Heuristic Approaches to Vehicle Routing Problems,” presented at the 2021 IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE), 2021. doi: 10.1109/CSDE53843.2021.9718378.

[23] S. Z. Abidin, N. I. Jaini, and H. Daud, “Decision-Making Support in Vehicle Routing Problems: A Review of Recent Literature,” J. Adv. Res. Appl. Sci. Eng. Technol., vol. 44, no. 2, pp. 124–134, 2025, doi: 10.37934/araset.44.2.124134.

[24] J. Bauß, S. N. Parragh, and M. Stiglmayr, “On improvements of multi-objective branch and bound,” EURO J. Comput. Optim., vol. 12, p. 100099, 2024.

[25] D. Pecin, A. Pessoa, M. Poggi, and E. Uchoa, “Improved branch-cut-and-price for capacitated vehicle routing,” Math. Program. Comput., vol. 9, no. 1, pp. 61–100, Mar. 2017, doi: 10.1007/s12532-016-0108-8.

[26] C. Archetti and M. G. Speranza, “A survey on matheuristics for routing problems,” EURO J. Comput. Optim., vol. 2, no. 4, pp. 223–246, Nov. 2014, doi: 10.1007/s13675-014-0030-7.

[27] D. Pecin, C. Contardo, G. Desaulniers, and E. Uchoa, “New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows,” Inf. J. Comput., vol. 29, no. 3, pp. 489–502, Aug. 2017.

[28] R. Fukasawa, J. Lysgaard, M. P. de Aragao, M. Reis, E. Uchoa, and R. F. Werneck, “Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem”.

[29] X. Zhang, L. Chen, M. Gendreau, and A. Langevin, “A Branch-and-Price-and-Cut Algorithm for the Vehicle Routing Problem with Two-Dimensional Loading Constraints,” Transp. Sci., vol. 56, no. 6, pp. 1618–1635, Nov. 2022, doi: 10.1287/trsc.2022.1135.

[30] F. Cavaliere, E. Bendotti, and M. Fischetti, “An integrated local-search/set-partitioning refinement heuristic for the Capacitated Vehicle Routing Problem,” Math. Program. Comput., vol. 14, no. 4, pp. 749–779, Dec. 2022, doi: 10.1007/s12532-022-00224-2.

[31] M. Simensen, G. Hasle, and M. Stålhane, “Combining hybrid genetic search with ruin-and-recreate for solving the capacitated vehicle routing problem,” J. Heuristics, vol. 28, no. 5–6, pp. 653–697, Dec. 2022, doi: 10.1007/s10732-022-09500-9.

[32] Imen Hamdi, “Solving the cumulative capacitated vehicle routing problem with drones,” J. Ind. Prod. Eng., vol. 41, no. 4, pp. 344–361, 2024, doi: https://doi.org/10.1080/21681015.2024.2304570.