Optimization Online


Efficient implementations of heuristics for routing and wavelength assignment

Thiago F. Noronha(tfn***at***inf.puc-rio.br)
Mauricio G. C. Resende(mgcr***at***research.att.com)
Celso C. Ribeiro(celso***at***ic.uff.br)

Abstract: The problem of Routing and Wavelength Assignment in Wavelength 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.

Keywords: Algorithm engineering, routing and wavelength assignment, heuristics.

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Combinatorial Optimization

Citation: AT&T Labs Technical Report TD-7BBTGY, AT&T Labs Research, Florham Park, NJ 08932 USA, 2008.

Download: [PDF]

Entry Submitted: 01/29/2008
Entry Accepted: 01/30/2008
Entry Last Modified: 01/29/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society