Combining heuristic and exact approaches for solving the routing and spectrum assignment problem
Authors:
Open Access
- 1 April 2018
- journal article
- research article
- Published by Institution of Engineering and Technology (IET) in IET Optoelectronics
- Vol. 12 (2) , 65-72
Abstract
Efficient algorithms for solving the routing and spectrum assignment (RSA) problem in flex‐grid optical networks are of paramount importance to leverage network efficiency. Exact approaches based on integer linear programming (ILP) models are known to be computationally hard and hence, difficult to solve for realistic models while heuristics have inherent downsize of local optimal trapping. In addressing those issues, this paper firstly presents a novel and efficient heuristic based on the genetic algorithm (GA) to provide (near‐) optimal solutions to the RSA problem. The effectiveness of the GA‐based algorithm is benchmarked against typically used reference heuristics for a set of network scenarios and it is shown that in addition to the better performance than conventional heuristics in the literature, the proposed GA technique indeed could achieve optimal solutions in most cases while the running time is still manageable. Secondly, we propose to make use of efficient solutions from the heuristic approaches to set the upper‐bound and warm‐start point for ILP formulation. This combination has been shown very productive in enhancing running time performance and increasing the capability of achieving an optimal solution and/or improving the solution quality in a given time span compared with traditional ways for solving ILP models.Keywords
This publication has 21 references indexed in Scilit:
- Routing and Spectrum Allocation in Elastic Optical Networks: A TutorialIEEE Communications Surveys & Tutorials, 2015
- Next generation elastic optical networks: The vision of the European research project IDEALISTIEEE Communications Magazine, 2015
- On Routing and Spectrum Assignment in RingsJournal of Lightwave Technology, 2014
- Spectrum Assignment in Optical Networks: A Multiprocessor Scheduling PerspectiveJournal of Optical Communications and Networking, 2014
- Spectrum management techniques for elastic optical networks: A surveyOptical Switching and Networking, 2014
- Solving Routing and Spectrum Allocation Related Optimization Problems: From Off-Line to In-Operation Flexgrid Network PlanningJournal of Lightwave Technology, 2014
- On the Optimal Design of a Spectrum-Switched Optical Network With Multiple Modulation Formats and RatesJournal of Optical Communications and Networking, 2013
- AN EVOLUTIONARY ALGORITHM APPROACH FOR DEDICATED PATH PROTECTION PROBLEM IN ELASTIC OPTICAL NETWORKSCybernetics and Systems, 2013
- Modeling the routing and spectrum allocation problem for flexgrid optical networksPhotonic Network Communications, 2012
- Finding the K Shortest Loopless Paths in a NetworkManagement Science, 1971