A Hybrid Optimization Algorithm for the CMST Problem  

作　　者：HAN Jun FANG Qingan MAO Liyong HUANG Yaling 

机构地区：[1]State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China

出　　处：《Chinese Journal of Electronics》2011年第4期583-589,共7页电子学报（英文版）

基　　金：This work is supported by the National Natural Science Foundation of China （No.90818028）, National Science and Technology Major Research Plan of China （No.2009ZX01043-002-004, No.2008ZX07528-004-01） and State Key Laboratory of Software Development Environment （No.SKLSDE-2010ZX-08）.

摘　　要：The Capacitated minimum spanning tree （CMST） problem is one of the most fundamental and significant problems in the optimal design of networks. It is also a classical combinatorial optimization problem which has been tackled by researchers for centuries using various methods. In this paper, a new NS-TS hybrid optimization algorithm that combines neighborhood search and tabu search is proposed. A novel neighborhood structure and associate tabu strategy is proposed and implemented. Computational experiments showing the effectiveness and efficiency of the algorithm on benchmark instances are given.

关 键 词：Capacitated minimum spanning tree （CMST） Neighbourhood structure Tabu search Rooted subtree. 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置] O224[自动化与计算机技术—控制科学与工程]