Abstract: Due to the rapid development of application fields such as modern logistics industry,the multiple traveling salesman problem has attracted more and more attention.Thus,for the multiple traveling salesman problem with multiple depots and closed paths(MMTSP),this paper proposes a fuzzy C-means clustering based partheno-genetic algorithm (FCMPGA).The algorithm firstly uses the fuzzy C-means clustering method to classify all cities into several classes according to their subordinative degrees,and then establishes a corresponding traveling salesman problem for each class and solve it using an improved partheno-genetic algorithm.Finally,the results for each class are combined together to form a solution of the MMTSP.The solution strategy adopted in the proposed algorithm,which performs clustering prior to genetic operations,can not only greatly reduce the search space of the algorithm,but also make the reduced search space be explored more adequately and thereby obtain optimal solutions of the problems more quickly.Compared with several other related algorithms,the experimental results of a number of test instances in the TSPLIB database show that FCMPGA exhibits overall good performance on all test instances of different sizes,and especially on large-scale problems,the performance of the algorithm is better and its convergence speed is faster.

Key words: Fuzzy C-means clustering, Multiple traveling salesman problem, Partheno-genetic algorithm, Traveling salesman pro-blem