Penerapan Football Game Algorithm untuk menyelesaikan Capacitated Vehicle Routing Problem

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.