A hybrid heuristic for the diameter constrained minimum spanning tree problem - Université de technologie de Troyes Access content directly
Journal Articles Journal of Global Optimization Year : 2010

A hybrid heuristic for the diameter constrained minimum spanning tree problem

Abstract

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.

Dates and versions

hal-02291651 , version 1 (19-09-2019)

Identifiers

Cite

Abilio Lucena, Celso Ribeiro, Andréa Cynthia Santos. A hybrid heuristic for the diameter constrained minimum spanning tree problem. Journal of Global Optimization, 2010, 46 (3), pp.363-381. ⟨10.1007/s10898-009-9430-2⟩. ⟨hal-02291651⟩

Collections

CNRS UTT LOSI
18 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More