旅行商问题（TSP）的模拟退火求解

提出了循环排序中６种不同的随机抽样方式，对旅行商问题（ＴＳＰ）的模拟退火求解进行了进一步深入研究．理论分析证明，６种抽样方式均满足模拟退火算法的全局收敛性条件．实例计算表明，子排列反序并移位抽样方式的求解寻优效率最高，且明显优于目前公认最好的著名的Ｓ．Ｌｉｎ“２－交换”抽样方法．本研究和结论对循环排序类优化问题及其求解具有普遍意义．

Solving the Travelling Salesman Problem by Simulated Annealing

This paper introduces six different random sampling methods for cycling permutations and carries out a further study of solving the travelling salesman problem by simulated annealing. The theoretical analyses prove that the sampling methods all satisfy the global convergence condition of the simulated annealing algorithm. The experimental evaluations show that the sampling method of reversing and moving a sub-permutation has a highest efficiency for solving and is superior to the well-known S. Lin' s 2-interchange method. The works and conclusions of the paper are available to a study of optimization problems with cycling permutation properties.