Implementasi Kombinasi Algoritma Genetika dan Tabu Search untuk Penyelesaian Travelling Salesman Problem

Abstract

Saat melakukan kunjungan ke beberapa tempat, seringkali seseorang kebingungan dalam menentukan urutan titik atau tempat yang akan dikunjungi agar seluruh tempat tersebut dapat dilalui dan jarak yang ditempuh sekecil mungkin. Permasalahan ini dikenal dengan Travelling Salesman Problem (TSP). TSP adalah sebuah persoalan klasik seorang salesman saat mencari rute atau jalur terpendek. Banyak algoritma yang dapat digunakan dalam penyelesaian TSP, namun setiap algoritma juga memiliki kelebihan dan kekurangan masing-masing. Tujuan dari makalah ini yaitu merancang kombinasi Algoritma Genetika dan Tabu Search (GA-TS) dalam menyelesaikan kasus TSP. Diharapkan dengan menggunakan kombinasi GA-TS, hasil akhir dari penyelesaian TSP yang didapatkan lebih optimal dibandingkan dengan Algoritma Genetika. Kombinasi GA-TS memiliki beberapa tahapan yaitu inisialisasi kromosom, evaluasi kromosom, seleksi kromosom, pengecekan tabulist, crossover, mutasi, regenerasi, dan penentuan kromosom terbaik. Tahapan selanjutnya setelah perancangan yaitu implementasi sistem. Sistem diharapkan dapat menghasilkan sebuah program yang mampu menyelesaikan beberapa kasus TSP yang berbeda dan mendapatkan hasil yang optimal.