Traveling salesman problem(TSP) is a classical combinatorial optimization problem. Moreover, it is also a predigested form of various complex problems. Consequently, it is a research hotspot that an effective algorithm is found to solve this problem. The stochastic relaxation method is a kind of heuristic random search algorithm based on Metropolis iteration method. In order to solve the problem of plunging into local optimum of the algorithm when solving TSP, this paper puts forward three kinds of different improved methods. Namely, during the process of producing new solutions in solution transformation, firstly, three cities are randomly selected. Then, three different processing methods are given, respectively. Finally, in simulation, compared with the existing method, the results show that the proposed three methods have shorter paths and better results.