Optimization Online


A genetic algorithm with random keys 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 (RWA) 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 different wavelengths. This problem was shown to be NP-hard when the objective is to minimize the total number of wavelengths used. In this paper, we propose a genetic algorithm with random keys for routing and wavelength assignment with the goal of minimizing the number of different wavelengths used in the assignment. This algorithm extends the best heuristic in the literature by embedding it into an evolutionary framework. Computational results show that the new heuristic improves the state-of-the-art algorithms in the literature.

Keywords: Genetic algorithm, routing, wavelength assignment, optical networks, random keys.

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

Category 2: Combinatorial Optimization (Meta Heuristics )

Category 3: Global Optimization (Stochastic Approaches )

Citation: AT&T Labs Research Technical Report, AT&T Labs Research, Florham Park, NJ 07932, June 18, 2008.

Download: [PDF]

Entry Submitted: 06/18/2008
Entry Accepted: 06/18/2008
Entry Last Modified: 06/18/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