Efficient implementations of heuristics for routing and wavelength assignment

T.F. Noronha,  M. G. C. Resende, and C.C. Ribeiro 

Proceedings of 7th International Workshop on Experimental Algorithms (WEA 2008), C.C. McGeoch (Eds.), LNCS, Springer, vol. 5038, pp. 169-180, 2008.

ABSTRACT

The problem of Routing and Wavelength Assignment in Wave- length Division Multiplexing (WDM) optical networks consists in routing a set of lightpaths and assigning a wavelength to each of them, such that lightpaths whose routes share a common fiber are assigned to different wavelengths. When the objective is to minimize the total number of wavelengths used, this problem is NP-hard. The current state-of-the-art heuristics were proposed in 2007 by Skorin-Kapov. The solutions provided by these heuristics were near- optimal. However, the associated running times reported were high. In this paper, we propose efficient implementations of these heuristics and reevaluate them on a broader set of testbed instances

PDF file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 12 June 2008

Copyright Notice