Title: GRASP with hybrid heuristic-subproblem optimization for the multi-level capacitated minimum spanning tree problem
Authors: Martins, Alexandre X. *
Souza, Maurício C. *
Toffolo, TĂșlio A. M. * ×
Souza, Marcone J. F. #
Issue Date: 2-Apr-2009
Publisher: Kluwer Academic Publishers
Series Title: Journal of Heuristics vol:15 issue:2 pages:133-151
Abstract: We propose a GRASP using an hybrid heuristic-subproblem optimization approach for the Multi-Level Capacitated Minimum Spanning Tree (MLCMST) problem. The motivation behind such approach is that to evaluate moves rearranging the configuration of a subset of nodes may require to solve a smaller-sized MLCMST instance. We thus use heuristic rules to define, in both the construction and the local search phases, subproblems which are in turn solved exactly by employing an integer programming model. We report numerical results obtained on benchmark instances from the literature, showing the approach to be competitive in terms of solution quality. The proposed GRASP have in fact improved the best known upper bounds for almost all of the considered instances.
ISSN: 1381-1231
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Non-KU Leuven Association publications
* (joint) first author
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science