题目：网络设计经济综合优化问题的算法研究

网络设计问题追求的重要目标之一是经济最优化，而实际的网络设计中存在的诸多约束条件的限制，使得寻求这一目标的最优解甚至是可行解的过程变得尤为复杂。网络设计经济综合优化问题（NES——Network Economic Synthesis）正是针对网络设计中的这一目标而建立的模型。它综合考虑网络设计中诸如流量需求、点次、跃限、边容量等约束条件，遵循建立在边上的权值函数，构建最优化的网络拓扑结构与流量安排，以期获得网络中所有边上的权值总和最小的问题的解。NES问题是网络设计优化研究中的基础问题之一，具有重要的理论和实际意义。本文分析了现存的NES问题启发式算法的优劣，从问题模型、精确算法和启发式算法三个方面展开研究工作。首先，本文在研究了NES问题的已有模型的基础上，提出了网络综合的流量分割模型，简化了原模型决策变量的复杂性，且进一步将原问题从理论上转化为单位流量需求的NES问题。其次，在精确算法方面，针对单位流量需求的NES问题，设计和实现了一种分支定界算法。本文从理论上证明了该分支定界算法寻求最优解的精确性，通过动态路径生成算法在实现上解决了算法指数级空间复杂度的问题，并从初始解、可行性检测、下界求解三个方面对搜索过程进行剪枝；进一步，利用拉格朗日松弛技术对建立在边上的容量约束进行松弛，并利用次梯度法对原问题的多维拉格朗日乘子问题进行求解，从而改进了下界。实验结果通过对比反映了分支定界算法的精确性，同时说明拉格朗日松弛技术为算法的精确求解过程带来了一定程度的性能优化。第三，在启发式算法方面，本文研究了蚁群算法在NES问题中的应用。摒弃了预计算路径技术，采用人工蚂蚁爬行构建解的思想，提出了面向蚂蚁子群的路径构建方式，并丰富了多轨信息素的启发方法，依照构建解路径的不同策略，设计和实现了求解NES问题的贪婪型蚁群算法和竞争型蚁群算法。实验结果通过对比表明，本文设计的蚁群算法相比于同类算法的已有最优成果在最优解质量上有了明显提高；进一步对随机数据的运行结果肯定了多轨信息素在算法寻优方面发挥的积极作用，以及竞争型蚁群算法在应对较大规模问题求解时的有效性。