The multi traveling salesman problem is the extension of the well-known problem of traveling salesman and considered as a NP-Complete problem having exponential solution space. MTSP is more complicated than TSP, because in MTSP first the cities must be divided between salesmen, and then the optimal order of cities for each traveling salesman should be determined. By looking at early studies, it is revealed that researchers had focused on MTSP less than TSP, and few studies have been done in this area so far. In this paper a new combinatorial algorithm named CGA-MTSP is proposed for solving MTSP problem which is a combination of Genetic Algorithm and Clustering Technique. The aim of this method is to reduce the travelled distance by salesmen. In the proposed method the Clustering Technique has been used intelligently to reduce the solution space of the mentioned problem. Experimental results show that the proposed algorithm (CGA-MTSP) leads to better results than other algorithms, but it requires more execution time.
展开▼
