带有度约束的最小生成树问题存在于工业界的很多应用场景中,如电路芯片设计、通信工程、运输工程、管道工程、排水系统等领域。此外,带有度约束的最小生成树问题与很多重要的问题有着千丝万缕的关系,例如当生成树的度约束变得极为松弛时,该问题就转变成图论中常见的最小生成树问题;然而当生成树中的每一个顶点的度约束固定为2时,该问题则转变为经典的旅行商问题。从计算复杂度方面来讲,带有度约束的最小生成树问题已被证明为NP难度问题,因此不存在多项式时间复杂度的精确算法对其进行求解。本文将围绕求解有度约束的最小生成树问题的高效启发式算法展开研究。针对带有度约束的最小生成树问题的特殊问题结构,本文提出一种基于多目标的禁忌搜索算法对其进行求解。本文的主要工作和创新点包括:首先将关于度的硬约束条件转换为目标函数中的一级目标,使原问题转化为带有二级目标函数的最小生成树问题。其次,设计了基于边交换的邻域动作用于求解该问题。邻域动作每次尽可能改进目标函数中的一级目标或者二级目标,提高了算法的搜索效率。再次,提出了禁忌搜索策略,以达到搜索到全局最优解的目的。当满足解禁策略时,则采用解禁策略接受禁忌动作。最后,采用所提出了的二级目标函数的禁忌搜索算法对文献中248个标准算例进行了测试,表明了所提出的算法和策略的有效性。本文研究工作表明,对于带有度约束的最小生成树问题,采用将原始约束松驰到目标函数的方法、基于边交换的领域结构以及禁忌策略可以有效地求解该问题。同时,这些策略也可以用来求解其它具有NP难度的问题。