Abstract:
Asymmetric Traveling Salesman Problem atau ATSP adalah sebuah
permasalahan optimasi dimana terdapat seorang salesman yang memulai perjalanan
dari kota asalnya. Salesman tersebut hendak mengunjungi kota-kota lainnya dan kembali
ke kota asalnya lagi. Salesman tersebut mengetahui semua informasi jarak dari suatu
kota ke kota lainnya, dan ingin menentukan rute yang paling efisien yang dapat
ditempuh. ATSP sendiri merupakan variasi dari Traveling Salesman Problem biasa. Pada
ATSP, jarak dari kota A ke kota B belum tentu sama dengan jarak dari kota B ke kota A.
Pada penelitian ini, permasalahan ATSP ini diselesaikan menggunakan
Football Game Algorithm (FGA). FGA merupakan algoritma metaheuristik yang
terinspirasi oleh permainan sepak bola. Dalam algoritma ini, diadopsi dua elemen utama
permainan sepak bola, yaitu pergerakan pemain dan instruksi pelatih. Para pemain selalu
bergerak untuk mencari posisi terbaik terhadap posisi bola maupun posisi pemain
lainnya. Dalam algoritma ini, elemen pergerakan pemain mewakili proses eksplorasi
solusi yang dapat diatur menggunakan parameter pengatur keacakan ?쐝17T. Instruksi dari
pelatih dianalogikan sebagai proses eksploitasi solusi dan diatur menggunakan tiga buah
parameter, yakni 款 dan 貫 yang berfungsi mengatur tingkat eksploitasi, serta Coach
Memory Size (CMS) yang berfungsi untuk mengatur ukuran dari Coach Memory atau
memori yang menyimpan instruksi pelatih.
FGA diimplementasikan ke lima buah kasus benchmark ATSP dengan
menggunakan 16 kombinasi nilai parameter yang berbeda. Penerapan FGA
menghasilkan solusi yang sama dengan best known solution dari empat kasus dengan
jumlah kota 17, 34, 45, dan 56 buah. Pada kasus dengan jumlah kota 71 buah, solusi
yang dihasilkan tidak dapat menyamai best known solution. Parameter-parameter dari
FGA kemudian diuji pengaruhnya terhadap performansi algoritma menggunakan ANOVA
multifaktor, dan terbukti bahwa pada semua kasus terdapat interaksi parameter yang
mempengaruhi hasil yang didapatkan. Solusi yang dihasilkan FGA juga dibandingkan
dengan New Genetic Algorithm (NGA), Improved Discrete Bat Algorithm (IDBA), dan
Harmony Search Algorithm (HSA). FGA menunjukkan performansi yang sama atau lebih
baik dari algoritma pembanding untuk empat kasus pertama. Pada kasus dengan kota
terbanyak FGA dapat menghasilkan solusi yang lebih baik dari IDBA dan HSA, namun
lebih buruk dibandingkan dengan NGA.
