TSP (Traveling Salesman Problem) is a typical combinational optimization problem. At present, there are a lot of methods to solve this problem, but with the increase of the scale of this problem, most methods face the difficult problem of "combination exploding". This paper combines Multi-Agent theory and MSM-PGA (Master-slaver Model Parallel Genetic Algorithm) together, form one MSM-PGA Multi-Agent union. This union solves the TSP by the coordination between many Agents inside the union. The introduction of Multi-Agent theory, make the master course and slave course of MSM-PGA to be made of Agent, so the ability of communication and coordination raise greatly, thus overcome the shortcoming of original MSM-PGA; And comparing with other methods solved TSP, the method of this paper has the fast computational speed and the high precision, and not only has overcome the difficult problem of "combination exploding" but also can get more optimal solving than other algorithms.