Title: Comparison of heuristics for the colourful travelling salesman problem

 

Author: 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

 

Journal: Int. J. of Metaheuristics, 2013 Vol.2, No.2, pp.141 - 173

 

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: http://dx.doi.org/10.1504/IJMHEUR.2013.054143

 

Available online 23 May 2013

 

 

Editors Full Text AccessAccess for SubscribersPurchase this articleComment on this article