Multiple Depots Multiple Traveling Salesman Problem is an extension of Traveling Salesman Problem. To solve this problem, a parallel K-means clustering simulated annealing algorithm based on Spark platform is proposed. The algorithm firstly classifies all the cities by k-means clustering algorithm, then establishes a traveling salesman problem for each class, and solves the traveling salesman problem by an improved simulated annealing algorithm. The MMTSP solution is calculated from the sum of the shortest paths of these classes. The proposed algorithm adopts the solution strategy of clustering first and then simulated annealing algorithm, which can greatly reduce the simulated annealing search space. Moreover, Spark platform can divide the clustering algorithm into several classes for parallel solution, so as to obtain the optimal solution of MMTSP problem faster. Several test instances in TSPLIB database are selected for simulation experiments, and the solution accuracy and running time are tested. The experiments are compared with other related algorithms. The experimental results show that, compared with the current FCMPGA, IPGA, IWO and other algorithms, the solution accuracy is improved by 5%~40%, and the solution efficiency is improved by 1~5 times compared with other algorithms, especially when the value of K is large.