The Structure Of The TSP Mining And Heuristic Design

The TSP (traveling salesman problem) is one of the typical NP-hard combinatorial optimization problems and has an extensive application background on traffic, networks, circuitry design and so on. According as computational complexity, there is no polynomial exact algorithm for NP-hard problems under the assumption P≠NP . Effective heuristics for the large-scale instance of TSP have been the hotline in research of computer science at all times. As the tool to describe the structure of the TSP, backbone and fat is essential for heuristic algorithm design.Firstly in this paper we presented and analyzed the research status of the TSP, and aimed at the lack of research of these tools which describe the structure of the TSP. Analyzing the fat computational complexity for the TSP. And then proving that it is NP-hard to obtain the fat of the TSP by construction of biased instances, i.e., there is no algorithm to get the full fat of the TSP in polynomial time under the assumption P≠NP . Furthermore, a new meta-heuristic—dynamic candidate set search (DCSS) was proposed by analysis of the relationship between local optimal solutions and the fat. And we applied the DCSS to improve the LKH, one of the best existing algorithms for the TSP.Then we analyzed the relation between the local optimal tour and the global optimal tour, and put forward a new tool to describe the construe of the TSP that was disturb-edge. We also proved that it was NP-hard to get the full disturb-edges on the assumption that constructing a polynomial algorithm. We got some edges which can simulate disturb-edge effectively by operating the local optimal tours. We defined these edges approximate disturb-edge in this paper. At last, we proposed a meta-heuristic algorithm frame based on approximate disturb-edge (MAFBOAD). And we implemented it on LKH.