重庆邮电学院学报(自然科学版)2003，Vol.15Issue(3)：51-56,6.
用嵌套插队算法解决旅行推销员问题
Nested Queue-Jumping Algorithm for Solving TSP
翟东海 1靳蕃1
作者信息
- 1. 西南交通大学,计算机与通信工程学院,成都,610031
- 折叠
摘要
Abstract
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.关键词
TSP问题/插队算法/嵌套插队算法/随机化算法Key words
traveling salesman problem/queue-jumping algorithm/nested queue-jumping algorithm/randomized algorithm分类
信息技术与安全科学引用本文复制引用
翟东海,靳蕃..用嵌套插队算法解决旅行推销员问题[J].重庆邮电学院学报(自然科学版),2003,15(3):51-56,6.
