Improvisasi Algoritma Genetika dengan Route-Based Crossover dan 2-opt pada Permasalahan Rute Kendaraan

Abstract

Permasalahan Rute Kendaraan (Vehicle Routing Problem) bertujuan untuk meminimalkan biaya transportasi. Rute adalah serangkaian urutan dari depo menuju beberapa pelanggan kemudian kembali lagi ke depo. Adapun permasalahan normalnya dimodelkan dalam bentuk graf dengan bobot. Karena setiap ruas jalan memiliki jarak/biaya yang harus dikeluarkan ketika menempuh ruas tersebut maka diperlukan penyelesaian agar meminimalkan biaya transportasi ketika menempuh ruas-ruas jalan tersebut dengan tetap melayani semua pelanggan yang ada. Penelitian ini mengembangkan algoritma metaheuristik, khususnya algoritma genetika yang diimprovisasi dengan Route-Based Crossover dan 2-opt untuk meminimalkan total jarak pengiriman. Hasilnya menunjukkan solusi yang 3% lebih buruk dibandingkan algoritma koloni semut, namun 7% lebih baik daripada pencarian tabu.