Modifikasi penerapan algoritma Multi-Verse pada : studi kasus Asymmetric Traveling Salesman Problem

Abstract

Asymmetric Traveling Salesman Problem (ATSP) adalah permasalahan optimasi dimana terdapat seorang pedagang yang perlu mengunjungi beberapa kota. Pada kasus ATSP, jarak tempuh dari kota A ke kota B tidak sama dengan jarak tempuh dari kota B ke kota A. Tujuan penyelesaian masalah ini adalah untuk meminimasi jarak tempuh yang dialami oleh pedagang itu. Multi-Verse Optimizer algorithm (MVO) adalah salah satu metode metaheuristik pernah dicoba untuk menyelesaikan permasalahan ATSP. Namun, hasil dari implementasi MVO dalam menyelesaikan permasalahan ATSP masih kurang begitu baik. Oleh sebab itu, pada penelitian ini akan dilakukan modifikasi penerapan MVO terhadap kasus ATSP. Modifikasi dilakukan dengan menggunakan algoritma divide and conquer sebagai dasar. Metode divide and conquer berusaha memecah satu permasalahan yang besar menjadi beberapa permasalahan kecil. Lalu, permasalahan kecil yang ada diselesaikan akan digabung lagi untuk mendapat hasil akhir secara keseluruhan.Hasil penerapan modifikasi mampu membuat best known solution yang awalnya bernilai lebih besar 22,81% menjadi 8,68% lebih besar dari solusi optimal untuk kasus dengan 45 kota. Pada kasus ATSP dengan 34 kota, hasil penerapan modifikasi mampu membuat best known solution yang sebelumnya lebih besar 10,49% menjadi 2,95% lebih besar dari solusi optimal.