Penerapan Algoritma Pigeon Inspired Optimization untuk menyelesaikan Capacitated Vehicle Routing Problem

Abstract

Capacitated Vehicle Routing Problem (CVRP) merupakan suatu permasalahan untuk menentukan rute pengiriman dari satu depot dengan menggunakan beberapa kendaraan yang berada pada depot yang dapat digunakan untuk mengirimkan barang menuju ke pelanggan. CVRP menentukan set rute S (satu rute untuk setiap kendaraan yang harus dimulai dan diakhiri di depot) sehingga seluruh kebutuhan pelanggan dan batasan operasional dapat dipenuhi dengan jarak transportasi minimal. Masalah CVRP adalah variasi dari VRP dimana pada CVRP terdapat tambahan batasan kapasitas kendaraan. Pada Penelitian ini CVRP akan diselesaikan dengan menggunakan algoritma Pigeon Inspired Optimization (PIO). Algoritma ini adalah algoritma swarm intelligence yang terinspirasi dari kemampuan burung merpati yang dapat mencari jalan pulang sendiri (homing ability). Terdapat dua kemampuan merpati yang digunakan sebagai inspirasi dalam algoritma ini yaitu map and compass operator dan landmark operator. Terdapat 4 parameter yang digunakan pada algoritma ini yaitu NP, Nc1max, Nc2max, dan R. Pernacangan algoritma PIO untuk menyelesaikan CVRP telah dilakukan dan algoritma PIO telah diimplementasikan pada 6 kasus benchmark CVRP. Performansi PIO akan dibandingkan dengan Artificial Bee Colony (ABC), Genetic Algorithm (GA), dan Dragonfly Algorithm (DA). Algoritma PIO berhasil mendapatkan solusi optimal pada kasus dengan 15 pelanggan, namun untuk kasus lain algoritma ABC dan GA menghasilkan solusi yang lebih baik dari PIO. Pengujian parameter telah dilakukan dengan ANOVA Multifaktor, hasilnya parameter R dan Nc1max memiliki pengaruh pada beberapa kasus.