Penerapan Football Game Algorithm untuk menyelesaikan Asymmetric Travelling Salesman Problem

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.