Penerapan harmony search algorithm untuk menyelesaikan kasus asymmetric traveling salesman problem

Abstract

Asymmetric Traveling Salesman Problem (ATSP) merupakan masalah pencarian rute terpendek oleh seorang salesman untuk mengunjungi seluruh kota yang perlu ia kunjungi. Pada ATSP, seorang salesman hanya boleh mengunjungi masing-masing kota yang ada satu kali dan setelah mengunjungi kota terakhir, ia akan kembali ke kota pertama. Persoalan ATSP ini merupakan variasi dari persoalan Traveling Salesman Problem. Perbedaan ATSP adalah matriks jarak antarkota yang tidak simetris (asimetrik). Asimetrik berarti jarak dari kota A menuju kota B berbeda dengan jarak dari kota B menuju kota A. Dalam penelitian ini, persoalan ATSP coba diselesaikan menggunakan Harmony Search Algorithm (HSA). HSA merupakan algoritma metaheuristik yang terispirasi dari musik. HSA terispirasi dari kebiasaan para pemusik dalam mencari kombinasi nada-nada yang dapat menghasilkan suatu harmoni yang baik. Cara pemusik untuk mencari kombinasi nada tersebut dengan melakukan improvisasi yang terdiri dari 3 cara, yaitu memilih nada yang diingatnya, memilih nada acak, dan melakukan adjustment. Dengan ketiga cara ini, akan didapatkan sebuah kombinasi nada yang menghasilkan harmoni. Terdapat 3 buah parameter pada HSA, yaitu HMS yang menunjukkan kapasitas memori, HMCR yang merupakan peluang memilih memori yang diingatnya, dan PAR yang merupakan peluang melakukan pitch adjustment. Dalam penelitian ini, HSA telah dirancang dan diimplementasikan pada 5 buah kasus benchmark ATSP dengan menggunakan 12 kombinasi parameter yang berbeda-beda. Perbandingan HSA yang dilakukan dengan new genetic algorithm (NGA) dan improved discrete bat algorithm (IDBA) untuk kasus dengan jumlah kota 17 menunjukkan hasil yang sama baiknya, yaitu mencapai titik optimal. Untuk kasus yang memiliki jumlah kota lebih banyak, algoritma pembanding menghasilkan solusi yang lebih baik dari HSA. Semua parameter diuji pengaruhnya dan interaksinya dengan menggunakan ANOVA multifactor. Hasil dari pengujian pengaruh parameter tersebut menunjukkan adanya pengaruh dari parameter pada kasus dengan jumlah kota sedikit dan interaksi parameter pada kasus dengan jumlah kota yang lebih banyak.