USING ITERATED TABU SEARCH FOR THE TRAVELING SALESMAN PROBLEM

Abstract

In this paper, we propose an iterated tabu search (ITS) algorithm for the well-known combinatorial optimization problem, the traveling salesman problem (TSP). ITS is based on so-called intensification (improvement) and diversification (reconstruction) (I&D) paradigm. The goal of the intensification is the search for a locally optimal solution in the neighbourhood of the current solution. The diversification is responsible for escaping from the current local optimum and moving towards new regions in the solution space. Using the limited standard tabu search (TS) in the role of an effective intensification (local improvement) procedure resulted in promising solutions obtained during the experimentation with a number of the test data from the library of TSP instances TSPLIB. The results show that the proposed variant of ITS outperforms both the straightforward TS algorithm and the other heuristic algorithms tested.