A Study For WDM Network Design Problem With Traffic Grooming

This paper studies the network design problem,which is originally a classic problem in operations research and widely exists in the industrial production,such as urban road network design problem,transmission network layout problem,etc.With the rapid development of Internet technology,a kind of WDM network design problem appears in people's view.Two problems often occur in WDM network designing: designing a network to minimize the cost,and grooming traffic to maximize the channel utilization in the traffic network.However,in the real world,these two problems are often dealt with simultaneously,which is called the network design problem with traffic grooming.The network design problem is a kind of classic NP-hard problem,like the maximum clique problem and the travelling salesman problem.In practical applications,the scale of the problem is very large,and the general solver can not give a good solution.This problem is originated from the practical application scenario of the communication companies.But due to the complexity of the problem structure,there is little research in the academic society.This paper first gives the mathematical formula and model of the network design problem,and then proposes a new meta-heuristic algorithm framework,which is an iterative local search algorithm based on two-level structure.The upper structure is used to adjust the structure of network topology,and the lower structure used for traffic grooming.For this local search framework,a novel neighborhood structure based on tree search and a fast evaluation method are proposed,which not only improves the search efficiency of the algorithm,but also provides a new perspective to the neighborhood structure of the design problem.Finally,two disturbance techniques,flow disturbance and topology disturbance,are proposed to improve the diversification of the algorithm framework.In this paper,the lower bound method of NDG problem is proposed,and the lower bound of NDG problem is calculated successfully according to the method.The benchmarks in this paper are divided into two groups according to the scale.Among them,the large-scale cases originate from the practical application scenario of communication companies.The algorithm proposed in this paper runs on all the cases,and the results are compared with the commercial software CPLEX.For small scale cases,the optimal solution can be obtained with less time than CPLEX.In large scale cases where CPLEX cannot be solved,high quality solutions close to lower bounds can be obtained,which verifies the effectiveness of the algorithm.