A Parallel Tabu Search Algorithm Based on Partitioning Principle

We presented a parallel tabu search (PTS) algorithm for the traveling salesman problem (TSP), which is NP-hard. To parallelize tabu search (TS) algorithm efficiently, the search space decomposition based on partition principle was used to balance the computing load, while exploitation in subspace had been boosted by an adaptive search strategy of intensification and diversification. Numerical results illustrated this algorithm was efficient and easy to implement. Key words: Parallel Tabu Search, Meta-heuristic, TS