A tabu search heuristic for the generalized minimum spanning tree problem


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

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, vol.191, no.2, pp.306-319, 2008 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 191 Issue: 2
  • Publication Date: 2008
  • Doi Number: 10.1016/j.ejor.2007.08.021
  • Title of Journal : EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
  • Page Numbers: pp.306-319

Abstract

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.