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.
