A Heuristic Algorithm For Routing And Wavelength Assignment Problem

The routing and wavelength assignment problem(RWA)consists of assigning a wavelength to each lightpath and finding a feasible route for the lightpath,such that no two lightpaths assigned the same wavelength traverse the same link.The routing and wavelength assignment problem with minimum number of wavelength(min-RWA)is a variant of RWA,whose objective is to minimize the used wavelength of the network.This is a classic and challenging problem in wavelength-division multiplexing(WDM)optical networks,which is important for improving the utilization of network and has been shown to be NP-hard.Therefore,the research on this problem is both challenging and important.In this paper,a min-RWA problem is firstly transformed into a series of decision subproblems(k-RWA)and the original problem is solved by solving k-RWA problems.We present a new powerful neighborhood called Shift-Shaking(SS),which integrates a highlevel shift move to change the wavelength of one lightpath and two low-level ejection chainbased shaking(ECS)procedures to find the best routings for the related lightpaths.This new neighborhood is embedded into a simple iterated local search algorithm,called SS-ILS,for solving the k-RWA subproblem.In addition,to solve the problem that neighborhood search is too cumbersome,this paper proposes four acceleration strategies: neighborhood reduction,two-layer evaluation strategy,incremental evaluation technology and cache acceleration technology,which greatly improves the efficiency of the algorithm.Experimental results demonstrate that our proposed algorithm outperforms the best methods in the literature by improving the best known results for 22 out of 113 instances while matching the best known results for the remaining instances.In addition,this paper constructs four simplified versions of SS-ILS by disabling the main strategies in this paper.Compared with SS-ILS,the experimental results prove the effectiveness of these strategies.In sum,this paper proposes a new heuristic algorithm for the min-RWA problem.This algorithm solves the original problem by solving its subproblems.Meanwhile,it combines the new shift-shaking neighborhood and four acceleration strategies,which is a great improvement compared with previous algorithms.