Recherche locale a voisinage variable pour le routage optique dans des reseaux utilisant des routeurs latins

摘要

This paper proposes an approach based on Variable Neighbourhood Search (VNS) to solve the Routing and Wavelength Assignment (RWA) problem in optical networks including latin routers. It can be summed up as establishing routing (finding intermediate routers on optical paths between each origin/destination pair) and wavelength assignment of these optical paths in such networks. The problem will be tackled according to two scena-rii: to optimize the number of established connections (scenario 1) or to answer as well as possible an accurate traffic array (scenario 2). In traditional optical networks (without latin routers), one often separates routing and wavelength assignment because of the general problem complexity (each of the two sub-problems is NP-hard). However, latin routers introduce constraints connecting routing and assignment, this requires a simultaneous treatment of the two problems. A local search heuristic, VNSFOR, based on the definition of different neighbourhoods (with simple and double moves) is proposed in this paper to provide us with solutions close to the optimum. Experimental results show how VNSFOR leads to better solutions, according to both scenarii, in comparison with the reference algorithm LONCA.