ITERATED TABU SEARCH FOR THE TRAVELING SALESMAN PROBLEM: NEW RESULTS

Abstract

In this paper, we present some new results obtained for the traveling salesman problem (TSP) by using the iterated tabu search (ITS) meta-heuristic. ITS is a promising extension to the ordinary tabu search scheme. It seeks near-optimal solutions by combining intensification (standard tabu search) and diversification (perturbation of solutions) in a proper way. For the TSP, the main effect is achieved due to decomposition of the solution neighbourhood structure and considerably speeding-up the tabu search process, which is used, namely, in the role of intensification. This fast-iterated tabu search (FITS) technique resulted in quite encouraging solutions for the TSP instances from the TSP instance library TSPLIB. FITS obviously outperformed the other heuristic algorithms used in the experimentation, especially, on the smaller TSP instances.