Tabu Search on the Geometric Traveling Salesman Problem

This paper presents a new tabu search approach for the geometric Traveling Salesman Problem. The use of complex TSP transitions in a tabu search context is investigated; among these transitions are the classical Lin-Kernighan transition and a new transition, called the Flower transition. The neighbourhood of the complex transitions is reduced strategically by using computational geometry forming a so-called variable candidate set of neighbouring solutions, the average quality of which controlled by a parameter. A new diversification method based on a notion of solution-distance is used. The experimental results are comparable to the best published results in the literature.