A tabu search algorithm for static routing and wavelength assignment problem

• Main Authors: Wang, Ying, Cheng, Tee Hiang, Lim, Meng-Hiot
• Other Authors: School of Electrical and Electronic Engineering
• Format: Article
• Language: English
• Published: 2010
• Subjects: DRNTU::Engineering::Electrical and electronic engineering::Computer hardware, software and systems
• Online Access: https://hdl.handle.net/10356/90761; http://hdl.handle.net/10220/6312
• Institution: Nanyang Technological University

Static routing and wavelength assignment (RWA) is usually formulated as an optimization problem with the objective of minimizing wavelength usage (MWU). Existing solution methodologies for the MWU problem are usually based on a two-step approach, where routing and wavelength assignment are done independently. Though this approach can reduce computational cost, the optimality of the solution is compromised. We propose a novel tabu search (TS) algorithm, which considers routing and wavelength assignment jointly without increasing the computational complexity. The performance of the proposed TS algorithm is compared with the Integer Linear Programming (ILP) method, which is known to solve the MWU to optimality. The results for both small and large networks show that our proposed TS algorithm works almost as well as the ILP solution and is much more computationally efficient.