A hybrid heuristic for the diameter constrained minimum spanning tree problem

Abilio Lucena 1 Celso Ribeiro 2 Andréa Cynthia Santos 3
1 Departamento de Administração and Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brasil
2 Fluminense Federal University [Niterói]
3 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
ICD - Institut Charles Delaunay
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.
Keywords : GRASP Heuristics Iterated local search Spanning trees Diameter constrained spanning trees
Document type :
Journal articles
Complete list of metadatas
https://hal-utt.archives-ouvertes.fr/hal-02291651
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Thursday, September 19, 2019 - 9:58:02 AM
Last modification on : Wednesday, February 12, 2020 - 4:52:29 PM

Links full text

istex

Identifiers

Collections

CNRS | ROSAS | UTT

Citation

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

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

23

Contact

Informations

CCSD