Comparison of heuristics for the colourful travelling salesman problem Online publication date: Sat, 05-Jul-2014
by J. Silberholz; A. Raiconi; R. Cerulli; M. Gentili; B. Golden; S. Chen
International Journal of Metaheuristics (IJMHEUR), Vol. 2, No. 2, 2013
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.
Online publication date: Sat, 05-Jul-2014
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Metaheuristics (IJMHEUR):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email firstname.lastname@example.org