Tabu Search on the Geometric Traveling Salesman Problem

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review


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.
Original languageEnglish
Title of host publicationMeta-heuristics
Subtitle of host publicationTheory and Applications
Place of PublicationBoston
PublisherSpringer US
Number of pages17
ISBN (Electronic)978-1-4613-1361-8
ISBN (Print)978-0-7923-9700-7
Publication statusPublished - 1996


  • Combinatorial optimization
  • heuristics
  • local search
  • tabu search
  • traveling salesman problem


Dive into the research topics of 'Tabu Search on the Geometric Traveling Salesman Problem'. Together they form a unique fingerprint.

Cite this