A two-phase local search algorithm for the ordered clustered travelling salesman problem

The ordered clustered travelling salesman problem (OCTSP) is an extension of the classical travelling salesman problem where the set of vertices is partitioned into clusters with a prespecified order. The objective is to find a minimum cost Hamiltonian tour such that the vertices in any cluster are visited contiguously and the clusters are visited in the given order. This paper proposes a two-phase approach using the 2-Opt heuristic and the guided local search (GLS) metaheuristic for obtaining approximate solutions of high-quality to the OCTSP. The first phase attempts to find an optimal Hamiltonian cycle for each cluster. The resulted cycles will be concatenated in the second phase, which then focuses on finding an optimal Hamiltonian cycle for the OCTSP. Computational results confirm the effectiveness of the proposed approach in terms of solution quality and computational time, in comparison with a hybrid genetic algorithm (HGA) on symmetric instances obtained from the travelling salesman problem instance library (TSPLIB).