Nested queue-jumping algorithm for Traveling Salesman Problem

Nested queue-jumping algorithm for Traveling Salesman Problem

0.00 Avg rating0 Votes
Article ID: iaor2005759
Country: China
Volume: 12
Issue: 4
Start Page Number: 49
End Page Number: 54
Publication Date: Aug 2003
Journal: Operations Research and Management Science
Authors: ,
Keywords: heuristics
Abstract:

This paper proposes a new approximate algorithm, the nested queue-jumping algorithm (NQJA), for traveling salesman problem. The proposed algorithm incorporates the ideas of heuristic algorithm, randomized algorithm and local optimization. Numerical results show that, 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 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. Nested queue-jumping algorithm is specially devised for TSP. But its concept can tackle other NP-hard combinatorial optimization problems.

Reviews

Required fields are marked *. Your email address will not be published.