A tabu search heuristic for the generalized minimum spanning tree problem |
| |
| Authors: | Temel Öncan Jean-François Cordeau Gilbert Laporte |
| |
| Institution: | 1. Department of Industrial Engineering, Galatasaray University, Ortaköy, Istanbul 34357, Turkey;2. Canada Research Chair in Logistics and Transportation and Center for Research on Transportation, HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montréal, Canada H3T 2A7;3. Canada Research Chair in Distribution Management and Center for Research on Transportation, HEC Montréal, 3000 chemin de la Côte-Sainte-Catherine, Montréal, Canada H3T 2A7 |
| |
| 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. |
| |
| Keywords: | Generalized minimum spanning tree Tabu search |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
