A novel simple candidate set method for symmetric TSP and its application in MAX-MIN ant system

Traveling Salesman Problem (TSP) is a kind of typical NP problem and has been extensively researched in combinatorial optimization. For solving it more effectively, candidate set is used in many algorithms in order to limit the selecting range when choosing next city to move, such as in Ant Systems, or to initialize a local optimum solution, such as in Lin-Kernighan Heuristic (LKH) algorithm. A novel simple method for generating candidate set is proposed in this paper and applied into MAX-MIN Ant System (MMAS) for symmetric TSP problem. Experimental results show that it has better performance than other Ant Systems including MMAS. Moreover, this method can be used in other algorithms for symmetric TSP problem.