Penentuan Rute Untuk Wate Collection Menggunakan Algoritma Genetika

Abstract

Aktivitas pengumpulan dan pengangkutan sampah memberikan kontribusi sebesar 70% terhadap total biaya pengelolaan sampah. Untuk menekan total biaya pengelolaan sampah, perlu dilakukan optimasi rute agar dapat meminimasi biaya transportasi pada proses waste collection. Penelitian ini berfokus pada penentuan rute waste collection khusus untuk sampah multilayer plastic (MLP) dengan fungsi tujuan untuk meminimasi total biaya transportasi. Kondisi pengumpulan sampah dimodelkan sebagai Vehicle Routing Problem (VRP) dengan batasan kapasitas kendaraan, time windows depot dan dengan ketentuan bahwa proses collecting dilakukan selama 3 periode (3 hari). Model ini disebut Multi-period Capacitated Vehicle Routing Problem with Time Windows (MCVRPTW). Sebagai pengembangan, permasalahan juga dimodelkan ke dalam Multi Trip Capacitated Vehicle Routing Problem with Time Windows (MTCVRPTW) dimana proses collecting dilakukan dalam 1 hari dan kendaraan diperbolehkan melakukan trip lebih dari satu kali. Kedua model diselesaikan dengan metode eksak menggunakan linear programming dan pendekatan metaheuristik menggunakan Algoritma Genetika (GA). Hasil penelitian menunjukkan bahwa metode eksak hanya mampu menyelesaikan permasalahan pada instance data yang kecil dan membutuhkan waktu komputasi 99% lebih tinggi dibandingkan GA. Rute terbaik dari hasil percobaan GA untuk model MCVRPTW dengan mutation rate dan crossover rate 0,75 dan 0,1 menghasilkan penghematan 30,2%. Adapun model MTCVRPTW dengan mutation rate dan crossover rate 0,75 dan 0,05 memberikan penghematan sebesar 32,2% dibandingan dengan kondisi existing.