随着网络通信流量的急剧增大,光网络规划与建设的相关研究得到了越来越多的重视。由于与网络建设运营成本直接相关,光网络流量疏导规划成为光网络通信领域的核心问题之一。光网络流量疏导的几个子问题已被证明为NP难,且这些问题并没有与其完全对应的传统NP难问题,因此光网络流量疏导相关问题不论是在学术科研领域还是在实际生产工业界都是重要的具有挑战性的课题。由于光网络流量疏导相关问题的复杂性极高,即使是小规模算例也很难使用精确算法在短时间内进行求解。因此使用启发式算法,或启发式与精确算法的结合算法是求解该问题的唯一有效方法。元启发式算法被广泛用于求解复杂组合优化问题,是求解NP难问题的有力工具之一。本文的研究重点是设计高效的元启发式算法用于求解光网络流量疏导相关问题。同时,本文对所述算法的重要特性进行了分析与说明。本文的主要贡献有1.针对带流量疏导的网络设计问题以及带简单路约束的流量疏导与路由问题这两个真实工业运用上急需解决的问题,本文首次给出了它们的一般化数学模型,为问题研究奠定了基础。2.提出了用于求解带流量疏导的网络设计问题的混合精确禁忌算法(HETS)。算法具有以下特点。2.1算法将线性规划算法及整数线性规划算法作为子过程嵌入迭代的禁忌搜索算法。结合了规划算法的精确性以及禁忌搜索算法的高效性。2.2为该问题的子问题——流量疏导问题——给出了拥有良好松弛下界的整数线性规划模型。该模型求解速度快,且线性松弛解与整数解差异极小。2.3提出了基于边旋转邻域结构。该邻域结构通过选择适当的边进行操作以减少算法计算量,提高了搜索的有效性。同时针对该邻域结构提出了相应的快速评估技术,提高了搜索效率。该技术使用算法模型的线性松弛模型对邻域解进行估算。2.4使用带流量疏导的网络设计问题的22公共算例对HETS算法进行了测试,HETS改进了22个公共算例中21个算例的最优解,1个算例的解与当前最好解持平。且与文献引用算法对比,HETS的计算时间优势巨大。3.提出了用于求解带简单路约束的流量疏导与路由问题的自适应随机贪心算法(GRASP)。算法具有以下特点:3.1算法主构架由贪心构造过程与局部搜索优化过程迭代组成。其中局部搜索优化过程为多个局部搜索算法嵌套构成的复合局部搜索算法。3.2为算法上层局部搜索过程设计了带权复合信息目标函数,保证了子过程之间切换的连续性,使得它们之间的合作更为有效,提高了算法的求解优度和效率。3.3使用基于实际工程特性的随机算例集对算法进行了测试。与公共通用优化求解软件CPLEX和LocalSolver的结果进行对比,GRASP算法性能及优度远超通用求解软件,且GRASP算法能够求解通用求解器所不能求解的大规模算例。4.针对路由与波长分配问题,提出了多邻域迭代禁忌算法(MN-ITS)。算法具有以下特点:4.1为该算法提出了三种不同邻域结构以搜索不同的解空间,有效增大了算法的搜索范围。同时,为这三种邻域结构设计了统一的增量更新评估方案,使得算法能够平滑地在各邻域间进行切换。4.2使用路由与波长分配问题的88个公共算例对算法进行测试,并与其它文献中优秀算法进行了对比。MN-ITS能够求得W算例集中所有算例的最优解,以及42个Y算例的历史最优解。同时MN-ITS算法更新了Y算例集中5个算例的历史最优解。5.使用逻辑证明以及对比实验对本文所提算法进行了分析,解释说明了本文所提算法特性的思想原理,同时验证了这些特性的有效性与高效性。本文的研究为网络结构问题的数学建模给出了指导。同时本文为复杂优化问题的启发式求解算法设计指明了方向,其中包括如何对复杂问题进行邻域结构设计;如何有效对复杂邻域结构进行评估;如何对复杂问题进行拆分求解;如何协调各邻域结构使其有效合作;以及如何将精确算法与启发式算法相结合以获取这两种算法的优势。同时本文所述算法技术具有普适性,可尝试将其应用到其它类型相似结构的NP难优化问题中,以期望得到类似的改进效果。融合本文所述各算法可以开发出解决光网络流量疏导规划工程的系统。