Penerapan Soccer League Competition Algorithm untuk menyelesaikan Capatitated Vehicle Routing Problem

Abstract

Capacitated Vehicle Routing Problem (CVRP) merupakan permasalahan yang bertujuan untuk mencari rute minimum dalam pengiriman barang ke pelanggan. Pengiriman dilakukan oleh beberapa kendaraan yang kapasitasnya identik. Setiap pelanggan hanya dilayani oleh satu kendaraan dan kendaraan yang ada juga memulai rute dari depot dan kembali ke depot. Barang yang dibawa tidak boleh melebihi kapasitas kendaraan. Karena CVRP merupakan permasalahan NP-hard maka semakin bertambah banyaknya jumlah pelanggan waktu penyelesaian akan semakin lama.

Pada penelitian ini CVRP diselesaikan menggunakan Soccer League Competition Algorithm (SLC). SLC merupakan salah satu jenis algoritma metaheuristik yang terinspirasi dari liga sepak bola di dunia. Di dalam sebuah liga sepak bola ada beberapa tim yang bertanding untuk memenangkan liga Pemain menjadi representasi solusi dari CVRP. Atribut dari pemain akan berkembang pada setiap pertandingan.

Pada penelitian ini juga dilakukan implementasi SLC ke dalam enam kasus benchmark dari CVRP. Dari kasus yang diuji SLC berhasil menemukan solusi yang sama dengan best known solution untuk kasus P-N16-K8, P-N19-K2, B-N31-K5, dan A-N32-K5. Nilai parameter jumlah tim yang dipakai adalah 2, 3, 4, dan 5. Nilai parameter jumlah pemain cadangan yang dipakai adalah 5, 11, dan 15. Lalu dilakukan uji ANOVA terhadap parameter SLC. Untuk kasus A-N32-K5 dan B-N57-K7 parameter yang berpengaruh adalah jumlah pemain cadangan dan interaksi antara jumlah pemain cadangan dan jumlah tim untuk nilai-nilai yang diuji. Untuk kasus B-N54-K7 parameter yang berpengaruh adalah interaksi antara jumlah pemain cadangan dan jumlah tim.

Performansi SLC dibandingkan dengan beberapa metode metaheuristik lainnya. Performansi SLC lebih baik dibandingkan dengan Dragonfly Algorithm pada semua kasus. SLC memiliki performansi yang sama baiknya dengan Artificial Bee Colony. SLC memiliki performansi yang sama dengan Genetic Algorithm pada kasus A-N32-K5 dan punya performansi yang lebih buruk dibanding Genetic Algorithm pada kasus B-N54-K7 dan B-N57-K7.