A matheuristic for the routing and spectrum allocation problem

Marcelo Bianchetti () and Javier Marenco ()
Additional contact information
Marcelo Bianchetti: Universidad de Buenos Aires
Javier Marenco: Universidad Torcuato Di Tella

4OR, 2025, vol. 23, issue 3, No 3, 269-301

Abstract: Abstract One of the most promising solutions to deal with huge data traffic demands in large communication networks is given by flexible optical networking, in particular the flexible grid (flexgrid) technology specified in the ITU-T standard G.694.1. In this specification, the frequency spectrum of an optical fiber link is divided into narrow frequency slots. Any sequence of consecutive slots can be used as a simple channel, and such a channel can be switched in the network nodes to create a lightpath. In this kind of networks, the problem of establishing lightpaths for a set of end-to-end demands that compete for spectrum resources is called the routing and spectrum allocation problem (RSA). Due to its relevance, this NP-hard problem has been intensively studied in the last decade. In this work we present an integer-programming-based heuristic for RSA. We propose several measures of the instance density, and we explore the performance of the proposed heuristic procedure as a function of these measures. Our computational experience shows that the proposed heuristic is effective for tackling RSA, in particular for detecting probably infeasible instances. We report the impact of the addition of this heuristic to an existing branch-and-cut procedure, showing that this addition enhances the ability of this procedure to solve realistic instances with optimality. Finally, we propose an instance benchmark in order to allow the comparison among different methods for RSA, a feature that was lacking in the RSA literature up to this point.

Keywords: Routing and spectrum allocation; Optical networks; Heuristics; Integer programming; 90B18; 90C11; 90C27; 90C59 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-025-00588-w Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:aqjoor:v:23:y:2025:i:3:d:10.1007_s10288-025-00588-w

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-025-00588-w

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().