Abstract:
Asymmetric Traveling Salesman Problem (ATSP) merupakan masalah
pencarian rute untuk mengunjungi seluruh kota yang perlu ia kunjungi dengan jarak
terpendek. Pada permasalahan ATSP, seorang salesman hanya boleh mengunjungi
masing-masing kota yang ada satu kali dan kembali ke kota pertama setelah seluruh kota
telah dikunjungi. Persoalan ATSP ini merupakan variasi dari persoalan Traveling
Salesman Problem yang memiliki perbedaan berupa matriks jarak antarkota yang
asimetrik. Asimetrik berarti jarak dari kota X menuju kota Y dapat berbeda dengan jarak
dari kota Y menuju kota X.
Dalam penelitian ini, persoalan ATSP diselesaikan dengan menggunakan
Elephant Herding Optimization (EHO). EHO merupakan algoritma metaheuristik yang
terinspirasi dari bagaimana sebuah populasi gajah berkumpul dan bergerak. Arah dan
besar pergerakan gajah dalam satu clan dipengaruhi oleh seorang gajah tertua yang
disebut Matriarch dan seluruh posisi gajah yang ada di dalam clan tersebut. Setiap
periode tertentu gajah laki-laki termuda pada clan akan pergi untuk hidup sendiri.
Terdapat 3 buah parameter pada EHO, yaitu Alfa yang menunjukkan pengaruh dari
Matriarch, Beta yang menunjukan pengaruh dari posisi gajah, dan Clan yang
menunjukkan berapa gajah setiap periode yang akan meninggalkan populasi.
Dalam penelitian ini, EHO telah dirancang untuk dapat menyelesaikan kasus
ATSP dan diimplementasikan pada 5 buah kasus benchmark dengan menggunakan 8
kombinasi parameter yang berbeda-beda. Perbandingan EHO dilakukan dengan New
Genetic Algorithm (NGA), Improved Discrete Bat Algorithm (IDBA), dan Harmony Search
Algorithm (HSA). Kasus dengan jumlah kota 17 hingga 56 menunjukkan hasil yang
mencapai solusi optimal, sedangkan untuk kasus yang memiliki jumlah kota 71, algoritma
NGA menghasilkan solusi yang lebih baik dari EHO. Semua parameter diuji pengaruhnya
dan interaksinya dengan menggunakan ANOVA multifactor. Hasil dari pengujian
pengaruh parameter tersebut menunjukkan adanya pengaruh dari interaksi parameter
pada semua kasus yang terdapat pada penelitian ini.
