Penyelesaian Multiple Traveling Salesman Problem (MTSP) dengan algoritma firefly

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.