用嵌套插队算法解决旅行推销员问题

提出了一种求解TSP问题的近似算法--嵌套插队算法.这种算法结合了启发式算法和随机化算法以及局 部寻优的思想。实验结果表明对于较小规模的TSP问题,直接用插队算法(QJA)就能以很大的概率获得已知最优 解。对于规模较大的TSP问题,嵌套插队算法(NQJA)能获得质量高于著名的启发式算法的解。另外，用嵌套插队 算法找到的China144的最短路径优于目前已知的最短路径。嵌套插队算法是专门针对TSP问题而提出的，但其思 想也可以给求解其他NP难解的组合优化问题以启发。

Nested Queue-Jumping Algorithm for Solving TSP

This paper presents a new approximate algorithm Nested Queue-Jumping Algorithm (NQJA) to solve traveling salesman problem. The proposed algorithm incorporates the thoughts of heuristic algorithm, randomized algorithm and local optimization. Numerical results show that to the small-scale instances, using Queue-Jumping Algorithm (QJA) directly the known optimal solution with a large probability can be obtained. In the case of large-scale instances, NQJA generates high-quality solution compared to well know heuristic methods. Moreover, the shortest tour to China144 TSP found by NQJA is shorter than known optimal tour. It can be a very promising alternative for finding a solution to the TSP. NQJA is specially devised for TSP. But its thought can give elicitation for other NP-hard combinatorial optimization problems.