Pengembangan Algoritma Hybrid Restart Simulated Annealing with Variable Neighborhood Search (HRSA-VNS) untuk penyelesaian kasus Vehicle Routing Problem with Time Windows (VRPTW)

Abstract

Penentuan rute kendaraan (vehicle routing problem) merupakan salah satu komponen penting dalam sistem logistik saat ini. Hal ini dikarenakan penentuan rute kendaraan berpengaruh pada biaya transportasi dan waktu yang diperlukan dalam sistem logistik. Dalam permasalahan penentuan rute kendaraan terdapat batasan yang dihadapi yaitu kapasitas maksimum dari kendaraan dan batasan waktu dimana depot atau customer memiliki jam buka yang terbatas atau spesifik (time windows). Permasalahan inilah yang disebut sebagai Vehicle Routing Problem with Time Windows (VRPTW). Untuk menyelesaikan permasalahan VRPTW, penelitian ini mengembangkan suatu metode metaheuristik yaitu Hybrid Restart Simulated Annealing with Variable Neighborhood Search (HRSA-VNS). Algoritma HRSA-VNS ini merupakan modifikasi dari algoritma Simulated Annealing dengan menambahkan strategi restart dan menggunakan skema algoritma VNS dalam tahap pencarian solusi tetangga (neighborhood search). Pengujian performa algoritma HRSA-VNS dilakukan dengan membandingkan hasil algoritma dengan Best Known Solution (BKS) dan algoritma SA biasa tanpa modifikasi. Dari hasil yang didapatkan, diketahui bahwa algoritma yang dibangun cukup baik dalam menyelesaikan kasus VRPTW dengan rata-rata difference-nya adalah -2,0% dengan BKS web Solomon, 1,83% dengan BKS dari Alvarenga, dan -2,2% dengan algoritma SA biasa tanpa modifikasi.