A hybrid heuristic for the diameter constrained minimum spanning tree problem

A hybrid heuristic for the diameter constrained minimum spanning tree problem

0.00 Avg rating0 Votes
Article ID: iaor20101565
Volume: 46
Issue: 3
Start Page Number: 363
End Page Number: 381
Publication Date: Mar 2010
Journal: Journal of Global Optimization
Authors: , ,
Keywords: heuristics
Abstract:

We propose a hybrid GRASP and Iterated Local Search (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 Variable Neighborhood Descent (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.

Reviews

Required fields are marked *. Your email address will not be published.