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.
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 *