Penerapan Algoritma Discrete Cuckoo Search Pada Multiple Travelling Salesman Problem

Pada penelitian ini salah satu variasi dari Travelling Salesman Problem (TSP) yaitu Multiple Travelling Salesman Problem (MTSP) diselesaikan dengan algoritma Discrete Cuckoo Search dan algoritma k-means++. Untuk menyelesaikan permasalahan MTSP ini, pertama-tama dilakukan klustering dengan menggunakan k-means++ untuk mendapatkan kota yang membentuk rute dari setiap salesman.Kemudian setelah mendapatkan kluster-kluster, dilakukan pembentukan dan pengoptimalan rute pada kluster-kluster tersebut satu per satu menggunakan Discrete Cuckoo Search. Dari hasil percobaan didapat bahwa parameter: jumlah populasi (pop) dan banyak generasi (ngen), berpengaruh pada jarak terpendek yang didapat serta waktu komputasi. Sedangkan untuk parameter fraksi Cuckoo yang jelek (pa), tidak berpengaruh terhadap jarak terpendek yang dihasilkan, tetapi berpengaruh pada waktu komputasi. Jika nilai fraksi yang diberikan semakin mendekati satu, waktu komputasi semakin bertambah dengan pa= 0 memiliki rerata waktu komputasi terkecil dan pa = 1 adalah fraksi dengan rerata waktu komputasi terbesar. Selain itu kombinasi k-means++ dan Discrete Cuckoo Search dibandingkan dengan Ant Colony Optimization dan Genetic Algorithm dari penelitian lain. ============================================================================== In this thesis writer combine Discrete Cuckoo Search and k-means++ to solve Multiple Travelling Salesman Problem (MTSP) with single depot which is nondeterministc polynomial-hard problem. k-means++ is used to find the city for route of every salesman. Once the route is found, Discrete Cuckoo Search is used to create route and optimize route. From the experiments it gets parameters such as number of population ( pop ) and number of generation ( ngen ) affect the solution from Discrete Cuckoo Search and its time of computation. Fraction of the worst Cukoo ( p a ) does not affect the algorithm to get solution. It only affects the time of computation. Every increasing of value of p a , get the time of computation bigger. The smallest time of computation is found on p a = 0 and the biggest is on p a = 1 . Also, the combination of method is compared with Ant Colony Optimization and Genetic Algorithm