Optimasi Genetic Algorithm Dengan Simulated Annealing untuk Multiple Depot Capacitated Vehicle Routing Problem - Aditya Permana; Mahmud Dwi Sulistyo; Gia Septiana Wulandari (Indonesia Symposium on Computing, 2015)
Multiple Depot Capacitated Vehicle Routing Problem (MDCVRP) adalah pengembangan dari Vehicle Routing Problem (VRP). Tujuan objektifnya adalah mencari rute kendaraan dengan biaya termurah dari depot ke setiap pelanggan yang harus dikunjungi. Pada MDCVRP, permasalahan bertambah dengan bertambahnya jumlah depot dan adanya constraint tambahan berupa batas kapasitas kendaraan. Secara matematis, MDCVRP ini merupakan permasalahan kombinatorial yang termasuk ke dalam kategori NP- hard (non-deterministic polynomial-time hard). Pada penelitian ini, digunakan Genetic Algorithm (GA) yang dioptimasi oleh algoritma Simulated Annealing (SA) dalam menyelesaikan permasalahan MDCVRP. Pada dasarnya, GA sudah cukup bagus dalam menyelesaikan berbagai permasalahan kombinatorial. Namun, kekurangannya adalah adanya kemungkinan GA dalam proses pencariannya terjebak dalam kondisi optimal lokal. Untuk mengatasi kekurangan tersebut, SA hadir untuk mengoptimalkan performansi GA agar terhindar dari konvergensi prematur karena terjebak dalam optimum lokal sehingga hasil yang diperoleh menjadi lebih baik. Observasi telah dilakukan beberapa kali sehingga mendapatkan setting terbaik untuk beberapa parameter yang berpengaruh terhadap sistem. Dari hasil percobaan, terbukti bahwa penerapan SA untuk mengoptimaasi GA selalu dapat menaikkan performansi sistem sebesar sekitar 1-2%. Dari keseluruhan pengujian yang telah dilakukan, performansi terbaik yang dihasilkan oleh sistem mencapai 94.51%. Â