An efficient genetic algorithm approach for solving routing and spectrum assignment problem

Abstract

In flex-grid optical network, routing and spectrum assignment (RSA) problem is a crucial task for planning and operating. Due to the non-deterministic polynomial time (NP-hard) complexity of problem, efficient computing techniques are always sought out with the aim to not only achieve good solutions but also in an efficient time span. In this context, this paper addresses the static version of RSA problem in a single objective scenario. We propose efficient meta-heuristic based on genetic algorithm (GA) to provide (near-) optimal solutions to the problem. The effectiveness of GA-based heuristic is bench-marked with exact approach based on integer linear programming (ILP) and other traditional heuristics for a set of scenarios. It is shown that the proposed GA heuristic exhibits better performance than typical heuristics and indeed could achieve optimal solutions in most cases while the running time is still highly manageable.