Optimisation du routage et de l'affectation de longueurs d'onde sur un réseau de télécommunication par programmation mathématique


This work presents a decomposition approach for solving a variant of the routing and wavelength assignment problem, in which all connection requests are covered by shortest paths with respect to the number of hops. Our variant consists in minimizing the number of wavelengths required to all-to-all communication. Our decomposition approach is an extension of a recent method proposed in the literature, for the case of shortest paths. We also modify this method by proposing an improved path selection phase. The decomposition approach consists of four phases: (i) shortest paths computation; (ii) lower bound computation; (iii) selection of a shortest path per connection request; (iv) assignment of a wavelength to each connection request. Several methods have been proposed for the different phases but only one per phase has been kept after numerical experiments. This approach as well as a direct approach have been tested on 29 optical transport networks. The decomposition approach was able to solve these instances in less time than the direct approach while finding the optimal solution for 28 of them. For the remaining network, the approach was able to provide a small interval in which the optimal solution value resides. Finally, this approach can be used to accelerate the solution process of the direct approach by providing a good upper bound and a near optimal initial solution.

Master thesis