Solving the minimum labelling spanning tree problem using hybrid local search

Given a connected, undirected graph whose edges are labelled (or coloured), the minimum labelling spanning tree (MLST) problem seeks a spanning tree whose edges have the smallest number of distinct labels (or colours). In recent work, the MLST problem has been shown to be NP-hard and some metaheuristics have been proposed and analyzed. A hybrid local search method is proposed in this paper. It is obtained by combining Variable Neighbourhood Search with Simulated Annealing. Computational experiments show that the proposed hybrid heuristic has high-quality performance for the MLST problem and it is able to obtain optimal or near-optimal solutions in short computational running time. © 2012 Elsevier B.V.