Article ID: | iaor20003074 |
Country: | United States |
Volume: | 2 |
Issue: | 3 |
Start Page Number: | 187 |
End Page Number: | 200 |
Publication Date: | Jul 1996 |
Journal: | Journal of Heuristics |
Authors: | Laporte Gilbert, Potvin Jean-Yves, Quilleret Florence |
Keywords: | 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 from a new starting solution (in a manner reminiscent of genetic algorithms). Computational results are reported on sets of Euclidean problems with different characteristics.