Penyelesaian Traveling Salesman Problem menggunakan Algoritma Fruitfly Optimization

Abstract

Traveling Salesman Problem (TSP) merupakan sebuah permasalahan di mana seseorang ingin bepergian ke setiap kota yang terdapat dalam peta masing-masing satu kali, dan kembali ke kota asalnya dengan bobot serendah mungkin. Untuk mencari rute yang memiliki bobot yang paling rendah ini tentunya dapat dilakukan dengan menghitung segala jenis kemungkinan rute yang ada, namun semakin banyak kota dalam peta tersebut, maka semakin lama waktu yang dibutuhkan untuk mencari rute terbaik tersebut dan semakin banyak kemungkinan rute yang menjadi pertimbangan untuk rute yang memiliki bobot paling rendah. Maka dari itu, pendekatan optimisasi akan dilakukan untuk mencari rute dengan bobot paling optimal dengan menggunakan waktu yang relatif lebih sedikit. Optimal yang dimaksud di sini adalah sebuah keadaan di mana hasil yang didapatkan paling mendekati hasil yang terbaik. Dengan demikian, tidak perlu diperhitungkan segala kemungkinan yang ada. Fruitfly Optimization Algorithm (FOA) merupakan sebuah algoritma optimisasi yang meniru pergerakan dari lalat buah untuk mencari makanan. Lalat buah ini akan mencari makanan dalam kawanan. Lalat-lalat buah yang terdapat dalam suatu area akan berusaha berkumpul dengan kawanannya sebelum mencari makanan dengan smell concentration value yang paling tinggi di setiap kawanan lalat buah tersebut. Calon solusi / rute paling optimal dalam TSP dapat dimodelkan menjadi lalat buah dalam FOA. Titik atau kota dalam peta dalam TSP dapat dimodelkan dengan arah pergerakan kawanan lalat buah pada FOA. Bobot dari perjalanan dalam TSP ini dapat dimodelkan dengan smell concentration value. Semakin sedikt bobotnya maka semakin tinggi smell concentration value tersebut. Dalam penelitian ini akan dibuat sebuah perangkat lunak berbasis web yang menggunakan web framework Django. Web framework merupakan sebuah kumpulan dari peralatan yang dapat meringankan kesulitan untuk penyelesaian persoalan dalam pengembangan jaringan. Perangkat lunak ini akan menerima masukan berupa variabel-variabel seperti iterasi pengerjaan FOA, banyaknya calon solusi, konstanta Vr, banyaknya iterasi operasi mutasi bit, jenis sensitive vision function, dataset beserta jenis datasetnya. Setelah menerima masukan, perangkat lunak akan memproses masukan dan mengeluarkan pemetaan titik-titiknya dalam sebuah graf, dan akan ditampilkan hasil dari rute yang paling optimal beserta visualisasi grafnya dan total bobot yang diperlukan untuk perjalanan tersebut. Kinerja FOA dalam menyelesaikan TSP akan diuji dengan memasukkan berbagai variasi pada variabel-variabel masukan yang telah disebut sebelumnya, yaitu, banyaknya titik pada dataset yang akan diuji, sensitive vision function yang digunakan, konstanta Vr yang digunakan, banyaknya iterasi operasi mutasi bit, banyaknya calon solusi yang paling optimal, dan banyaknya iterasi penggunaan FOA. Kinerja FOA dalam menyelesaikan TSP lebih baik jika jumlah titik pada dataset sedikit, penggunaan sensitive vision function tertentu, semakin dekat konstanta Vr ke 50%, banyaknya populasi, dan iterasi penggunaan FOA yang cukup banyak.