中文摘要：

在网络设计当中，经济指标永远是网络设计者追求的最重要的目标之一。而网络设计中诸多的约束条件的限制，使得寻求这一目标的最优解的过程变得尤为复杂。网络设计经济综合优化问题(NES- - - - Network Economic Synthesis) 正是针对网络设计的这一目标而建立的模型。它在综合考虑网络设计中诸如流量需求、点次(Node Degree)、跃限(Hop Limit)、边容量等约束条件的

结论摘要：

在网络设计当中，经济指标永远是网络设计者追求的最重要的目标之一。而网络设计中诸多约束条件的限制，使得寻求这一目标的最优解的过程变得尤为复杂。网络设计经济综合优化问题 (NES- - - - Network Economic Synthesis) 正是针对网络设计的这一目标而建立的模型。CMST问题是NES中的最基础的问题，是组合优化问题中最基础的问题之一，也是NP-hard问题中的经典问题之一。该问题的研究在网络综合优化领域，和计算方法研究领域都具有重要的理论和实际意义。本项目开展了对NES中CMST问题的精确算法与启发式算法两方面的研究。通过本项目的研究，在精确算法方面，提出了新的分支定界算法，大大提高了原有算法的效率，保持了在该问题的精确算法研究上的国际领先地位；在启发式算法研究方面，提出的子树移动搜索算法，对TC类CMST问题，算法效率也已经大大超越先前已有的工作。