题目：CMST问题混合优化算法的研究与实现

在人类的生产和生活实践中，基于对效率、质量、资源利用率、经济性等方面的追求，人们提出了众多的优化问题，其中很多问题都可以用网络模型来表达。网络设计经济综合优化问题 (NES----Network Economic Synthesis)是网络设计研究中的基础问题之一，它是在综合考虑网络设计中诸多约束条件下，寻求经济指标的最优化；而满足网络流量需求的树解（Capacitated Minimum Spanning Tree--CMST）作为NES一个重要的子问题则被认为是网络设计基础中的基础。目前国内外针对CMST的算法主要分为精确算法、启发式算法和下界算法三类，本论文主要研究CMST问题精确算法和启发式算法。在精确算法方面，基于点的分支定界算法[23]是目前计算效率最高的精确算法，本文从下界值的计算方法，搜索树的搜索规则和候选边的排序规则等方面对其进行了改进，实现了增强型的基于点的分支定界算法，对标准例题的计算结果表明算法的计算性能较原算法[23]有了显著的提高。在启发式算法方面，本文主要针对邻近搜索算法进行研究，通过分析CMST问题最优解的特征，提出了一种新的邻近搜索算法，并在此算法的基础上加入GRASP、禁忌等算法规则，使其成为一种混合的优化算法，并将其对标准例题的计算结果跟现在存在几种主流的启发式算法进行了比较，结果表明该算法是一种性能出色的启发式算法。论文工作的贡献主要体现在如下几个方面：1). 提出了新的下界值的计算方法和搜索树的搜索规则，在此基础上设计实现了增强型的基于点的分支定界算法，成为首个能计算出41节点TE类问题最优解的精确算法。2). 提出了一种新的邻居结构，设计了新的基于随机EW算法的初始解算法，在此基础上研究实现了一种解决CMST问题的邻近搜索算法，该算法可以在更短的时间内解决41节点规模的问题。3). 将GRASP、禁忌算法等算法思想融入到新设计的邻近搜索算法中，从而实现了一种综合多种算法策略的CMST问题混合优化算法，进一步提高了算法的性能，使算法对于各类标准例题均表现出很好的性能。