Local Search based on a New Neighborhood for Routing and Wavelength Assignment
- Resource Type
- Conference
- Authors
- Fang, Yuan; Lu, Zhipeng; Su, Zhouxing; Wang, Yang; Zhang, TianCheng; Zhang, Qingyun
- Source
- 2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC) Systems, Man, and Cybernetics (SMC), 2020 IEEE International Conference on. :1123-1128 Oct, 2020
- Subject
- Engineering Profession
General Topics for Engineers
Robotics and Control Systems
Signal Processing and Analysis
Transportation
Wavelength assignment
Conferences
WDM networks
Routing
Search problems
Synthetic aperture sonar
Cybernetics
- Language
- ISSN
- 2577-1655
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.