Abstract:
Capacitated Vehicle Routing Problem (CVRP) merupakan suatu permasalahan yang terkait dengan
pencarian rute terpendek yang dapat ditempuh oleh kendaraan dalam melayani pelanggan. Setiap
kendaraan akan berpusat pada suatu depot. Setiap kendaraan yang telah selesai menempuh rute yang
ditugaskan akan kembali ke depot. Setiap pelanggan hanya dapat dilayani oleh satu kendaraan. Dalam
penentuan rute pengiriman, dipertimbangkan kapasitas kendaraan dan demand dari setiap pelanggan.
Pada penelitian ini, permasalahan CVRP akan diselesaikan dengan menggunakan Football Game
Algorithm (FGA). FGA merupakan algoritma metaheuristik yang terinspirasi dari tingkah laku pemain sepak
bola dalam mencari posisi terbaik untuk mencetak gol. Dalam pencarian posisi terbaik untuk mencetak gol,
ada dua jenis perpindahan posisi yang dilakukan pemain, yaitu perpindahan posisi menuju posisi pemain
yang membawa bola dan perpindahan posisi berdasarkan arahan pelatih.
Pada penelitian ini, FGA telah diimplementasikan pada enam kasus benchmark CVRP. Dari enam
kasus yang telah diselesaikan, FGA berhasil mendapatkan solusi yang sama dengan best known solution
untuk empat kasus. Hasil implementasi yang dilakukan akan dibandingkan dengan beberapa algoritma
pembanding, yaitu Dragonfly Algorithm (DA), Artificial Bee Colony (ABC), dan Genetic Algorithm (GA).
Secara keseluruhan, dapat dikatakan bahwa FGA memiliki peformansi yang lebih baik dari DA dan memiliki
performansi yang sama baiknya dengan ABC. Sedangkan, bila dibandingkan dengan GA, GA memiliki
performansi yang lebih baik dari FGA untuk beberapa kasus benchmark. Ada empat parameter FGA yang
diuji pengaruhnya terhadap performansi FGA, yaitu konstanta yang mengurangi nilai hyper radius limitation
value (γ), konstanta yang mengurangi nilai fitness limitation value (λ), konstanta yang mengurangi nilai step
size perpindahan pemain (θ), dan ukuran memori pelatih yang menyimpan posisi pemain dengan fitness
yang kecil (CMS). Hasil pengujian menunjukkan adanya pengaruh parameter dan interaksi antar parameter
terhadap performansi FGA untuk beberapa kasus benchmark.