TY - GEN
T1 - Local Search based on a New Neighborhood for Routing and Wavelength Assignment
AU - Fang, Yuan
AU - Lü, Zhipeng
AU - Su, Zhouxing
AU - Wang, Yang
AU - Zhang, TianCheng
AU - Zhang, Qingyun
PY - 2020
Y1 - 2020
N2 - 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. © 2020 IEEE.
AB - 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. © 2020 IEEE.
UR - https://www.scopus.com/pages/publications/85098868998
UR - https://www.scopus.com/pages/publications/85098868998#tab=impact
U2 - 10.1109/SMC42975.2020.9283031
DO - 10.1109/SMC42975.2020.9283031
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 9781728185279
T3 - Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics
SP - 1123
EP - 1128
BT - 2020 IEEE International Conference on Systems, Man, and Cybernetics
PB - IEEE
T2 - 2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC 2020)
Y2 - 11 October 2020 through 14 October 2020
ER -