摘要
本文提出了一种求解TSP问题的近似算法—嵌套插队算法。这种算法结合了启发式算法和随机化算法以及局部寻优的思想。实验结果表明对于较小规模的TSP问题,直接用插队算法(QJA)就能以很大的概率获得已知最优解。对于规模较大的问题实例,嵌套插队算法(NQJA)能获得质量高于著名的启发式算法的解。另外,用嵌套插队算法找到的China144的最短路径优于目前已知的最短路径。嵌套插队算法是专门针对TSP问题而提出的,但其思想也可以给求解其他NP难解的组合优化问题以启发。
This paper proposes a new approximate algorithm-nested queuejumping algorithm for traveling salesman problem.The proposed algorithm incorporates the thoughts of heuristic algorithm,randomized algorithm and local optimization.Numerical results show that, to the smallscale instances,using queuejumping algorithm directly can obtain the known best solution with a large probability.In the case of largescale instances,nested queuejumping algorithm generates highquality solution compared to wellknown huristic methods.Moreover,the shortest tour to China144 TSP found by NQJA is shorter than the known optimal tour.It can be a very promising alternative for finding a solution to the TSP.Nested queuejumping algorithm is specially devised for TSP.But its thought can elicit other NPhard combinatorial optimization problems.
出处
《运筹与管理》
CSCD
2003年第4期49-54,共6页
Operations Research and Management Science