光网络规划流量疏导优化

Traffic grooming problem is one of the most challenging problems in the next generation optical network planning based on mesh WDM networks. In theory, traffic grooming problem has proven to be NP-hard, which consists of several important combinatorial optimization problems, such as bin packing, routing, constraint satisfaction and so on. Meanwhile, traffic grooming problem has a wide range of applications in air traffic grooming, city traffic management and so on. Therefore, it is of significance in both theory and practice to design effective optimiation algorithms for solving the traffic grooming optimization problems in WDM networks. This project will study the effective and efficient optimization algorithms for solving the traffic grooming problem arsing from real world applications. It mainly includes: 1) Study the initial solution generation method and effective local search algorithms for the traffic grooming problem; 2) By combining intensification-based local search algorithms and diversification-based evolutionary algorithms, we study hybrid evolutionary algorithms for solving the traffic grooming problem; 3) Study lower-bound algorithms for the traffic grooming problem, so as to assess the performance of the upper-bounds metaheuristics algorithms. The outcomes produced in this project can be directly applied to the optical network planning in our domestic telecommunication companies. Moreover, this research can deepen our understandings for challening NP-hard problems and other traffic grooming optimization problems.

流量疏导问题是下一代光网络规划的核心挑战性难题。在理论上，流量疏导问题已被证明为NP难度问题，它结合了多个组合优化问题，如装箱问题，路由问题，约束满足问题等。同时，流量疏导问题在航空流量控制、城市交通流量管理等领域有着广泛的应用。因此，设计求解流量疏导问题的高效优化算法具有重要的实际意义和理论价值。本课题拟研究来自通信公司的真实的光网络流量疏导问题的优化算法。研究工作主要包括：1）研究光网络规划流量疏导问题的初始解生成算法和高效局部搜索算法；2）将局部搜索算法和进化算法相结合，借助局部搜索的局部搜索能力和进化算法的全局寻优能力，研究求解光网络规划流量疏导问题的混合进化算法；3）采用松弛和划分的策略，研究求解光网络规划流量疏导问题的下界算法，以评估启发式优化算法的性能。本课题的研究成果可直接应用于国内通信公司的光网络规划，同时加深我们对挑战性NP难度问题及其它流量疏导问题的理解和研究。

流量疏导问题是下一代光网络规划的核心挑战性难题。在理论上，流量疏导问题已被证明为NP难度问题，它结合了多个组合优化问题，如装箱问题，路由问题，约束满足问题等。同时，流量疏导问题在航空流量控制、传感器网络规划、城市交通流量管理等领域有着广泛的应用。因此，设计求解流量疏导问题的高效优化算法具有重要的实际意义和理论价值。本课题研究了来自通信公司的真实的光网络流量疏导问题的优化算法。研究成果主要包括：1）结合我国通信公司（如华为）的具体业务场景，首次提出了光网络规划流量疏导问题的数学模型，并提出了求解该问题的初始解生成算法和高效局部搜索算法。在此基础上，将局部搜索算法和精确算法相结合，借助启发式算法的全局搜索能力和精确算法的局部寻优能力，研究求解光网络规划流量疏导问题的混合数学启发式算法。通过与当前国际文献中的最好的算法结果进行详细地对比和分析，表明了所提出的算法在优度和效率两方面的优势。2）研究了若干网络规划流量疏导问题及与其紧密相关的子问题、如最小连通支配集问题、多维二次背包问题、负载均衡问题、路由和波长分配问题等。这些子问题是解决光网络规划流量疏导问题的瓶颈所在，对其求解具有重要的理论意义和实际价值。对于这些相关的子问题，分别设计了求解它们的高效启发式优化算法，与当前文献中最好结果进行了详细的对比，表明所提出的算法的有效性。特别地，本项目中所提出的算法对以上问题均改进了若干国际文献中的最好结果。3）参加了与本项目相关的两个国际算法竞赛——2016年ROADEF/EURO库存路由配送问题挑战赛以及2017年SAT国际竞赛，并分别获得了全球第三名和全球第一名的成绩。本课题的研究成果可直接应用于国内通信公司的光网络规划，同时加深我们对挑战性NP难度问题及其它流量疏导问题的理解和研究。