Please use this identifier to cite or link to this item:
http://bura.brunel.ac.uk/handle/2438/1336
Title: | Solving the minimum labelling spanning tree problem using hybrid local search |
Authors: | Consoli, S Darby-Dowman, K Mladenović, N Moreno-Perez, J A |
Keywords: | Combinatorial optimization;Graphs and Networks;Local search;Minimum labelling spanning trees |
Issue Date: | 2007 |
Series/Report no.: | TR/02/07 |
Abstract: | 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 effective heuristics (Modified Genetic Algorithm (MGA) and Pilot Method (PILOT)) have been proposed and analyzed. A hybrid local search method, that we call Group-Swap Variable Neighbourhood Search (GS-VNS), is proposed in this paper. It is obtained by combining two classic metaheuristics: Variable Neighbourhood Search (VNS) and Simulated Annealing (SA). Computational experiments show that GS-VNS outperforms MGA and PILOT. Furthermore, a comparison with the results provided by an exact approach shows that we may quickly obtain optimal or near-optimal solutions with the proposed heuristic. |
URI: | http://bura.brunel.ac.uk/handle/2438/1336 |
Appears in Collections: | Publications Dept of Mathematics Research Papers Mathematical Sciences |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
GS-VNS.pdf | 354.36 kB | Adobe PDF | View/Open |
Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.