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.
