路径交叉检测与消除方法和邻节点置换方法改进TSP的解

Improve solution of TSP based on route-intersection inspection and elimination method and neighbor nodes interchanging method

针对当前算法在求解规模较大的TSP时得到的近似解中常常存在路径交叉这一不足,提出了一种路径交叉检测与消除方法,可以完全消除路径交叉从而提高近似解的质量;通过分析近似解的结构,发现一些相邻节点相互交换位置也可以有效提高解的质量,因此提出了一种邻节点置换方法。实验表明提出的方法可以有效改进模拟退火算法求得的TSP近似解。

There often was route-intersection in approximate solutions obtained by current algorithms when solving TSP,this paper proposed a new route-intersection inspection and elimination method,which could eliminate route-intersection completely and improve the quality of the solution of TSP markedly.Through analyzing the structure of the approximate solution,found that interchanging some neighbor nodes could also improve the solution effectively.Therefore,proposed a neighbor nodes interchanging method.Simulation results show that the methods proposed can make the solution first resolved by simulated annealing algorithm much better.