Martin Zachariasen and Martin Dam

: 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. Key Words: Combinatorial optimization, heuristics, local search, tabu search, traveling salesman problem 1. Introduction The Traveling Salesman Problem (TSP) is probably the best known NP-hard problem of its genre: combinatorial optimization. Several approximation algorithms and heuristics exist for obtaining ..