Groupe d’études et de recherche en analyse des décisions

An efficient hybrid heuristic for the Routing and Wavelength Assignment problem

Christophe Duhamel Professeur agrégé, ISIMA, France

In all-optical networks a traffic demand is carried from its source to its destination through a lightpath, which is a sequence of fiber links carrying the traffic from end to end. The wavelength continuity constraint implies that a single wavelength must be assigned to a given lightpath. Moreover, a wavelength cannot be assigned to two different lightpaths sharing a common physical link. The routing and wavelength assignment (RWA) problem arises in this context as to establish lightpaths to carry traffic demands. We consider the min-RWA version of the problem, which consists in finding the minimal number of wavelengths such that the set \(R\) of lightpath requests (origin-destination pairs of demand) is satisfied over the undirected graph \(G\).

Thus, the solution is a minimal partition of R such that the requests in each subset can be routed through edge-disjoint paths in \(G\). We present a hybrid heuristic for the problem. It combines a variable neighborhood descent (VND) with an Iterated Local Search (ILS). Three neighborhood structures are used in the VND to rearrange requests between the subgraphs associated to subsets of the current partition in order to remove subset, one by one. Given one request in the current subset, it can be transferred to another subset if there is a path from its origin to its destination in the subgraph induced by this subset. Thus, the first structure tries to transfer a request from the current subset to another one. The second structure tries to make room for the request in the destination subset by first sending out some of its requests. The third structure first swaps the request with another one before sending the new one to another subset. The ILS uses the VND as local search. Its shaking operator consists in randomly some requests among the subsets. Numerical results are reported on classical RWA instances and the heuristic is compared with efficient existing heuristics.