Optimization of Non-Linear Multiple Traveling Salesman Problem Using K-Means Clustering, Shrink Wrap Algorithm and Meta-Heuristics

Abstract

This paper deals with generating of an optimized route for multiple Traveling Sales- man Problems. We used a methodology of the given cities depending upon the num- ber of salesmen and each cluster is allotted to a salesman. -Means clustering algorithm has been used for easy of the cities. In this way the �� TSP 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. To achieve this, we first generated a parent route using Shrink Wrap algorithm and this parent string is further optimized by using two other optimizing algorithms. For this purpose, Search and were extensively used. From the results, we observed that Simulated Annealing generate optimized route covering less distance than Tabu search.