Penerapan Lion Pride Optimizer untuk menyelesaikan kasus Asymmetric Traveling Salesman Problem

Abstract

Asymmetric Traveling Salesman Problem (ATSP) adalah suatu permasalahan pencarian rute yang dilakukan oleh seorang salesman dengan tujuan mengunjungi seluruh kota yang perlu Ia kunjungi dengan jarak terpendek. Pada permasalahan ATSP, seorang salesman hanya boleh mengunjungi masing-masing kota satu kali dan akan kembali ke kota pertama setelah seluruh kota telah dikunjungi. Permasalahan ATSP merupakan variasi dari persoalan Traveling Salesman Problem dengan perbedaan pada matriks jarak antarkota yang asymmetric. Asymmetric yang dimaksud berarti jarak dari kota A ke kota B dapat berbeda dari jarak kota B ke kota A. Dalam penelitian ini, permasalahan ATSP diselesaikan menggunakan Lion Pride Optimizer (LPO). LPO merupakan metaheuristic algorithm dan berbentuk sebagai evolutionary algorithm yang terinspirasi dari dinamika bertahan hidup sekelompok singa yang disebut pride. LPO didasarkan pada proses evolusi dan teori bertahan hidup singa pada pride dan masing-masing individu singa memainkan peran yang penting dalam menjaga kelompok pride itu sendiri dari generasi ke generasi. Terdapat 6 parameter pada LPO yaitu ths, thls, tls, mc0, k1 dan k2. Dalam penelitian ini LPO telah dirancang untuk dapat menyelesaikan kasus ATSP dan telah diterapkan pada 5 buah kasus benchmark menggunakan 8 kombinasi parameter yang berbeda-beda. Performansi LPO dibandingkan dengan Elephant Herding Optimization (EHO), New Genetic Algorithm (NGA), Improved Discrete Bat Algorithm (IDBA), Harmonic Search Algorithm (HSA), dan Lion Optimization Algorithm (LOA). Kasus dengan jumlah 17 hingga 45 kota berhasil diselesaikan dengan nilai best known solution sedangkan untuk kasus dengan jumlah 56 dan 71 didapatkan nilai yang lebih baik dari algoritma pembanding. Hasil dari pengujian parameter menunjukkan tidak adanya pengaruh dari interaksi parameter pada semua kasus pada penelitian ini.