Skip to main navigation Skip to search Skip to main content

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

  • Yuan Fang
  • , Zhipeng Lü
  • , Zhouxing Su
  • , Yang Wang
  • , TianCheng Zhang
  • , Qingyun Zhang

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

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.
Original languageEnglish
Title of host publication2020 IEEE International Conference on Systems, Man, and Cybernetics
Subtitle of host publicationFinal Program and Conference Digest
PublisherIEEE
Pages1123-1128
Number of pages6
ISBN (Electronic)9781728185262
ISBN (Print)9781728185279
DOIs
Publication statusPublished - 2020
Externally publishedYes
Event2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC 2020): Human-Centered Systems for Smart and Connected Communities and Infrastructures - Virtual, Toronto, Canada
Duration: 11 Oct 2020 → 14 Oct 2020

Publication series

NameConference Proceedings - IEEE International Conference on Systems, Man and Cybernetics
Volume2020-October
ISSN (Print)1062-922X
ISSN (Electronic)2577-1655

Conference

Conference2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC 2020)
Abbreviated titleIEEE SMC 2020
PlaceCanada
CityToronto
Period11/10/20 → 14/10/20

Fingerprint

Dive into the research topics of 'Local Search based on a New Neighborhood for Routing and Wavelength Assignment'. Together they form a unique fingerprint.

Cite this