Comparison of heuristics for the colourful travelling salesman problem
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.