Comparison of heuristics for the colourful travelling salesman problem. (1st January 2013)

• Record Type: Journal Article
• Authors: Silberholz, J.; Raiconi, A.; Cerulli, R.; Gentili, M.; Golden, B.; Chen, S.
• Is Part Of: International journal of metaheuristics. Volume 2:Number 2(2013)
• Page Start: 141
• Page End: 173
• Publication Date: 2013-01-01
• Subjects: genetic algorithms -- Hamiltonian tour -- metaheuristics; Heuristic algorithms -- Periodicals; 006.3105
• Languages: English
• ISSNs: 1755-2176

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.