A Multilevel Approach for the Routing and Wavelength Assignment Problem

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.