A hybrid heuristic for the diameter constrained minimum spanning tree problem

被引:20
作者
Lucena, Abilio [2 ]
Ribeiro, Celso C. [1 ]
Santos, Andrea C. [3 ]
机构
[1] Univ Fed Fluminense, Inst Comp, BR-24210240 Niteroi, RJ, Brazil
[2] Univ Fed Rio de Janeiro, BR-22290240 Rio De Janeiro, Brazil
[3] Univ Blaise Pascal, LIMOS, F-63173 Aubiere, France
关键词
Spanning trees; Diameter constrained spanning trees; Heuristics; GRASP; Iterated local search;
D O I
10.1007/s10898-009-9430-2
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We propose a hybrid GRASP and ILS based heuristic for the diameter constrained minimum spanning tree problem. The latter typically models network design applications where, under a given quality requirement, all vertices must be connected at minimum cost. An adaptation of the one time tree heuristic is used to build feasible diameter constrained spanning trees. Solutions thus obtained are then attempted to be improved through local search. Four different neighborhoods are investigated, in a scheme similar to VND. Upper bounds within 2% of optimality were obtained for problems in two test sets from the literature. Additionally, upper bounds stronger than those previously obtained in the literature are reported for OR-Library instances.
引用
收藏
页码:363 / 381
页数:19
相关论文
共 31 条
[1]  
ABDALLA A, 2001, THESIS U CENTRAL FLO
[2]  
Achuthan N., 1992, OPTIMIZATION TECHNIQ, V1, P297
[3]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[4]  
[Anonymous], 1994, AUST J COMB
[5]  
BALA K, 1993, IEEE INFOCOM SER, P1350, DOI 10.1109/INFCOM.1993.253399
[6]   OR-LIBRARY - DISTRIBUTING TEST PROBLEMS BY ELECTRONIC MAIL [J].
BEASLEY, JE .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1990, 41 (11) :1069-1072
[7]  
BOOKSTEIN A, 2001, INFORM SYST, V16, P110
[8]  
Deo N, 2000, LECT NOTES COMPUT SC, V1767, P17
[9]  
Duarte AR, 2007, LECT NOTES COMPUT SC, V3867, P158
[10]   A PROBABILISTIC HEURISTIC FOR A COMPUTATIONALLY DIFFICULT SET COVERING PROBLEM [J].
FEO, TA ;
RESENDE, MGC .
OPERATIONS RESEARCH LETTERS, 1989, 8 (02) :67-71