A GRASP heuristic for the capacitated minimum spanning tree problem using a memory-based local search strategy
Mauricio C. Souza (mauricioflamengo.isima.fr)
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.
Entry Submitted: 03/10/2002
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|