A novel GRASP based on mixed k-opt method for the Traveling Salesman Problem

摘要

Objective: A novel Greedy Randomized Adaptive Search Procedure was proposed in this paper to resolve the traveling salesman problem, which is proven to be NP-complete in most cases. Methods: The proposed novel algorithm has two phases. In the first phase the novel algorithm finds an initial solution of the problem with a proposed mergence feature greedy randomized method. In the second phase the expanded neighborhood adaptive search procedure was proposed to find the TSP solution. Results: The proposed algorithm was tested on numerous benchmark problems from TSPLIB. The algorithm is compared with other two algorithms and the results showed that the results of the proposed algorithm are always the best. The results were very satisfactory. Conclusion: For the majority of the instances the results were equal to the best known solution. The algorithm is suitable for the TSP. This kind of novel algorithm can be used for many aspects of object, especially for logistical problem.