Penerapan Algoritma Variable Neighborhood Search dan Algoritma Large Neighborhood Search pada Distance Constrained Vehicle Routing Problem

Abstract

Distance Constrained Vehicle Routing Problem (DCVRP) merupakan salah satu macam dari Vehicle Routing Problem (VRP) yaitu masalah optimasi untuk menemukan rute pengirimian barang yang paling optimal dengan meminimumkan total jarak tempuh. Masalah utama DCVRP adalah menentukan rute kendaraan sedemikian hingga setiap pelanggan terlayani oleh satu kendaraan, setiap kendaraan memiliki jarak tempuh maksimal, dan mencari rute perjalanan setiap kendaraan yang paling minimum dimulai dari depot sampai kembali lagi ke depot. Penelitian ini menggunakan data simulasi berupa jarak antara depot dengan setiap pelanggan dan jarak antara setiap pelanggan dengan pelanggan lainnya yang dibuat melalui pembangkitan secara random dengan program MATLAB. Penelitian ini menyelesaikan masalah DCVRP dengan menggunakan algoritma Variabel Neighborhood Search (VNS) dan Large Neighborhood Search (LNS). Selain untuk mengetahui hasil dari penerapan kedua algoritma tersebut dalam menyelesaikan masalah DCVRP, penelitian ini juga bertujuan untuk membandingkan hasil dari kedua algoritma berdasarkan total jarak minimum yang dihasilkan dan waktu komputasinya. Algoritma VNS menghasilkan total jarak yang lebih optimal daripada algoritma LNS. Hal ini dikarenakan pada algoritma VNS memiliki parameter 𝜅𝑚𝑎𝑥 yang membuat algoritma VNS memiliki beberapa pilihan untuk menentukan solusi optimalnya, sedangkan pada algoritma LNS hanya menghasilkan solusi tunggal. Berdasarkan running time yang dihasilkan, tidak selalu algoritma VNS lebih baik daripada algoritma LNS. Adanya pembangkitan bilangan random pada kedua algoritma menjadi salah satu faktor dari hasil tersebut.