A tabu search heuristic using genetic diversification for the clustered traveling salesman problem

Research paper by Gilbert Laporte, Jean-Yves Potvin, Florence Quilleret

Indexed on: 01 Dec '97Published on: 01 Dec '97Published in: Journal of Heuristics


The clustered traveling salesman problem is an extension of the classical traveling salesman problem where the set of vertices is partitioned into clusters. The objective is to find a least cost Hamiltonian cycle such that the vertices of each cluster are visited contiguously and the clusters are visited in a prespecified order. A tabu search heuristic is proposed to solve this problem. This algorithm periodically restarts its search by merging two elite solutions to form a new starting solution (in a manner reminiscent of genetic algorithms). Computational results are reported on sets of Euclidean problems with different characteristics.