Metaheuristic hybridizations for the regenerator placement and dimensioning problem in sub-wavelength switching optical networks

Physical layer impairments severely limit the reach and capacity of optical systems, thereby hampering the deployment of transparent optical networks (i.e., no electrical signal regenerators are required). Besides, the high cost and power-consumption of regeneration devices makes it unaffordable for network operators to consider the opaque architecture (i.e., regeneration is available at every network node). In this context, translucent architectures (i.e., regeneration is only available at selected nodes) have emerged as the most promising short term solution to decrease costs and energy consumption in optical backbone networks. Concurrently, the coarse granularity and inflexibility of legacy optical technologies have re-fostered great interest in sub-wavelength switching optical networks, which introduce optical switching in the time domain so as to further improve resources utilization. In these networks, the complex regenerator placement and dimensioning problem emerges. In short, this problem aims at minimizing the number of electrical regenerators deployed in the network. To tackle it, in this paper both a greedy randomized adaptive search procedure and a biased random-key genetic algorithm are developed. Further, we enhance their performance by introducing both path-relinking and variable neighborhood descent as effective intensification procedures. The resulting hybridizations are compared among each other as well as against results from optimal and heuristic mixed integer linear programming formulations. Illustrative results over a broad range of network scenarios show that the biased random-key genetic algorithm working in conjunction with these two intensification mechanisms represents a compelling network planning algorithm for the design of future sub-wavelength optical networks.

► We model the regenerator placement and dimensioning problem (RPD) in subwavelength switching networks. ► A GRASP and a BRKGA are specifically developed to solve RPD. Further, we enhance their performance with PR and VND. ► The resulting hybridizations are compared against results from optimal and heuristic MILP formulations. ► Illustrative results show that BRKGA working in conjunction with PR and VND represents a compelling network planning algorithm.