A GRASP heuristic for the capacitated minimum spanning tree problem using a memory-based local search strategy

Mauricio C. Souza (mauricioflamengo.isima.fr)
Christophe Duhamel (Christophe.Duhamelisima.fr)
Celso C. Ribeiro (celsoinf.puc-rio.br)

Abstract: We describe a new neighborhood structure for the capacitated minimum spanning tree problem. This neighborhood structure is used by a local search strategy, leading to good trade-offs between solution quality and computation time. We also propose a GRASP with path-relinking heuristic. It uses a randomized version of a savings heuristic in the construction phase and an extension of the above local search strategy, incorporating some short term memory elements of tabu search. Computational results on benchmark problems illustrate the effectiveness of this approach, which is competitive with the best heuristics in the literature in terms of solution quality. The GRASP heuristic using a memory-based local search strategy improved the best known solution for some of the largest benchmark problem.

Keywords: Capacitated minimum spanning tree, metaheuristics, local search, GRASP

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Combinatorial Optimization (Graphs and Matroids )

Citation: Research report, Catholic University of Rio de Janeiro, Department of Computer Science, Rio de Janeiro (Brazil), February 2002.

Download: [Postscript]

Entry Submitted: 03/10/2002
Entry Accepted: 03/11/2002
Entry Last Modified: 03/10/2002

Modify/Update this entry