Solving traveling salesman problem with nested queue-jumping algorithm
Donghai Zhai, Fan Jin · IEEE Transactions on Image Processing · 2004
We present a new approximate algorithm nested queue-jumping algorithm (NQJA) to solve the traveling salesman problem. The proposed algorithm incorporates the thoughts of heuristic algorithm, randomized algorithm and local optimization. Numerical results show that for the small-scale instances, using a queue-jumping algorithm (QJA) directly can obtain a known optimal solution with a large probability. In the case of large-scale instances, NQJA generates a high-quality solution compared to well know heuristic 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. NQJA is specially devised for TSP, But its thought can give elicitation for other NP-hard combinatorial optimization problems.