期刊文献+

用嵌套插队算法解决TSP问题 被引量:1

Nested Queue-jumping Algorithm for Traveling Salesman Problem
下载PDF
导出
摘要 本文提出了一种求解TSP问题的近似算法—嵌套插队算法。这种算法结合了启发式算法和随机化算法以及局部寻优的思想。实验结果表明对于较小规模的TSP问题,直接用插队算法(QJA)就能以很大的概率获得已知最优解。对于规模较大的问题实例,嵌套插队算法(NQJA)能获得质量高于著名的启发式算法的解。另外,用嵌套插队算法找到的China144的最短路径优于目前已知的最短路径。嵌套插队算法是专门针对TSP问题而提出的,但其思想也可以给求解其他NP难解的组合优化问题以启发。 This paper proposes a new approximate algorithm-nested queuejumping 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 smallscale instances,using queuejumping algorithm directly can obtain the known best solution with a large probability.In the case of largescale instances,nested queuejumping algorithm generates highquality solution compared to wellknown 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 queuejumping algorithm is specially devised for TSP.But its thought can elicit other NPhard combinatorial optimization problems.
作者 翟东海 靳蕃
出处 《运筹与管理》 CSCD 2003年第4期49-54,共6页 Operations Research and Management Science
关键词 嵌套插队算法 TSP问题 启发式算法 随机化算法 最短路径 最优解 组合优化 旅行商问题 traveling salesman problem queue-jumping algorithm nested queue-jumping algorithm randomized algorithm
  • 引文网络
  • 相关文献

参考文献5

二级参考文献16

  • 1周培德.几何算法求解货郎担问题[J].计算机研究与发展,1995,32(10):63-65. 被引量:9
  • 2周培德.货郎担问题的几何解法[J].软件学报,1995,6(7):420-424. 被引量:12
  • 3周培德,北京理工大学学报,1993年
  • 4周培德,算法设计与分析,1992年
  • 5靳蕃,神经网络与神经计算机,1991年
  • 6黄文奇,中国科学.E,1997年,27卷,2期,179页
  • 7陈国良,遗传算法及其应用,1996年
  • 8刘勇,非数值并行算法.2,1995年
  • 9靳蕃,神经网络与神经计算机,1991年
  • 10黄文奇,应用数学学报,1979年,2卷,2期,176页

共引文献48

同被引文献11

引证文献1

;
使用帮助 返回顶部