Penerapan Best Offspring Hybrid Genetic Algorithm pada penyelesaian Capacitated Vehicle Routing Problem with Time Windows

Abstract

Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) merupakan masalah kombinatorial dalam penentuan rute pengiriman barang ke sejumlah pelanggan dengan batasan kapasitas dan jadwal penerimaan pada setiap pelanggan (time windows). Tujuan CVRPTW adalah mendesain rute terpendek untuk meminimasi total cost atau meminimasi jumlah kendaraan yang digunakan dalam pengiriman tanpa melanggar batasan yang ada. CVRPTW tergolong ke dalam permasalahan NP-hard yang bisa diselesaikan secara eksak jika masalahnya masih memiliki lingkup yang kecil. Seiring bertambahnya jumlah pelanggan menyebabkan ruang pencarian solusi semakin luas dan waktu komputasi meningkat. Oleh karena itu, metode metaheuristik menjadi alternatif untuk menyelesaikan masalah ini dengan waktu yang singkat dan diharapkan dapat menghasilkan solusi yang baik. Best Offspring Hybrid Genetic Algorithm (BOHGA) adalah sebuah metode metaheuristik yang dikembangkan oleh Wen Wan dan Jeffrey B. Birch pada tahun 2013. BOHGA sendiri adalah pengembangan dari metaheuristik Genetic Algorithm (GA) yang terinspirasi dari seleksi alam. BOHGA melakukan modifikasi pada GA tanpa menambahkan parameter baru. Tahap utama BOHGA dibagi menjadi inisialisasi populasi, crossover, mutasi, dan local search. BOHGA meningkatkan efisiensi local search dengan hanya melakukan local search ketika solusi terbaik yang dihasilkan pada populasi anak juga merupakan solusi terbaik pada parent population yang sekarang. Pada penelitian ini, algoritma BOHGA dirancang dan diimplementasikan pada 12 kasus hipotetik Solomon benchmark problem. Selain itu dilakukan pengujian pengaruh parameter mutasi terhadap performansi algoritma. Sebagian besar kasus menunjukkan bahwa mutasi berpengaruh terhadap performansi algoritma. Algoritma BOHGA menunjukkan hasil yang baik pada 8 dari 12 kasus yang diuji dan memberikan hasil yang lebih baik dari best known solution pada satu kasus. Performansi algoritma BOHGA lebih baik dari Multi-verse Optimizer pada 2 dari 3 kasus yang diuji. Namun, performansi algoritma BOHGA lebih rendah dibandingkan algoritma Hybrid GA-Tabu-Chaotic Search pada 2 kasus yang diuji.