New hybrid heuristic algorithm for the clustered traveling salesman problem

In this study, we present a new hybrid heuristic algorithm for the Clustered Traveling Salesman Problem (CTSP). The CTSP is NP-hard because it includes the well-known Traveling Salesman Problem as a special case. In the CTSP, the vertices are partitioned into clusters and all the vertices of each cluster have to be visited contiguously. The algorithm is based on iterated metaheuristics, including local search, greedy randomized adaptive search procedure, and variable neighborhood random descent. Our new hybrid heuristic algorithm uses several variable neighborhood structures, which are selected in a random order. The new algorithm helps to intensify the search by using local search operators and diversification with a constructive heuristic and a perturbation method. The results of computational tests are reported for different classes of instances based on data with different levels of granularity, i.e., with different numbers of vertices and clusters. The results obtained by our new hybrid heuristic were compared with those produced using four previously reported heuristics and an exact method. The computational results demonstrate that the new hybrid heuristic obtained better results when it was compared with a hybrid heuristic that uses variable neighborhood descent. The new hybrid heuristic also outperformed previously described algorithms and it was competitive within a reasonable amount of computational time.