Penyelesaian Capacitated Vehicle Routing Problem (CVRP) Menggunakan Algoritma Tabu Search Hgrex Crossover

Abstract

Abstrak: Kebutuhan akan adanya metode yang otomatis dapat menentukan rute optimal
dalam kasus CVRP, menuntun munculnya berbagai pendekatan yaitu eksak, heuristik, dan
metaheuristik. Salah satu algoritma dalam pendekatan heuristik/metaheuristik yang telah
banyak digunakan adalah Tabu Search. Tabu Search memanfaatkan teknik local search
solution space dan tabu list untuk dapat terhindar dari local optimum atau konvergensi yang
prematur, namun memerlukan proses yang panjang dikarenakan pencarian yang bersifat
sekuensial. Oleh karena itu, digunakanlah operator HGreX Crossover untuk meningkatkan
kualitas solusi yang dihasilkan dan mengurangi waktu eksekusi. Hasil pengujian pada dataset
Augerat dengan kode A-n32-k5 menunjukan bahwa penggunaan algoritma Tabu Search
HGreX Crossover mampu meningkatkan kualitas solusi secara berturut-turut sebesar 14.88%,
19.08%, dan 14.04% untuk 100, 500, dan 1000 iterasi jika dibandingkan dengan Tabu Search
konvensional dan waktu yang dibutuhkan Tabu Search HGreX Crossover secara berturutturut
lebih cepat 4.43%, 4.47%, dan 3.44% untuk 100, 500, dan 1000 iterasi dibandingkan
dengan Tabu Search konvensional.

Kata Kunci: CVRP, Tabu Search, HGreX Crossover