A Parallel Adaptive Tabu Search Approach for Traveling Salesman Problems

TSP (traveling salesman problem) is one of the typical combinatorial optimization problems, which is NP-hard. It is widely believed that there is no efficient polynomial time algorithm that can solve it accurately. On the other hand, this problem is very important since it has many applications in practice. It has been verified that TS (tabu search) is one of the meta-heuristic algorithms that can solve this problem satisfied. With the requirement of solving large-scale problems, we presented a new parallel tabu search (PTS) approach, which was cooperated with genetic crossover operation, for TSPs. In addition, a novel adaptive search strategy of intensification and diversification in TS was proposed to improve the solving quality and efficiency. Through computational experiment, it is showed that our proposed PTS is feasible and effective.