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

Authors: Abdullah Alsheddy

Addresses: Department of Computer Science, Al Imam Mohammad Ibn Saud Islamic University (IMSIU), Riyadh, 13318, Saudi Arabia

Abstract: 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).

Keywords: combinatorial optimisation; metaheuristics; clustered travelling salesman problem; GLS; guided local search.

DOI: 10.1504/IJMHEUR.2018.091882

International Journal of Metaheuristics, 2018 Vol.7 No.1, pp.80 - 92

Received: 13 Feb 2017
Accepted: 02 Nov 2017
Published online: 20 May 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article