PENYELESAIAN DYNAMIC TRAVELLING SALESMAN PROBLEM (DTSP) MENGGUNAKAN HYBRID GENETIC ALGORITHMS (GA) DAN TABU SEARCH (TS)

Dynamic Travelling Salesman Problem (DTSP) merupakan suatu permasalahan dalam menemukan jarak total minimal dari semua kota tujuan yang hanya dikunjungi tepat satu kali dan terdapat penambahkan atau pengurangan kota tujuan. Oleh karena itu, tujuan penulisan skripsi adalah untuk menyelesaikan DTSP dengan menggunakan hybrid Genectic Algorithm ( algoritma genetika) dan Tabu Search. Hybrid Genetic Algorithm dan Tabu Search adalah algoritma yang menggabungkan proses algoritma Genetika dengan Tabu Search. Secara umum proses Algoritma Genetika adalah inisialisasi parameter, membangkitkan populasi awal, evalusi kromosom, seleksi, crossover, dan mutasi. Sedangkan secara umum proses Tabu Search adalah menentukan tabu list, memodifikasi, membandingkan nilai fungsi tujuan dan update tabu list. Dalam tugas akhir ini, proses seleksi yang digunakan adalah Roulette Wheel, proses crossover yang digunakan adalah Order Crossover, dan proses Tabu Search digunakan sebagai pengganti proses mutasi. Ada 3 jenis data yang digunakan yaitu data kecil, data sedang, dan data besar. Ketiga data tersebut diselesaikan dengan progam C ++ yang dibuat oleh perangkat lunak Borland C ++. Hasil perhitungan data kecil (10 kota) setelah terdapat penambahan 5 kota tujuan adalah 316 satuan jarak, untuk perhitungan data sedang (25 kota) setelah terdapat penambahkan 5 kota tujuan adalah 10422 satuan jarak, sedangkan untuk perhitungan data besar (100 kota) setelah penambahan terdapat 5 kota tujuan adalah 60172 satuan jarak. Sehingga semakin besar jumlah kromosom yang dibangkitkan, semakin besar Pc dan jumlah iterasi yang dilakukan maka solusi akhir yang didapatkan lebih baik. Kata kunci : Genetic Algorithm, Tabu Search, Dynamic Travelling Salesman Problem, Hybrid Algorit