Genetic Algorithm with Local Search (GALS) pada Permasalahan Vehicle Routing Problem dalam Sistem Distribusi Darah PMI Kota Yogyakarta

Muhammad Alif Rahman, Ir.Nur Mayke Eka Normasari, S.T., M.Eng., Ph.D., IPM. ASEAN Eng.

2026 | Skripsi | TEKNIK INDUSTRI

Darah merupakan salah satu komponen vital dalam pemenuhan pelayanan medis rumah sakit seperti pelayanan operasi besar, persalinan, dan transfusi darah. Oleh karena itu, memastikan ketersediaan darah menjadi aspek yang sangat penting bagi rumah sakit. Tantangan muncul dari proses pengiriman darah karena darah memiliki batas umur simpan dalam transportasi atau spoilage time selama lima jam sehingga rute perjalanan harus dioptimalkan. Permasalahan ini termasuk dalam konteks Vehicle Routing Problem with Time Windows and Spoilage Time (VRPTWS). Penelitian terdahulu menyelesaikan permasalahan VRP dalam konteks distribusi darah dengan menggunakan pendekatan solusi eksak. Namun, pendekatan ini memiliki keterbatasan pada efisiensi waktu komputasi ketika kasus menjadi semakin kompleks. Oleh karena itu, penelitian ini bertujuan untuk mengembangkan pendekatan solusi metaheuristik dalam menyelesaikan kasus distribusi darah yang semakin kompleks.

Penelitian ini menentukan rute distribusi darah dengan mengembangkan pendekatan solusi metaheuristik berbasis Genetic Algorithm (GA) yang dikembangkan dengan bantuan mekanisme Local Search dan Pemilihan Operator Local Search yang Adaptif (GALS). Cara kerja pendeketan solusi Genetic Algorithm (GA) meniru proses evolusi melalui beberapa tahapan yaitu inisialisasi populasi, evaluasi fitness, seleksi, crossover, mutation, dan pembentukan generasi baru. Kemudian, pendekatan solusi Genetic Algorithm (GA) dikembangkan dengan menambahkan mekanisme Local Search dengan bantuan operator local search (swap, insertion, dan 2-opt) yang dipilih secara adaptif untuk membantu dalam proses eksploitasi solusi. Metode ini digunakan untuk mengoptimalkan rute distribusi darah dengan tujuan untuk meminimalkan jarak tempuh distribusi darah.

Hasil dari penelitian menunjukkan bahwa kinerja pendekatan solusi Basic Genetic Algorithm (BGA) memiliki waktu komputasi yang lebih baik daripada dua pendekatan solusi lainnya dengan gap solusi sebesar 4,17% terhadap pendekatan solusi eksak sebagai solusi paling optimal atau Best Known Solution (BKS). Sementara itu, pendekatan solusi Genetic Algorithm with Local Seach (GALS) memiliki kinerja hasil solusi yang lebih baik daripada kinerja pendekatan solusi BGA dasar dengan gap solusi sebesar <1>

Blood is a critical component in supporting hospital medical services, including major surgeries, childbirth, and blood transfusions. Therefore, ensuring the availability of blood supplies is an essential concern for hospitals. One of the main challenges in blood distribution lies in the delivery process, as blood products have a limited transportation shelf life, known as spoilage time, of five hours. Consequently, distribution routes must be carefully optimized. This problem can be formulated as a Vehicle Routing Problem with Time Windows and Spoilage Time (VRPTWS). Previous studies have addressed blood distribution routing problems using exact solution approaches; however, these methods suffer from significant computational limitations as problem size and complexity increase. Accordingly, this study aims to develop a metaheuristic-based solution approach to handle more complex blood distribution scenarios.

In this study, blood distribution routes are optimized using a Genetic Algorithm (GA), based metaheuristic approach enhanced with a Local Search mechanism and an Adaptive Local Search Operator Selection strategy, referred to as Genetic Algorithm with Local Search (GALS). The GA mimics the evolutionary process through several stages, including population initialization, fitness evaluation, selection, crossover, mutation, and generation replacement. Furthermore, the proposed approach incorporates a Local Search procedure using three neighborhood operators—swap, insertion, and 2-opt—which are selected adaptively to strengthen the exploitation capability of the algorithm. The objective of the proposed method is to minimize the total travel distance of blood distribution routes while satisfying time window and spoilage constraints.

The experimental results indicate that the Basic Genetic Algorithm (BGA) achieves superior computational time performance compared to the other solution approaches, with an average solution gap of 4.17% relative to the exact solution, which is considered the Best Known Solution (BKS). Meanwhile, the GALS approach produces higher-quality solutions than the BGA, achieving a solution gap of less than 1% with respect to the BKS, albeit at the cost of longer computational time. In addition to solution quality comparison, computational time analysis shows that the GALS approach is able to reduce the total travel distance by approximately 0.075 km or 75 m for each additional second of computation time. These findings provide practical insights for PMI Kota Yogyakarta in selecting distribution routes that prioritize reduced travel distance under time-sensitive conditions.

Kata Kunci : Blood Distribution, Vehicle Routing Problem with Time Windows and Spoilage Time, Metaheuristics, Genetic Algorithm, Local Search