A tabu search heuristic for the generalized minimum spanning tree problem

ÖNCAN T., Cordeau J., Laporte G.

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, cilt.191, sa.2, ss.306-319, 2008 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 191 Sayı: 2
  • Basım Tarihi: 2008
  • Doi Numarası: 10.1016/j.ejor.2007.08.021
  • Dergi Adı: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.306-319
  • Galatasaray Üniversitesi Adresli: Evet

Özet

This paper describes an attribute based tabu search heuristic for the generalized minimum spanning tree problem (GMSTP) known to be NP-hard. Given a graph whose vertex set is partitioned into clusters, the GMSTP consists of designing a minimum cost tree spanning all clusters. An attribute based tabu search heuristic employing new neighborhoods is proposed. An extended set of TSPLIB test instances for the GMSTP is generated and the heuristic is compared with recently proposed genetic algorithms. The proposed heuristic yields the best results for all instances. Moreover, an adaptation of the tabu search algorithm is proposed for a variation of the GMSTP in which each cluster must be spanned at least once. (C) 2007 Elsevier B.V. All rights reserved.