Perpustakaan Digital ITB

Pada dial-a-ride problem (DARP) penumpang harus diantarkan dari titik penjemputan ke titik pengantaran dengan memperhitungkan batasan jendela waktu dan waktu ketidaknyamanan penumpang. Penelitian ini mengembangkan model matematis dan algoritma penyelesaian untuk kasus DARP dengan karakteristik multi depot, maksimum waktu perjalanan yang heterogen untuk setiap penumpang dan jumlah minimum penumpang yang harus dilayani oleh setiap kendaraan yang dipakai. Model matematis dan algoritma penyelesaian pada penelitian ini memiliki fungsi tujuan untuk meminimalkan total biaya transportasi dalam memenuhi seluruh permintaan pelanggan. Pada algoritma pemecahan masalah, pembangkitan solusi rute awal dilakukan menggunakan metode greedy insertion heuristic. Solusi rute awal ini kemudian akan diperbaiki untuk mendapatkan solusi yang lebih baik menggunakan variable neighborhood search (VNS). Pada kedua tahap tersebut, batasan mengenai jumlah minimum penumpang akan diabaikan. Kemudian pada tahap selanjutnya akan dicari solusi layak yang dapat memenuhi batasan jumlah minimum penumpang menggunakan operator relokasi dan penghancuran. Algortima yang dikembangkan memiliki waktu komputasi rata-rata yang lebih cepat dengan gap sebesar -94% dibandingkan dengan perhitungan solusi optimal secara analitik. Sedangkan jika dilihat dari nilai fungsi tujuan, perhitungan menggunakan algoritma sama dengan hasil perhitungan solusi optimal secara analitik untuk data berukuran kecil.