Penerapan Algoritma Cat Swarm Optimization untuk menyelesaikan kasus Asymmetric Traveling Salesman Problem

Abstract

Asymmetric Traveling Salesman Problem (ATSP) merupakan permasalahan kombinatorial dimana dianalogikan terdapat kota-kota yang harus dikunjungi oleh seorang salesman sebanyak satu kali sebelum kembali ke kota asal, dengan jarak dari kota a ke kota b tidak sama dengan jarak dari kota b ke kota a. Tujuan dari permasalahan ini adalah untuk meminimasi jarak yang ditempuh oleh salesman tersebut. Solusi yang dihasilkan dari permasalahan traveling salesman problem adalah berupa rute atau urutan kota yang dikunjungi oleh salesman. Pengaplikasian asymmetric travelingsalesman problem di dunia nyata antara lain adalah permasalahan penentuan rutepesawat terbang dan penentuan jadwal pengambilan uang pada payphone. Pada penelitian ini, permasalahan ATSP diselesaikan dengan menggunakan algoritma Cat Swarm Optimization (CSO). Algoritma CSO merupakan algoritma metaheuristik yang menggambarkan perilaku dari sekerumunan kucing dalam mengejar mangsanya. Algoritma dirancang dengan menggunakan random-key encoding sebagai bentuk penyesuaian permasalahan ATSP yang bersifat diskrit ke dalam algoritma CSO yang bersifat kontinu. Algoritma juga akan dimodifikasi dengan penambahan local search 2-opt untuk mendapatkan solusi akhir yang lebih baik. Digunakan lima buah kasus benchmark pada penelitian ini dan algoritma CSO dapat menemukan best known solution untuk dua dari lima kasus benchmark yang digunakan yaitu untuk kasus 17 dan 34 kota. Dari tiga kasus dimana algoritma CSO masih gagal untuk menemukan best known solution, deviasi terbesar berada pada kasus 71 kota dengan deviasi terhadap best-known solution sebesar 568 dan deviasi terkecil terhadap best-known solution pada kasus dengan 45 kota sebesar 98. Performansi tersebut dibandingkan dengan tiga algoritma pembanding yaitu elephant herding optimization, football game algorithm, dan improved discrete bat algorithm. Berdasarkan hasil penelitian, performansi algoritma CSO masih berada di bawah dari ketiga algoritma pembanding tersebut.