Penerapan Cuckoo Search Algorithm dengan Local Search untuk menyelesaikan Orienteering Problem

Abstract

Orienteering Problem (OP) merupakan permasalahan dalam menentukan suatu rute kota dengan batasan waktu yang ditentukan. Tujuan utama dari OP adalah memaksimalkan skor total kepuasan. OP adalah permasalahan NP-hard (Nondeterministic Polynomial-time Hard), di mana waktu pencarian untuk solusi meningkat secara eksponensial untuk jumlah variabel yang meningkat. Hal ini menyebabkan penyelesaian permasalahan dengan metode analitik membutuhkan waktu yang sangat lama, sehingga menyelesaikan dengan metode pendekatan menjadi alternatif yang dipertimbangkan. Dalam penelitian ini, OP diselesaikan dengan salah satu metode pendekatan yaitu metode metaheuristik. Metode metaheuristik yang digunakan adalah Cuckoo Search Algorithm (CSA). CSA merupakan algoritma yang terinspirasi dari perkembangbiakan dan penyimpanan telur dari burung Cuckoo. Cuckoo dewasa akan meletakan telur pada sarang burung lain. Berdasarkan kegiatan yang dilakukan oleh CSA terdapat dua buah parameter yang diuji yaitu fraksi pergantian sarang buruk ( Pa ) dan parameter pada l ´e vy flights yaitu jarak pergerakan pencarian solusi ( ? ). Terdapat sembilan buah kombinasi parameter yang diterapkan untuk menyelesaikan 18 kasus OP. Dalam penelitian ini CSA dikombinasikan dengan tiga buah local search yaitu insertion, swap, dan 2-opt dalam menyelesaikan OP. Hasil dari penelitian ini adalah CSA yang dikombinasikan dengan local search dapat mencapai nilai yang sama dengan ACO pada 14 kasus dan belum mencapai nilai terbaik pada 4 kasus. Sedangkan bila dibandingkan dengan MFA, CSA dapat memberikan solusi yang lebih baik pada 3 kasus, memberikan nilai yang sama pada 11 kasus dan belum mencapai nilai terbaik pada 4 kasus. Berdasarkan uji ANOVA didapatkan parameter fraksi pergantian sarang buruk ( Pa ) berpengaruh terhadap performansi Cuckoo Search Algorithm dalam penyelesaian Orienteering Problem untuk 10 kasus.