Problème de conception de réseau de survie avec relais : une méthode par perturbation de voisinages

Session : SS16-2 / SS16 : Résolution parallèle des problèmes mono ou multi objectifs (continu et/ou combinatoire)
Vendredi 12 février 10:30 - 11:50 Salle : RP9
Adel Bouchakhchoukha et Mhand Hifi

Nous nous intéressons à la résolution d’une variante du problème de la conception d’un réseau avec des relais (noté NDPR : Network Design Problem with Relays). Ce type de problème est souvent rencontré dans le domaine des télécommunications et des systèmes adossés à des problématiques liées la logistique (transport). En effet, étant donnés un réseau et un ensemble de produits à acheminer (ou à transporter) sur ce réseau, le problème de la conception de réseau avec des relais revient à sélectionner un sous-ensemble de tronçons de sorte que chacun des produits (information) disponibles doit emprunter son propre itinéraire. De plus, l’acheminement (transmission) d’un produit (information) peut rencontrer des coupures ou parfois le transport ne peut dépasser une énergie maximale ; dans ce cas, sur chacun des itinéraires du réseau peut disposer d’un sous-ensemble de relais représentant des sommets du réseau. Dans d’autres cas, on exige des acheminements indépendants pour chacun des produits, permettant ainsi d’assurer le transfert ou du moins limiter les dégâts dans le cas où des perturbations fortes soient présentes.

Mots clés : méthode approchée, optimisation, relais, réseau, survie.