A tabu search heuristic for the generalized minimum spanning tree problem


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

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, cilt.191, ss.306-319, 2008 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 191 Konu: 2
  • Basım Tarihi: 2008
  • Doi Numarası: 10.1016/j.ejor.2007.08.021
  • Dergi Adı: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Sayfa Sayıları: ss.306-319

Ö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.