Union search: a new meta-heurisic algorithm to the Traveling Salesman Problem

The traveling salesman problem (TSP) is one of the classic NP-hard combinatorial optimization problems. It has been the focus of computer science research to develop heuristics for this problem. By analyzing the characteristic of the union of local optima based on the statistical model of solutions, this paper indicates that the union of local optima contains most of the edges of global optimal and the size of the union is comparatively small. Thus, this paper takes the union as the candidate set, and proposes a new meta-heuristic called ‘union search’. Furthermore, the paper indicates that, in ample experiments of instances from TSPLIB, incorporating the meta-heuristic in the iterated Lin Kernighan and Lin Kernighan Hesgaun methods would improve dramatically the quality of solutions.