中文摘要：

旅行商问题是一个典型的组合优化问题,也是多种复杂问题的一种简化形式.因此,寻求一种有效的算法来求解此问题成为研究热点.随机松弛法是一种基于Metropolis迭代法求解的启发式随机搜索算法.针对该算法在求解旅行商问题时,存在易陷入局部最优的缺点,本文提出了三种不同的改进方法.即就是说,在解变换产生新解的过程中,首先,随机选择三个城市.然后,分别给出了三种不同的随机处理方法.最后,在仿真研究中,与已有方法相比,结果表明所给的三种方法的路径更短,结果更优.

英文摘要：

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.