Multiple Depot Multi Traveling Salesman Problem (MMTSP) merupakan bentuk umum dari masalah Traveling Salesman Problem (TSP), yaitu menentukan rute minimum dari perjalanan m salesman dengan n depot untuk menempuh semua kota dan kembali ke depot awalnya. Pada skripsi ini, dilakukan clustering pada kota-kota yang dilalui, sehingga pada setiap klaster masalah MMTSP dapat disederhanakan menjadi masalah MTSP Multiple Traveling Salesman Problem atau TSP. Algoritma clustering yang digunakan adalah Agglomerative Clustering dan K-Means Clustering. Selanjutnya dilakukan metode Ant Colony Optimization untuk mencari rute terpendek dari setiap klaster. Jumlah dari hasil rute terpendek dari setiap klaster merupakan solusi dari masalah MMTSP. Implementasi dilakukan dengan menggunakan sampel data TSPLIB, dan hasil yang didapat juga akan dibandingkan dengan penelitian yang telah dilakukan sebelumnya. Dari hasil simulasi, hasil algoritma Agglomerative Clustering ACO memberikan hasil yang terbaik dibandingkan algoritma K-Means Clustering ACO dan algoritma ACO saja.

---

Multiple Depot Multiple Traveling Salesman Problem MMTSP is a generalization of the common Traveling Salesman Problem TSP , whole purpose is to generate a minimum route of m traveling salesmen from n depots to explore all cities and back to their origins. In this skripsi, the cities will be clustered, so for every cluster, MMTSP will be simplified as MTSP Multiple Traveling Salesman Problem or TSP. The clustering algorithms that will be used are Agglomerative Clustering and K Means Clustering. Furthermore, for every cluster, the Ant Colony Optimization will be implemented to determine the shortest path. The distance of shortest path in every cluster will be summed as the solution of MMTSP. Implementation of the algorithm will be simulated by using the TSPLIB, and the solutions will be compared to previous research. The simulation results show that the Agglomerative clustering ACO is the best solution compared to the K Means ACO rsquo s and the only ACO algorithm.