AN ADAPTIVE LARGE NEIGHBORHOOD SEARCH-BASED APPROACH FOR OPTIMIZING A MULTI-COMMODITY TWO-ECHELON VEHICLE ROUTING PROBLEM WITH BACKHAUL AND TIME WINDOWS: CASE STUDY OF INDONESIA’S NUTRITIOUS LUNCH PROGRAM

Melvin Cahyadi Tirtayasa, Muhammad Alfian Amrizal, B.Eng., M.I.S., Ph.D.

2026 | Skripsi | ILMU KOMPUTER

Suatu implementasi program 'Makanan Bergizi Gratis' (MBG) yang sukses perlu memiliki jaringan logistik yang efisien untuk memastikan pengiriman makanan yang tepat waktu kepada siswa. Penelitian ini mengatasi tantangan distribusi program tersebut dengan memodelkan jaringan sebagai Two-Echelon Multi-Commodity Vehicle Routing Problem with Time Windows, Backhaul, and Late Penalties (2E-MCVRP-TW-BH-LP). Formulasi ini merepresentasikan kontribusi baru dengan mengintegrasikan kendala yang kompleks, khususnya aliran multi-komoditas dan logistik balik (reverse logistics) simultan, yang jarang dibahas secara bersamaan dalam literatur yang ada. Penelitian ini berfokus pada pengoptimalan aliran bahan baku ke dapur umum dan pengiriman makanan siap saji ke sekolah-sekolah, sekaligus mengintegrasikan logistik balik yang diperlukan untuk mengumpulkan wadah kosong. Untuk mengatasi kompleksitas komputasi yang tinggi dari model VRP yang kaya ini secara efisien, sebuah algoritma heuristik Adaptive Large Neighbourhood Search (ALNS) dikembangkan. Model ini dievaluasi menggunakan studi kasus dunia nyata yang berbasis di Bali, yang bertujuan untuk meminimalkan biaya operasional dan waktu perjalanan dengan tetap mematuhi jendela waktu layanan secara ketat. Penelitian ini menyediakan kerangka kerja optimasi yang dapat diskalakan (scalable) untuk distribusi makan siang sekolah skala besar, serta menawarkan wawasan teknis dalam mengelola kendala kompleks dalam logistik kemanusiaan dan sektor publik. Evaluasi eksperimental terhadap exact solver (Gurobi) pada berbagai instans masalah berukuran kecil, menengah, dan besar menunjukkan bahwa metode berbasis ALNS yang diusulkan secara konsisten menghasilkan solusi dengan gap di bawah 2?ri lower bound. Hal yang krusial, sementara Gurobi menghabiskan batas waktu 2 jam dan gagal menemukan solusi untuk instans berukuran besar, pendekatan berbasis ALNS dapat menyelesaikannya dalam hitungan menit, yang menegaskan skalabilitas dari strategi dekomposisi tersebut.

A successful implementation of the 'Makanan Bergizi Gratis' (MBG) program requires an efficient logistics network to ensure the timely delivery of meals to students. This research addresses the distribution challenges of the program by modelling the network as a Two-Echelon Multi-Commodity Vehicle Routing Problem with Time Windows, Backhaul, and Late Penalties (2E-MCVRP-TW-BH-LP). This formulation represents a novel contribution by integrating complex constraints, specifically multi-commodity flows and simultaneous reverse logistics, that are rarely addressed simultaneously in existing literature. The study focuses on optimizing the flow of ingredients to mass kitchens and the delivery of prepared meals to schools, while integrating the reverse logistics required for collecting empty containers. To efficiently tackle the high computational complexity of this rich VRP model, an Adaptive Large Neighbourhood Search (ALNS) heuristic algorithm is developed. The model is evaluated using a real-world case study based in Bali, aiming to minimize operational costs and travel times while strictly adhering to service time windows. This research provides a scalable optimization framework for large-scale school lunch distribution, offering technical insights into managing complex constraints in humanitarian and public sector logistics. Experimental evaluation against an exact solver (Gurobi) across small, medium, and large problem instances demonstrates that the proposed ALNS-based method consistently produces solutions within a 2% gap of the lower bound. Critically, while Gurobi exhausts its 2-hour time limit and fails to find solutions for large instances, the ALNS-based approach solves them within minutes, affirming the scalability of the decomposition strategy.

Kata Kunci : Vehicle Routing Problem (VRP), Supply Chain Optimization, Otimalisasi Rantai Suplai, Two-Echelon VRP, Adaptive Large Neighbourhood Search (ALNS), Backhaul, Time Windows