Heuristic Algorithm For Routing And Wavelength Assignment Problem

Today fiber as a new information transmission medium has been widely applied to metropolitan networks or WAN and wavelength division multiplexing(WDM) is the common technology to improve the throughput of current fiber-optic network, it works by using the properties that different wavelengths don't interfere with each other, and thus we can use a variety of wavelengths to transmit services in the same fiber. In WDM transmission network, RWA has always been a hot research field of optical networks, which mainly refers to the scarce resources(wavelength) distribution and requirements set routing problem. Most currently available RWA related algorithms for solving large-scale network effect is not satisfactory, it cannot allocate wavelength resources reasonably under the given constraints as much as possible so that the resources will be fully utilized.The routing and wavelength assignment problem(RWA) has shown to be NP-hard if the wavelength continuity constraint and the objective of minimizing the number of wavelengths are considered. This paper introduces a multi-neighborhood based iterated tabu search algorithm(MN-ITS) to solve the min-RWA problem, this algorithm did not use a layered approach which other algorithms widely used. The Routing and wavelength assignment problem be placed under the same objective function considering, And the algorithm consists of three neighborhoods with a unified incremental evaluation method to evaluation objective function value. In the iterative local search process we also incorporate tabu search, disturbance and other strategies to improve the efficiency of the search algorithm.In order to verify the effect of our MN-ITS algorithm, we test the algorithm on most widely studied instances, and compare the algorithm with other algorithms. In the 88 test instances, our algorithm is able to calculate the lower bound of 55 instances, And Compared with current best algorithms-VND algorithm, we have six instances inferior to it, but there are five instances better than VND algorithm, which fully shows that our algorithms has a strong competitive.