A Multilevel Approach for the Routing and Wavelength Assignment Problem
- Resource Type
- Conference
- Authors
- Fischer, Thomas; Bauer, Kerstin; Merz, Peter
- Source
- 2008 International Symposium on Applications and the Internet Applications and the Internet, 2008. SAINT 2008. International Symposium on. :225-228 Jul, 2008
- Subject
- Computing and Processing
Communication, Networking and Broadcast Technologies
Routing
Wavelength assignment
Optical fiber networks
Construction industry
Distributed algorithms
Wavelength division multiplexing
Optical fiber communication
Routing and Wavelength Assignment Problem
Multilevel Approach
Iterated Local Search
- Language
In this paper we present a multilevel approach for the static Routing and Wavelength Assignment (RWA) problem. The RWA deals with the problem of assigning paths and wavelengths to requests in optical communication networks. The multilevel approach is a general solution strategy involving stepwise coarsening the original problem instance, solving a simplified instance and expanding the solution back to the original size.We propose both a multilevel-inspired construction heuristic and a multilevel algorithm using iterated local search for refinement. These algorithms significantly improve previous approaches regarding time consumption and solution quality for large instances.