Penerapan Lion Optimization Algorithm untuk menyelesaikan kasus Asymmetric Traveling Salesman Problem

Abstract

Asymmetric Traveling Salesman Problem (ATSP) merupakan model permasalahan optimasi dimana seorang salesman harus melalui semua kota yang ditunjuk dengan kondisi setiap kota hanya boleh dilalui satu kali dan terdapat perbedaan jarak rute pergi dan rute pulang. ATSP sendiri merupakan salah satu variasi dari Traveling Salesman Problem (TSP). Tujuan ATSP adalah meminimasi jarak yang akan ditempuh oleh salesman dalam mengunjungi setiap kota.

ATSP akan diselesaikan menggunakan Lion Optimization Algorithm atau biasa disingkat LOA dalam penelitian ini. Algoritma LOA merupakan salah satu algoritma metaheuristic yang tergolong dalam population-based algorithm yang terinspirasi dari tingkah laku kehidupan singa. Terdapat 6 operator berdasarkan tingkah laku kehidupan singa, yaitu Hunting, Moving Toward Safe Place, Roaming, Mating, Defense, dan Migration. Terdapat 4 parameter yang digunakan pada algoritma ini, yaitu persentase roaming (Ropc), persentase mating (Mapc), persentase mutasi (Mupc), dan persentase migration (Mipc).

Perancangan algoritma LOA untuk menyelesaikan permasalahan ATSP telah dilakukan. Implementasi algoritma LOA terhadap ATSP diterapkan pada 5 buah kasus ATSP. Metode OFAT digunakan untuk mendapatkan nilai parameter terbaik. Pengujian parameter telah dilakukan dengan ANOVA Multifaktor. Performansi LOA akan dibandingkan dengan A New Genetic Algorithm (NGA), Improved Discrete Bat Algorithm (IDBA), Harmony Search Algorithm (HSA), dan Elephant Herding Optimizaiton (EHO). Algoritma LOA berhasil mendapatkan best known solution pada kasus BR17, namun untuk kasus lainnya algoritma benchmark menghasilkan solusi yang lebih baik dari algoritma LOA.