Title: Comparison of heuristics for the colourful travelling salesman problem

Authors: J. Silberholz; A. Raiconi; R. Cerulli; M. Gentili; B. Golden; S. Chen

Addresses: Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA, 02139, USA ' Department of Mathematics, University of Salerno, P.te Don Melillo, 84084 Fisciano (SA), Italy ' Department of Mathematics, University of Salerno, P.te Don Melillo, 84084 Fisciano (SA), Italy ' Department of Mathematics, University of Salerno, P.te Don Melillo, 84084 Fisciano (SA), Italy ' R.H. Smith School of Business, University of Maryland, College Park, MD 20742, USA ' College of Business, Murray State University, Murray, KY 42071, USA

Abstract: In the colourful travelling salesman problem (CTSP), given a graph G with a (not necessarily distinct) label (colour) assigned to each edge, a Hamiltonian tour with the minimum number of different labels is sought. The problem is a variant of the well-known Hamiltonian cycle problem and has potential applications in telecommunication networks, optical networks, and multimodal transportation networks, in which one aims to ensure connectivity or other properties by means of a limited number of connection types. We propose two new heuristics based on the deconstruction of a Hamiltonian tour into subpaths and their reconstruction into a new tour, as well as an adaptation of an existing approach. Extensive experimentation shows the effectiveness of the proposed approaches.

Keywords: genetic algorithms; Hamiltonian tour; metaheuristics; colourful TSP; travelling salesman problem; CTSP; telecommunication networks; optical networks; multimodal transport networks.

DOI: 10.1504/IJMHEUR.2013.054143

International Journal of Metaheuristics, 2013 Vol.2 No.2, pp.141 - 173

Received: 10 May 2012
Accepted: 21 Dec 2012
Published online: 05 Jul 2014 *

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