Multi traveling salesman problem has a wide range of application value in real life. The solution of this problem has attracted more and more scholars" attention. Information propagation algorithm is the most effective method for solving combinatorial optimization problems. Based on K-means clustering technology, an information propagation algorithm for solving multiple depots multiple traveling salesman problem (mmtsp) is proposed. The algorithm clusters the traveling salesman problem by K-means clustering algorithm to form several classes, For each class, the information propagation algorithm is used for traveling salesman search, and the search results of each class are synthesized to obtain the solution of mmtsp problem. The results show that the algorithm is better than other similar algorithms.