Local Search based on a New Neighborhood for Routing and Wavelength Assignment

The routing and wavelength assignment (RWA) problem is a classic and challenging problem in wavelength-division multiplexing (WDM) optical networks and has shown to be NP-hard. This paper studies the min-RWA problem with the objective of minimizing the number of required wavelengths and presents a new powerful neighborhood called Shift-and-Shaking (SAS). The proposed SAS integrates a high-level shift move to change the wavelength of one lightpath and two low-level ejection chain-based 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 SAS-ILS, for solving min-RWA. The proposed SAS-ILS is tested on three sets of totally 113 widely studied instances in the literature. Comparison with other state-of-the-art algorithms shows that the SAS-ILS is able to improve 22 previous best known results, while matching the best known results for the remaining ones within short computational time.