A Study Of Approach To Solve The TSP Based On Delaunay Triangulation

TSP is not only a typical combinatorial optimization problem, but also a NP-hard problem,which is easy-to-describe but difficult to deal with. For a long time, people have been looking for an efficient, fast approximation algorithm to solve a Large-scale problem accurately in a reasonable time. So far, a lot of efficient and practical algorithms have been designed and the ant colony system is one of the better performance and the most representative algorithm.This article will mainly study the solution of TSP based on Delaunay triangulation. To solve the shortcomings of the classical algorithms, which are solving slow and low accuracy, this paper giving a solution:made use of the good characteristics of Delaunay triangulation to determine candidate set strategy, give an improved algorithm, using the MAX-MIN ant colony system to avoid falling into the local search, and use the technologies:reconstruction through the use of 2-options for solving path, improving the update method of pheromone and optimizing the preferences to further improve the performance of the algorithm.To verify the algorithm performance, this paper use the TSPLIB experimental data to compare and analyse the running results of the improved algorithm proposed in this paper, basic ant colony system, MAX-MIN ant colony system, dynamic adaptive ant colony system. The results show that the performance of the improved algorithm proposed in this paper is relative optimum, for some specific TSP, the algorithm can obtain an optimal solution,by an instance of TSP, using the matlab simulation to verify the effectiveness of the improved algorithm.