Abstract:
Multiple traveling salesman problem (MTSP) adalah pengembangan dari permasalahan traveling
salesman problem (TSP). Dalam MTSP, terdapat m orang salesman (m > 1) yang akan
mengunjungi n buah simpul kota pada sebuah graf peta masing-masing tepat satu kali, kecuali
simpul kota tempat keberangkatan dan ketibaan (depot) pada setiap rute perjalanan. Tujuan
dari MTSP adalah mencari solusi berupa rute perjalanan minimum pada graf peta.
Algoritma firefly akan diimplementasikan untuk mencari solusi MTSP. Algoritma firefly adalah
suatu teknik meta-heuristik yang meniru perilaku kunang-kunang di alam. Kunang-kunang
memiliki kemampuan untuk mengeluarkan cahaya dari dalam tubuhnya untuk mampu bertahan
hidup di alam. Algoritma firefly mengibaratkan intensitas cahaya kunang-kunang sebagai calon
nilai solusi suatu permasalahan. Semakin kuat intensitas cahaya seekor kunang-kunang, maka
nilai solusinya dianggap semakin mendekati nilai solusi permasalahan. Semakin redup cahaya
seekor kunang-kunang, maka nilai solusinya akan semakin tidak mendekati solusi permasalahan.
Kunang-kunang dalam algoritma firefly juga memiliki derajat ketertarikan (degree of attractiveness).
Degree of attractiveness adalah ukuran kemampuan seekor kunang-kunang untuk menarik
kunang-kunang lainnya dengan cahayanya.
Hasil dari penelitian dalam skripsi ini adalah algoritma firefly dapat diimplementasikan untuk
mencari solusi MTSP dengan sistem single depot, yaitu rute minimum yang dapat ditempuh
oleh seluruh salesman berjumlah m yang mengelilingi n buah simpul kota pada sebuah graf peta
masing-masing tepat satu kali pada setiap rute yang ditempuh oleh setiap salesman. Algoritma
firefly mampu untuk mencari solusi MTSP apabila input graf peta adalah graf peta terhubung
lengkap berbobot dan jumlah salesman antara 2 sampai dengan n − 2.
