Penerapan Multi-Verse Optimizer 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 Multi-Verse Optimizer (MVO). MVO merupakan algoritma metaheuristik yang terinspirasi oleh kejadian alam dimana universe yang ada pada alam semesta ini tidak hanya universe tempat kita hidup saja, tetapi ada universe lain yang tak terhingga jumlahnya. Dalam MVO sebuah universe terdapat white hole, black hole, dan wormhole. Objek-objek yang ada pada sebuah universe akan merepresentasikan sebuah kota pada permasalahan ATSP, sehingga sebuah universe akan merepresentasikan rute yang harus dikunjungi oleh salesman. Pertukaran objek akan dilakukan oleh white hole,black hole, dan wormhole. White hole dan black hole akan melakukan eksplorasi,sementara eksploitasi dilakukan oleh wormhole.

MVO diimplementasikan ke tiga buah kasus benchmark ATSP dengan menggunakan 8 kombinasi nilai parameter yang berbeda. Parameter yang diuji ada tiga yaitu Wormhole Existence Probability Maximum (WEP Max), Wormhole Existence Probability Minimum (WEP Min) dan L. Penerapan FGA menghasilkan solusi yang sama dengan best known solution dari kasus dengan jumlah kota 17, sementara untuk kota berjumlah 34, dan 45 solusi yang dihasilkan tidak dapat menyamai best known solution tetapi mempunyai nilai yang sangat dekat. Parameter-parameter dari MVO kemudian diuji pengaruhnya terhadap performansi algoritma menggunakan ANOVA multifaktor. Solusi yang dihasilkan MVO juga dibandingkan dengan New Genetic Algorithm (NGA), Harmony Search Algorithm (HSA), dan Football Game Algorithm (FGA). MVO menunjukkan performansi yang sama atau lebih baik dari HSA. Pada kasus dengan kota berjumlah 17, MVO dapat menghasilkan solusi yang sama dengan NGA dan FGA, tetapi untuk kota berjumlah 34 dan 45, MVO masih belum dapat menyaingi NGA dan FGA.