Penyelesaian Family Traveling Salesman Problem dengan algoritma Bee Colony Optimization

Abstract

Pada penulisan karya ilmiah ini akan dibahas mengenai penyelesaian Family Traveling Salesman Problem. Family Traveling Salesman Problem adalah permasalahan yang melibatkan n buah node yang terbagi dalam f buah family. Dalam tiap family terdapat v buah node yang harus dikunjungi. Hasil akhir dari permasalahan ini adalah sebuah jalur yang mengunjungi seluruh v node yang ada dalam tiap f yang memiliki panjang jalur terkecil. Algoritma bee colony optimization digunakan untuk menyelesaikan permasalahan tersebut. Algoritma Bee Colony Optimization digunakan dalam penelitian ini karena algoritma ini cocok untuk menyelesaikan permasalahan pencarian jalur. Algoritma ini juga mengikuti cara kerja dari koloni lebah. Cara kerjanya adalah lebah akan mengikuti lebah lain yang memiliki informasi dari jarak, dan kualitas makanan paling baik. Pada algoritma ini akan digunakan nilai preferensi untuk menentukan apakah suatu tujuan akan dipilih. Untuk beberapa kasus dengan masukan parameter yang tepat algoritma ini akan menghasilkan jalur yang dianggap optimal, sedangkan untuk kasus-kasus yang cukup rumit algoritma ini akan mengahasilkan jalur yang kurang baik tetapi masih memiliki nilai error yang cukup kecil. Eksperimen yang akan dilakukan adalah dengan mengganti nilai parameter yang ada pada perangkat lunak. Berdasarkan hasil dari pengujian yang telah dilakukan dengan mengganti nilai-nilai parameter yang ada. Dari hasil pengujian eksperimental untuk menguji apakah nilai probabilitas sebuah node akan dikunjungi berpengaruh pada panjang jalur yang dihasilkan. Didapatkan hasil bahwa jika nilai probabilitas pemilihan node digunakan, maka dihasilkan jalur yang lebih pendek. Sedangkan untuk pengaruh nilai jarak dari satu node ke node lain didapatkan jika besar nilai jarak yang digunakan sebesar 80% sampai 100% akan berpengaruh pada hasil panjang jalur yang didapatkan. Untuk pengujian terhadap nilai probabilitas terbesar yang digunakan didapatkan hasil jika besar nilai probabilitas yang dimasukkan berkisar antara 60% sampai 80% akan menghasilkan jalur dengan panjang yang lebih kecil, lalu untuk pengujian nilai error didapatkan hasil untuk kasus dengan banyak node 10 perangkat lunak memiliki nilai error rata-rata sebesar 22%. Sedangkan untuk kasus dengan banyak node 20 didapatkan rata-rata nilai error sebesar 19%, untuk kasus dengan banyak node 50 sampai 200 nilai error yang didapat berkisar antara 4% sampai 3,5%.