K-means Clustering Algorithm and Meta-heuristics for Multiple Traveling Salesman Problems

Vol.4 No.2

Year: 2009

Issue: October - December

Title: K-means Clustering Algorithm and Meta-heuristics for Multiple Traveling Salesman Problems   

Author Name: R. Nallusamy, K. Duraiswamy , R. Dhanalaksmi , P. Parthiban   

Synopsis:   

This paper deals with generating of an optimized route for multiple Travelling Salesman Problem (mTSP). We used a methodology of clustering the given cities depending upon the number of salesman and each cluster is allotted to a salesman. “K- Means clustering” algorithm has been used for easy clustering of the cities. In this way the mTSP has been converted into TSP which is simple in computation compared to mTSP. After clustering, an optimized route is generated for each salesman in his allotted cluster. Once the clustering had been done and after the cities were allocated to the various salesmen, each cluster/tour was taken as an individual Traveling Salesman problem (TSP) and the steps of Genetic Algorithm(GA) were applied to the cluster and iterated to obtain the most optimal value of the distance after convergence takes place. Now every cluster was again solved as a TSP by applying the Ant Colony Optimization (ACO) algorithm to determine the optimal distance value. The algorithms were simulated and executed in “MATLAB” software. After the application of both the heuristic techniques, it was found that the Ant Colony Optimization algorithm gave a better result and a more optimal tour for small size mTSPs in short computational time than Genetic Algorithm due to the extensive search and constructive nature of the algorithm.