Algoritma Genetika Ganda untuk Capacitated Vehicle Routing Problem

Abstract

Capacitated vehicle routing problem (CVRP) adalah salah satu variasi dari vehicle routing problem (VRP) yang menggunakan batasan kapasitas pada kendaraan yang dipakai. Ada banyak metode yang telah diteliti untuk bisa menyelesaikan CVRP, namun penggunaan algoritma genetika masih belum memberikan hasil yang memuaskan. Untuk mempermudah menyelesaikan CVRP, dapat dilakukan dekomposisi pada CVRP agar terbagi menjadi beberapa daerah yang dapat diselesaikan secara independen. Berdasarkan hal tersebut, dirumuskan algoritma genetika ganda yang terlebih dahulu berusaha untuk mendekomposisi CVRP dan kemudian mencari rute terpendek pada setiap daerah menggunakan dua algoritma genetika sederhana yang berbeda. Algoritma genetika ganda kemudian dibandingkan dengan algoritma genetika. Untuk membandingkan dua algoritma tersebut, dibuat empat permasalahan yaitu P50, P75, P100, dan P125 dengan pengujian pada setiap permasalahan menggunakan empat belas variasi kapasitas kendaraan yang berbeda. Didapatkan hasil bahwa algoritma genetika ganda lebih baik dari algoritma genetika dari segi waktu komputasi dan generasi. Dari segi jarak, algoritma genetika ganda juga lebih baik dari algoritma genetika kecuali untuk beberapa kapasitas kendaraan yang kecil pada permasalahan P50 dan P75.