Implementation of clustered ant colony optimization in solving fixed destination multiple depot multiple traveling salesman problem

The multiple-depot multi-traveling salesman problem is a generalization of the traveling salesman problem, in which the objective is to determine the shortest route for m salesmen with n depots to reach every other node exactly once before returning to the initial depot. In this paper, we will perform clustering on any nodes traversed, allowing MMTSP to be simplified to an MTSP (multiple traveling salesman problem) or a TSP for each cluster. The clustering algorithms that will be used are agglomerative clustering and K-means clustering, while ant colony optimization is used when determining the shortest route for each cluster. The solution of MMTSP is calculated from the sum of the shortest routes for these clusters. We will use data samples from TSPLIB for our implementation. The results of the simulation show that agglomerative clustering ACO algorithms take longer to compute than K-means clustering ACO and standalone ACO algorithms; on the other hand, they yield superior results than the other two. These results will also be compared with results obtained from prior research.