A parallel tabu search algorithm for large traveling salesman problems

Tabu search is a general heuristic procedure for global optimization which has been successfully applied to several types of difficult combinatorial optimization problems (scheduling, graph coloring, etc.). Based on this technique, an efficient algorithm for getting almost optimal solutions of large traveling salesman problems is proposed. The algorithm uses the intermediate- and long-term memory concepts of tabu search as well as a new kind of move. Experimental results are presented for problems of 500-1000000 cities and a new estimation of the asymptotic normalized length of the shortest tour through points uniformly distributed in the unit square is given. Finally, as the algorithm is well suited for parallel computation, an implementation on a transputer network is described. Numerical results and speedups obtained show the efficiency of the parallel algorithm.