Penerapan Football Game Algorithm untuk menyelesaikan Asymmetric Travelling Salesman Problem

Show simple item record

dc.contributor.advisor Juwono, Cynthia Prithadevi
dc.contributor.author Raharja, Fransiskus Arnold
dc.date.accessioned 2018-02-02T08:56:03Z
dc.date.available 2018-02-02T08:56:03Z
dc.date.issued 2017
dc.identifier.other 6113166
dc.identifier.uri http://hdl.handle.net/123456789/5066
dc.description 4480 - FTI en_US
dc.description.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. en_US
dc.publisher Program Studi Teknik Industri Fakultas Teknologi Industri - UNPAR en_US
dc.subject Asymmetric Travelling Salesman Problem (ATSP) en_US
dc.subject Optimization Problem en_US
dc.subject Travelling Salesman Problem en_US
dc.subject Football Game Algorithm en_US
dc.subject Metaheuristic Algorithm en_US
dc.title Penerapan Football Game Algorithm untuk menyelesaikan Asymmetric Travelling Salesman Problem en_US
dc.type Unpublished Student Papers en_US


Files in this item

This item appears in the following Collection(s)

Show simple item record

Search UNPAR-IR


Advanced Search

Browse

My Account