Penyelesaian kasus Asymmetric Traveling Salesman Problem untuk meminimasi jarak tempuh dengan menggunakan algoritma Elephant Herding Optimization

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.