spi.other
Alexandre Xavier Martins 
  
Alexandre Xavier Martins 
  
Metaheurísticas 
  
Ao Professor 
  
Mauricio Cardoso De Souza 
  
Rodney Rezende Saldanha 
  
Christophe Duhamel 
  
Aos Professores 
  
Ricardo Amigos 
  
Saraiva De Camargo 
  
Gilberto De Miranda 
  
Aos Meus Pais 
  
João Francisco Martins 
  
Ana Maria 
  
Xavier Martins 
  
Alisson Xavier Martins 
  
Andre Xavier Martins 
  
Rômulo Angelo 
  
Dos Santos 
  
Maria Ocarlina 
  
Martins De 
  
Souza Santos 
  
Meus Primos 
  
Melissa Martins 
  
Matheus Martins 
  
À Família Vieira 
  
José Carlos 
  
Os Fanfarrões 
  
Francis E Especialmente 
  
Anos Aos Amigos Da França 
  
Datta Ramadasan 
  
Djellul Mameri 
  
Erol Ozgur 
  
Lahkdar Akroun 
  
Libo Ren 
  
Nardjees Manadjelia 
  
Natália Vaz 
  
Nathalie Bernard 
  
Monica Unau 
  
Raksmey Phan 
  
Agradeço 
  
Ao Casal 
  
  
  
  
  
  
  
  
  
  
  
Redes Ópticas

Keywords: método, que chamamos Otimização, telecomunicação, roteamento Optimization, telecommunication, routing and wavelength allocavii tion, mathematical programming, column generation, metaheuristic. viii Optimisation, télécommunication, routage et allocation de longueur d'onde, modèle mathématique, génération de colonnes, métaheuristique

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Metaheurísticas e Formulações para a resolução do Problema de Roteamento e Alocação de Comprimentos de Onda em

Résumé Introduction

Les réseaux optiques ont favorisé une forte croissance dans les télécommunications en général. En eet, ils possèdent une grande bande passante, ils ne sont pas affectés par les interférences électromagnétiques du fait de l'utilisation de matériaux diélectriques, ils résistent bien à la corrosion et ont un faible taux de perte. De plus il est possible de mettre en place des systèmes de transmission longue distance avec un espacement raisonnablement grand entre les répétiteurs, ce qui limite le coût et la complexité [START_REF] Borella | Optical components for WDM lightwave networks[END_REF].

Cependant, la vitesse de transmission théoriquement oerte par la bre optique est rarement atteinte à cause des traitements électroniques sur les routeurs [START_REF] Murthy | WDM optical Networks: Concepts, Design and Algorithms[END_REF]. Le mécanisme de commutation actuel nécessite du stockage et du traitement sur les routeurs. Il induit donc du retard dans la transmission et transforme les n÷uds de commutation en points de congestion. De plus, la bande passante oerte par les bres optiques n'est pas susante pour garantir l'ecacité du réseau [START_REF] Chlamtac | Lightpath communications: An approach to high-bandwidth optical WAN's[END_REF]. Une clé pour obtenir des réseaux à grande vitesse est de maintenir le signal sous forme optique en évitant ainsi les transformations coûteuses sur les convertisseurs optoélectroniques, tant en entrée qu'en sortie du signal [START_REF] Lee | An optimization approach to routing and wavelength assignment in WDM all-optical mesh networks without wavelength conversion[END_REF].

Un système de transmission des bres optiques est fondamentalement constitué par un émetteur optique et un récepteur, et un câble de bre optique. Le transmetteur se compose d'un dispositif émettant de la lumière et un circuit associé, qui a des fonctions de polarisation et de contrôle de puissance de sortie par le dispositif émetteur de lumière. Le dispositif émetteur de lumière est l'élément actif du système, il est responsable de la conversion opto-électronique des signaux. Deux xix types de dispositifs sont couramment utilisés comme sources de lumière dans les systèmes de transmission par des bres optiques: diodes laser (LD's) et diodes électroluminescentes (LED's). Plusieurs dispositifs ont été développés pour améliorer cette technologie, par exemple, des commutateurs optiques (Optical CrossConnect -OXC) et des amplicateurs optiques (OA).

De nombreuses recherches sont donc orientées multiplexage pour permettre de proter des grandes capacités oertes. Les diérentes techniques de multiplexage consiste à envoyer un signal sur chaque canal et introduire une séparation temporelle, spatiale et fréquentielle. Les multiplexages les plus répandues sont:

• Le multiplexage à répartition spatiale (Spatial Division Multiplexing -SDM):

il consiste à partitionner l'espace physique pour augmenter la bande passante, par exemple, en regroupant un ensemble de bres dans un câble, ou en utilisant des câbles multiples en un seul lien;

• Le multiplexage à répartition temporelle (Time Division Multiplexing -TDM):

il consiste à consacrer la totalité de la bande passante à l'échange d'une donnée pendant un intervalle de temps avant de passer à la donnée suivante; l'incovénient de cette méthode est le gaspillage de la bande passante du fait que toutes les données envoyées n'ont pas la même taille; il arrive donc de consacrer un intervalle de temps très grand pour envoyer une donnée minimale; Le OADM reçoit les informations, elles sont multiplexés puis envoyé à l'émetteur et se connecte ensuite à un amplicateur de ligne optique. Ensuite, le signal passe par un chemin optique pour atteindre la destination. Puis, le signal atteint le récepteur, qui a un démultiplexeur (DEMUX), où les longueurs d'onde sont de nouveau séparées et est alors dirigé vers l'OADM. S'il y a des sommets intermédiaires, la clé OXC est utilisée pour changer la lumière d'un sommet à l'autre, qui peut être un autre sommet intermédiaire ou même le sommet de destination.

•
La clé de ces réseaux à haut débit est de maintenir le signal sous forme optique, en évitant la surcharge de la conversion sous forme électrique, soit à l'arrivée ou au signal de sortie [START_REF] Lee | An optimization approach to routing and wavelength assignment in WDM all-optical mesh networks without wavelength conversion[END_REF].

Associé au problème de répondre aux exigences d'un réseau à l'aide WDM, on peut citer les problèmes et leurs caractéristiques suivantes:

• La conception de la topologie virtuelle: il s'agit essentiellement d'un choix de chemins optiques du réseau. Pour ces connexions, on ne fait pas de traitement électronique pour le routage.

xxi

• Le routage et l'aectation de longueur d'onde: ce problème a essentiellement deux objectifs, accueillir les chemins optiques de la conception de la topologie virtuelle au cours de la topologie physique et l'aectation des longueurs d'onde sur chaque lien, de sorte qu'une longueur d'onde ne soit pas aectée à deux chemins optiques dans le même lien.

• Problème de concentration du trac (Trac Grooming): ce problème est déni comme le problème de la combinaison des demandes de faible vitesse sur les canaux de capacité de transmission élevée. En général, il a déjà prédéterminé les chemins optiques et le problème de la concentration du trac est de combiner le trac de ces voies [START_REF] Patrocínio | Planejamento de topologia virtual com combinação de tráfegos em redes Ópticas multiplexadas por divisão de comprimentos de onda. Tese de doutorado[END_REF].

Dans ce travail, nous allons traiter le problème du routage et l'aectation de longueur d'onde. En l'abscence de conversion, la contrainte de continuité de longueur La restriction qui est imposée est que la même longueur d'onde ne peut pas être utilisée pour répondre à deux ou plusieurs requêtes diérentes si les chemins de ces requêtes utilisent le même arc. En outre, nous avons la contrainte de continuité, où la longueur d'onde aectée à un chemin doit être utilisée du début à la n de ce chemin, sans conversion. Cette restriction sera adoptée dans tous les travaux.

Chlamtac et al. [START_REF] Chlamtac | Lightpath communications: An approach to high-bandwidth optical WAN's[END_REF] ont montré que le RWA est NP-complet pour des graphes de topologie arbitraire en réduisant le problème au problème de coloration de graphes.

C'est à dire que trouver le nombre minimum de longueurs d'onde et que d'aecter toutes les requêtes est le même problème que trouver le nombre minimum nécessaire pour colorer un graphe tel qu'aucun n÷ud adjacent reçoit la même couleur, où le nombre de couleurs est le nombre de longueurs d'onde.

Pour résoudre le problème du routage et d'aectation de longueur d'onde sont proposés certains modèles de programmation mathématique dans la littérature. La plupart de ces modèles visent à maximiser le nombre de requêtes attribuées.

Ramaswami et Sivarajan [START_REF] Ramaswami | Routing and wavelength assignment in all-optical networks[END_REF] présentent une formulation pour le problème de routage et d'aectation des longueurs d'onde, en introduisant l'idée d'ensembles indépendants.

Lee et al. [START_REF] Lee | An optimization approach to routing and wavelength assignment in WDM all-optical mesh networks without wavelength conversion[END_REF] ont présenté une formulation basée sur les chemins. Pour cela, xxiii ils ont introduit la notion de conguration de routage indépendante. L'ensemble c est une conguration de routage indépendante si on peut faire a c sd connexions pour chaque (s, d) ∈ R sur le graphe G simultanément en utilisant une seule longueur d'onde. Généralement, il ya un nombre exponentiel de congurations de routage indépendante, c'est à dire que le problème maître a un nombre exponentiel de variables de décision. Pour cette raison, Lee et al. [START_REF] Lee | An optimization approach to routing and wavelength assignment in WDM all-optical mesh networks without wavelength conversion[END_REF] ont également présenté une stratégie basée sur la génération de colonnes [START_REF] Gilmore | A linear programming approach to the cutting stock problem[END_REF] et un algorithme branch-and-price pour résoudre le problème, la méthode a été en mesure d'obtenir de bonnes solutions.

Krishnaswamy et Sivarajan [START_REF] Krishnaswamy | Algorithms for routing and wavelength assignment based on solutions of lp-relaxation[END_REF] ont présenté un modèle avec l'objectif de maximiser le nombre de requêtes déni basé sur des arcs.

Des comparaisons des modèles de programmation mathématique pour le RWA avec l'objectif de maximiser le nombre de connexions établies peuvent être trouvées dans [START_REF] Jaumard | ILP Formulations and Optimal Solutions for the RWA Problem[END_REF], [START_REF] Jaumard | ILP formulations for the RWA problem for symmetrical systems[END_REF] et [START_REF] Jaumard | Comparison of ILP formulations for the RWA problem[END_REF].

Dans [START_REF] Jaumard | On column generation formulations for the RWA problem[END_REF] est fait un examen des modèles de génération de colonnes pour le RWA an de maximiser le nombre du connexions établies et quelques améliorations sont proposées. En outre, combinant les idées de Ramaswami et Sivarajan [START_REF] Ramaswami | Routing and wavelength assignment in all-optical networks[END_REF] et Lee et al. [START_REF] Lee | An optimization approach to routing and wavelength assignment in WDM all-optical mesh networks without wavelength conversion[END_REF], Jaumard et al. [START_REF] Jaumard | On column generation formulations for the RWA problem[END_REF] ont présenté une nouvelle formulation et un algorithme Branch and Price qui a été en mesure de résoudre certains cas de taille moyenne à grande.

Pour les problèmes qui ont un trac uniforme, c'est à dire qu'une connexion doit être établi entre toutes les paires de sommets (v × (v -1) demandes), Baroni et Bayvel [START_REF] Baroni | Wavelength requirements in arbitrarily connected wavelength-routed optical networks[END_REF] ont obtenu des bornes inférieures introduisant des réductions dans le graphe.

Sharafat et Ma'rouzi [START_REF] Sharafat | The most congested cutset: deriving a tight lower bound for the chromatic number in the RWA problem[END_REF] ont présenté une généralisation du travail de Baroni et Bayvel [START_REF] Baroni | Wavelength requirements in arbitrarily connected wavelength-routed optical networks[END_REF] en calculant des bornes inférieures pour des graphes de diérentes matrices de trac et de topologies arbitraires.

Skorin-Kapov [START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF], inspirée par la méthode introduite par Ramaswami et Sivarajan [START_REF] Ramaswami | Design of logical topologies for wavelengthrouted optical networks[END_REF] à des problèmes de dénition de topologies virtuelles, a présenté une méthode simple pour obtenir des bornes inférieures.

En 2009, Fisher et al. [START_REF] Fischer | Solving the routing and wavelength assignment problem with a multilevel distributed memetic algorithm[END_REF] ont adapté le modèle présenté par Banerjee et Mukherxxiv jee [START_REF] Banerjee | Practical approaches for routing and wavelength assignment in large all-optical wavelength routed networks[END_REF]. Dans ce travail, la contrainte de continuité sur la longueur d'onde a été assouplie et un algorithme pour obtenir des bornes inférieures pour la RWA a été fait.

Plusieurs travaux sont consacrés à la résolution du RWA minimisant le nombre de longueurs d'onde. Certaines stratégies décomposent le problème en deux parties [START_REF] Banerjee | A practical approach for routing and wavelength assignment in large wavelength-routed optical networks[END_REF][START_REF] Li | The partition coloring problem and its application to wavelength routing and assignment[END_REF][START_REF] Noronha | Routing and wavelength assignment by partition colouring[END_REF]. Une route est d'abord déterminée pour chaque connexion puis une longueur d'onde est aectée à chaque route en résolvant un problème de coloration de graphe [START_REF] Brelaz | New methods to color the vertices of a graph[END_REF]. D'autres stratégies traitent les deux problèmes simultanément [START_REF] Manohar | Routing and wavelength assignment in optical networks from edge disjoint path algorithms[END_REF][START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF].

Inspiré par Conway et al. [START_REF] Conway | Theory of Scheduling[END_REF], Chlamtac et al. [START_REF] Chlamtac | Lightpath communications: An approach to high-bandwidth optical WAN's[END_REF] ont développé une heuristique gloutonne pour l'attribution des longueurs d'onde. Dans cet article, les chemins sont déterminés par un algorithme de plus court chemin. Ensuite, ils sont triés par ordre décroissant de taille, puis attribués à chaque longueur d'onde à tous les chemins disjoints possible. L'idée est que les routes plus grandes sont plus diciles à attribuer et doivent donc être aectés en premier lieu.

Manohar et al. [START_REF] Manohar | Routing and wavelength assignment in optical networks from edge disjoint path algorithms[END_REF] ont proposé un algorithme constructive et randomisé pour RWA, le Greedy-EDP-RWA, cet algorithme est utilisé comme un algorithme de multipartite, exécuté par le nombre xe d'itérations, en retournant la meilleure solution trouvée. L'idée est similaire aux travaux présentés par Chlamtac et al. [START_REF] Chlamtac | Lightpath communications: An approach to high-bandwidth optical WAN's[END_REF] d'aecter le même longueur d'onde sur les chemins disjoints, mais ici, les chemins sont générés à chaque itération, l'ordre de toutes les demandes est tiré au hasard. Banerjee et Sharan [START_REF] Banerjee | A evolutionary algorithm for solving the single objective static routing and wavelength assignment problem in WDM networks[END_REF] ont utilisé un algorithme évolutionnaire pour déterminer le routage et de résoudre le problème de l'aectation des longueurs d'onde comme un problème de coloration de graphes.

Li et Simha [START_REF] Li | The partition coloring problem and its application to wavelength routing and assignment[END_REF] ont proposé pour résoudre le problème du routage et d'aectation des longueurs d'onde en résolvant le problème de coloration de partitions, une extension du problème de coloration de graphes. Dans ce travail, les auteurs ont adapté six méthodes de construction appliquées à la coloration de graphes. Les meilleurs résultats ont été obtenus avec l'algorithme onestepCD (One Step Color Degree).

Noronha et al. [START_REF] Noronha | Routing and wavelength assignment by partition colouring[END_REF] ont utilisé la stratégie exposée dans le travail de Manohar et al. [START_REF] Manohar | Routing and wavelength assignment in optical networks from edge disjoint path algorithms[END_REF] pour générer deux chemins pour chaque connexion, puis ils ont utilisé une xxv procédure basée sur la Tabu Search pour déterminer les aectations des longueurs d'onde comme un problème de coloration partitions [START_REF] Li | The partition coloring problem and its application to wavelength routing and assignment[END_REF]. [START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF] propose quatre heuristiques constructives basées sur des algorithmes similaires utilisées dans la résolution du Bin Packing. First Fit (FF), Best Noronha et al. [START_REF] Noronha | Ecient implementation of heuristics for routing and wavelength assignment[END_REF] ont amélioré les performances des méthodes présentées dans [START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF]. Les auteurs ont travaillé dans la structure des données et des stratégies de mise en ÷uvre, telle que la liste d'adjacence doublement enchaînée soit mise à jour dynamique des plus courts chemins. Les meilleurs résultats sont obtenus avec une variante de l'algorithme BFD.

Skorin-Kapov

Noronha et al. [START_REF] Noronha | A biased random-key genetic algorithm for routing and wavelength assignment[END_REF] ont proposé un algorithme génétique avec clés aléatoires pour trier les demandes. Les éléments sont triés en fonction de la taille et la valeur de la clé. Les chromosomes sont des vecteurs de nombres réels, appelées clés. Chaque demande est associée à une valeur de clé entre [0, 1], cette valeur dans la population initiale est générée aléatoirement. Les clés sont utilisées pour décoder en générant des solutions réalisables. Les demandes sont triées en fonction de la somme de la taille de son plus court chemin entre l'origine et la destination, et la valeur de la clé, puis ensuite le BFD est appliqué. Pour générer une nouvelle population, la méthodologie proposée dans DeJong et Britney [START_REF] Spears | On the virtues of parameterized uniform crossover[END_REF] est utilisée. Les résultats numériques ont été réalisés sur la plupart des cas étudiés dans la littérature ainsi que de nouvelles instances introduites dans [START_REF] Noronha | Ecient implementation of heuristics for routing and wavelength assignment[END_REF]. L'algorithme a obtenu de meilleurs résultats que les méthodes proposées jusqu'à présent.

Heuristiques appliquée au problème de RWA Nous proposons dans cette thèse deux approches heuristiques pour résoudre le problème de RWA.

xxvi Dans la première stratégie nous avons développé un algorithme VND, qui, avec l'heuristique BFD tente d'éliminer à chaque itération une longueur d'onde. En outre, malgré la première stratégie, nous combinons l'algorithme VND avec la Tabu Search présentés dans Noronha et al. [START_REF] Noronha | Routing and wavelength assignment by partition colouring[END_REF].

La première étape de la méthode consiste à sélectionner deux longueurs d'onde.

Le critère utilisé pour ce premier choix est de sélectionner deux sous-graphes (longueurs d'onde) qui forment ensemble le sous-graphe le plus proche du graphe d'origine. Le concept de sous-graphe le plus proche est déni comme suit: soit une collection de sous-graphes de G = (V, E), deux sous-graphes

G ′ = (V, E ′ ) et G ′′ = (V, E ′′ ) qui
forment la collection plus proche du graphe G cas la diérence entre la cardinalité de E et E ′ ∪ E ′′ est la plus petite possible d'obtenir avec deux sous-graphes de la collection.

Avec les deux sous-graphes déterminés, l'étape suivante consiste à aecter les requêtes dans ces sous-graphes dans un autre graphe, quelque soient les tailles du chemins. Cette étape vise à libérer des arcs appartenant à des sous-graphes sélectionnés.

Enn, on applique l'algorithme BFD sur les requêtes restantes dans sous-graphes sélectionnés. Il s'agit du voisinage 1-opt, où nous travaillons avec deux copies du graphe original. Si la solution retournée par BFD est meilleure, c'est à dire que si la méthode aecte toutes les requêtes en utilisant moins de sous-graphes (longueurs d'onde) qu'au début du processus, alors nous acceptons la solution, sinon nous irons vers le prochain voisinage en ajoutant un sous-graphe à la procédure. Dans cette étape, chaque nouveau graphe ajouté, est celui qui a le plus grand nombre d'arcs sans utilisation. Cette opération est répétée jusqu'à ce que le nombre de sous-graphes utilisés dans le mouvement atteint une limite prédéterminée, qui est un paramètre de la méthode.

La méthode BFD est utilisée pour générer la solution, ainsi que dans le rafnement de la solution. Dans le ranement, il est utilisé sur un sous-ensemble de requêtes appartenant à un certain nombre de sous-graphes, en fonction du voisinage exploré.

xxvii Le Tabu Search présenté dans [START_REF] Noronha | Routing and wavelength assignment by partition colouring[END_REF] a été adapté pour faire partie d'une procédure hybride pour résoudre le RWA. La méthode hybride fonctionne comme suit: lorsque les voisinages explorés par le VND ont été épuisés, nous avons aecté un sousensemble de requêtes dans un sous-ensemble de graphes (longueurs d'onde). Pour chaque requête, à ce point, nous avons deux chemins, un chemin généré lors de la construction de la solution initiale et un autre produit dans la dernière itération du VND. Ainsi, ces deux chemins de chaque requête sont passés à Tabu Search. Le Tabu Search est exactement égal à celui présenté dans [START_REF] Noronha | Routing and wavelength assignment by partition colouring[END_REF]. Dans le voisinage Φ 2 la première étape est d'essayer de trouver un nouvel espace pour la requête r dans un autre sous-graphe en déplaçant le maximum de requêtes de cette sous-graphe. Si la méthode peut déplacer au moins une requête du sousgraphe, alors nous pouvons essayer d'aecter la requête r dans ce sous-graphe. En cas de succès, nous passons à la prochaine requête sur la liste, le cas échéant, dans le voisinage Φ 1 . Dans le contraire, la méthode passe au voisinage Φ 3 toujours avec la même requête r considérée. À chaque nouvelle recherche via Φ 2 un seul sous-graphe est choisi selon l'ordre de la création du sous-graphes.

Un mouvement dans le voisinage Φ 3 essaie de modier la requête r avec une autre requête appartenant à un autre sous-graphe. Les échanges sont acceptés uniquement pour les requêtes qui ont le chemin plus court que celui de la requête r. Notez que le mouvement dans le voisinage Φ 3 ne réduit pas la cardinalité du sous-graphe.

Si un changement n'est pas possible dans le voisinage Φ 3 , on passe à l'étape de perturbation de la méthode.

La perturbation est appliqué lorsque le VND a échoué à changer une requête dans le voisinage Φ 3 . Notez qu'à ce stade, le VND peut avoir fait quelques pas. Nous n'annulons pas ces mouvements faits. La perturbation se trouve sur un problème xxix de l'attribution construit pour réorganiser les requêtes entre les sous-graphes. La méthode choisit au hasard une requête r ′ pour chaque sous-graphe de la solution, à l'exception du sous-graphe que nous voulons éliminer.

Soit G a w ′ = (V, E a w ′ ) le sous-graphe de G, où E a w ′ = E -∪ r∈Γ w ′ -{r ′ } E r (
les arcs utilisés pour acheminer r ′ sont réactivés dans G a w ′ ). La perturbation est fait pour trouver la meilleure façon d'attribuer W -1 requêtes en W -1 sous-graphes.

Le coût de l'attribution de la requête i ∈ Γ w i pour le sous-graphe j est donnée comme suit:

• c ij = 2, si j = w i ; {Coût de retourner la requête au le sous-graphe d'origine}

• c ij = ∞, si il n'existe aucun moyen d'acheminer la requête i dans le sous-graphe Méthodes exactes appliquées au problème de RWA Dans cette thèse, nous présentons quelques modications aux modèles mathématiques basés sur des arches existantes à ce problème de routage et l'aectation des longueurs d'onde an de maximiser le nombre de connexions établies.

G a j ; • c ij = 1 - min spl (i) min spl (i)(G a j ) -max(min spl (i)(G a i ) -min spl (G a j ), 0), cas contraire, où min spl (i)(G ′ )
Le but ici est de rendre les modèles plus "légers"et de pouvoir résoudre des instances de même taille dans un temps plus court ou de même instances plus grandes qui ne sont pas traitées par les modèles existants.

Nous présentons les modèles que nous appelons KS [START_REF] Krishnaswamy | Algorithms for routing and wavelength assignment based on solutions of lp-relaxation[END_REF] et JMT [START_REF] Jaumard | Comparison of ILP formulations for the RWA problem[END_REF] Para fazer frente ao rápido crescimento na demanda de informações que atravessam uma rede começou-se a fazer uso da multiplexação por divisão de comprimento de onda. Multiplexar é enviar um certo número de canais pelo do mesmo meio de transmissão. A multiplexação por divisão de comprimento de onda (WDM -Wavelenght Division Multiplexing) é uma técnica que vem sendo utilizada juntamente com técnicas de encaminhamento de informações por uma rede óptica, auxiliando as telecomunicações [START_REF] Zang | A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks[END_REF]. Esta técnica permite a expansão da capacidade dos sistemas ópticos sem a necessidade de instalação de novas bras, pois permite transformar uma única bra óptica em várias bras virtuais, cada uma destas transportando sinais com comprimentos de onda diferentes, independentemente do formato dos dados transportados. As conexões entre os nós de uma rede totalmente óptica WDM são estabelecidas por caminhos ópticos [START_REF] Chlamtac | Lightpath communications: An approach to high-bandwidth optical WAN's[END_REF].

Figura 1.1: Uma bra transmitindo três comprimentos de onda distintos - [START_REF] Huiban | O problema da reconguração nas redes WDM multibras[END_REF] Os caminhos ópticos podem envolver um ou mais vértices da rede. O caminho óptico necessita do uso de um comprimento de onda, ou seja, cada requisição está associada a um comprimento de onda especíco. A chave para a alta velocidade nestas redes é manter o sinal em sua forma óptica, evitando a sobrecarga da conversão na forma elétrica tanto na chegada quanto na saída do sinal [START_REF] Lee | An optimization approach to routing and wavelength assignment in WDM all-optical mesh networks without wavelength conversion[END_REF].

Desde que não haja conversão, cada caminho óptico utiliza um comprimento de onda único em todos os arcos da origem ao destino, isto é chamado de restrição de continuidade do comprimento de onda [START_REF] Banerjee | A practical approach for routing and wavelength assignment in large wavelength-routed optical networks[END_REF].

Diferentes técnicas de multiplexação podem ser usadas nas redes ópticas WDM como, por exemplo:

• Multiplexação por divisão de espaço (SDM): particiona o espaço físico para aumentar a largura de banda, por exemplo, agrupando um conjunto de bras em um único cabo, ou usando vários cabos em um único enlace [START_REF] Barr | Grooming telecommunication networks[END_REF].

• Multiplexação por divisão de freqüência (FDM): particiona o espectro de freqüência disponível em um conjunto de canais independentes. A utilização de FDM em uma rede óptica se reduz ao WDM, multiplexação por divisão de comprimento de onda que permite uma bra levar tráfego em muitos comprimentos de onda distintos [START_REF] Barr | Grooming telecommunication networks[END_REF].

• Multiplexação por divisão de tempo (TDM): divide o domínio de tempo da banda em intervalos de duração xa. Utilizando a TDM, múltiplos sinais podem compartilhar um determinado comprimento de onda se eles não se sobrepõe no tempo [START_REF] Barr | Grooming telecommunication networks[END_REF].

Ligados ao problema da acomodação das demandas em uma rede usando sistemas WDM, pode-se citar os seguintes problemas e características:

• Projeto da Topologia Virtual: consiste basicamente em uma escolha dos caminhos ópticos da rede. Estes são denidos com conexões ponto-a-ponto que são transparentes aos nós intermediários, isto é, para estas conexões não é realizado processamento eletrônico para ns de roteamento em tais nós [START_REF] Krishnaswamy | Design of logical topologies: A linear formulation for wavelength-routed optical networks with no wavelength changers[END_REF].

• Roteamento e Atribuição dos Comprimentos de Onda: este problema possui basicamente dois objetivos: acomodar os caminhos ópticos provenientes do projeto da topologia virtual sobre a topologia física e atribuir os comprimentos de onda em cada enlace, am de que um comprimento de onda não seja atribuído a dois caminhos ópticos em um mesmo enlace.

• Problema de Concentração de Tráfego (Trac Grooming): este problema é denido como o problema de combinar demandas de baixa velocidade em canais de transmissão de alta capacidade. Em geral considera-se uma conguração de caminhos ópticos pré-estabelecidos e o problema de concentração de tráfego consiste em combinar o tráfego dentro destes caminhos [START_REF] Patrocínio | Planejamento de topologia virtual com combinação de tráfegos em redes Ópticas multiplexadas por divisão de comprimentos de onda. Tese de doutorado[END_REF].

Uma topologia física G p é um grafo em que os arcos representam um par de bras (um em cada direção) e os nós representam nós roteadores de comprimento de onda.

O conjunto de todos os caminhos ópticos unidirecionais ao longo dos roteadores forma a topologia virtual G v ou topologia de caminhos ópticos.

Para uma rede com V vértices, o ideal seria congurar caminhos ópticos para todos os V (V -1) pares. Entretanto, isso não é usualmente possível primeiramente pelo número de comprimentos de onda disponíveis que impõe um limite na quantidade de caminhos ópticos que podem ser congurados (isto é também uma função da distribuição de tráfego) e ainda cada nó pode ser fonte e destino de um número limitado de caminhos ópticos. Isto é determinado pela quantidade de hardware óptico que pode ser provido (transmissores e receptores) e pela quantidade total de informações que um nó pode processar [START_REF] Ramaswami | Design of logical topologies for wavelengthrouted optical networks[END_REF].

A topologia virtual é dita simétrica se, sempre que existir uma ligação lógica do vértice i para o vértice j, existe uma outra ligação lógica de j para i, caso contrário a topologia virtual é dita assimétrica [START_REF] Krishnaswamy | Design of logical topologies: A linear formulation for wavelength-routed optical networks with no wavelength changers[END_REF].

Denida a topologia virtual o próximo passo é saber como as ligações ponto a ponto desta topologia irão ser feitas sobre a topologia física, ou seja, como será feito o roteamento na topologia física e a alocação de comprimentos de onda para os enlaces virtuais estabelecidos previamente. Esse problema é conhecido como Roteamento e Alocação de Comprimentos de Onda (RWA -Routing and Wavelength Assignment).

O RWA visa atender às demandas denidas na etapa do projeto de topologia virtual, em geral minimizando recursos como a quantidade de comprimentos de onda utilizados ou maximizando a quantidade de requisições atendidas com um número limitado de comprimentos de onda disponíveis.

A m de utilizar ecientemente a largura de banda oferecida pelas redes ópticas, uxos independentes com baixa taxa de tráfego devem ser multiplexados em um único caminho óptico [START_REF] Dutta | Trac grooming in WDM networks: Past and future[END_REF]. Esta observação dá origem ao conceito de concentração de tráfego (PCT), ou Trac Grooming Problem, que refere-se às técnicas utilizadas para combinar os componentes de baixa velocidade em comprimentos de onda disponíveis para atender aos objetivos do projeto de rede, como a minimização de custos ou a maximização do uxo na rede.

O RWA pode ser considerado um caso especial do PCT. A diferença é que no RWA, cada requisição ocupa a capacidade inteira de um comprimento de onda enquanto no PCT essa capacidade pode ser dividida para mais de uma requisição.

Objetivos

O objetivo desta tese é estudar o RWA independentemente da topologia da rede física subjacente. Para isso duas abordagens distintas serão apresentadas. Uma abordagem heurística, visando soluções viáveis de boa qualidade em um tempo computacional razoável e uma abordagem exata, através de técnicas como a geração de colunas para a obtenção de limites inferiores. Como objetivos especícos deste trabalho, podemos destacar:

• Revisão de Literatura sobre o RWA;

• Construção de Heurísticas para a resolução do RWA;

• Testes computacionais das heurísticas propostas;

• Modelagem matemática para RWA;

• Testes computacionais para os modelos propostos;

• Desenvolvimento de métodos para determinação de limites inferiores;

• Comparações com a literatura.

Contribuições

Os seguintes elementos são as principais contribuições desta tese:

• Desenvolver e testar três buscas locais que visam a realocação de requisições;

• Desenvolver e testar um método de perturbação de soluções que não alteram o valor da função objetivo;

• Apresentar e testar simplicações aos modelos compactos existentes para a resolução do problema;

• Desenvolver um modelo de geração de colunas para a geração de caminhos;

• Desenvolver e testar uma nova abordagem de geração de colunas para a resolução do problema; Capítulo 2

Roteamento e Alocação de Comprimentos de Onda

Neste capítulo é apresentada uma revisão acerca do problema de roteamento e alocação de comprimentos de onda (RWA -Routing and Wavelength Assignment).

Primeiramente o problema é apresentado e denido. A seguir, são mostrados alguns modelos de programação matemática e métodos para obter limites inferiores.

Por m, é feita uma revisão sobre métodos heurísticos e sobre as metaheurísticas utilizadas para a resolução do problema. Note que, se G é uma árvore, cada par de nós pode ser conectado por somente um caminho; assim, a primeira parte do problema já estará resolvido, o roteamento. A complexidade do problema de minimizar número de comprimentos de onda alocados dependerá da topologia da árvore. Se G for uma árvore em cadeia (árvore com grau máximo igual a dois), estrela ou spider (árvore com exatamente um vértice de grau maior que dois) o problema de minimizar o número de comprimentos de onda pode ser resolvido em um tempo polinomial [START_REF] Dutta | Trac grooming in WDM networks: Past and future[END_REF]. A Figura 2.3 mostra exemplos das topologias citadas. Ainda segundo Dutta e Rouskas [START_REF] Dutta | Trac grooming in WDM networks: Past and future[END_REF], se G é uma árvore em cadeia, a segunda parte do problema, a alocação dos comprimentos de onda, é equivalente ao problema de coloração em grafos de intervalos e pode ser resolvido em tempo linear por um algoritmo guloso. Se G é uma árvore em estrela, a alocação é equivalente a encontrar o mínimo número de cores em arestas de um grafo bipartido, o qual pode ser resolvido em tempo polinomial combinando os teoremas de Hall e Konig [START_REF] West | Introduction to Graph Theory[END_REF]. Para árvores com topologia spider encontrar o número mínimo de comprimentos de onda é uma tarefa que também pode ser feita em tempo polinomial [START_REF] Wilfong | Ring routing and wavelength translation[END_REF]. Segundo Corteel et al. [START_REF] Corteel | The permutation-path coloring problem on trees[END_REF], caso G seja uma árvore com uma topologia geral, ou seja, uma topologia diferente das denidas até então, o problema de minimizar o número de comprimentos de onda é NP-difícil.

Introdução

Seja G = (V, E) um grafo direcionado onde V , v = |V |,
Mostrando que o problema de estabelecer caminhos ópticos é equivalente ao problema de coloração de grafos, Chlamtac et al. [START_REF] Chlamtac | Lightpath communications: An approach to high-bandwidth optical WAN's[END_REF] mostraram que o RWA é NPcompleto para grafos com topologia arbitrária. Isto é, encontrar o número mínimo de comprimentos de onda para alocar todas as requisições é o mesmo que encontrar o 

min λ max (2.1)
s.a:

λ max ≥ ∑ (s,d)∈R λ sd ij , ∀ (i, j) ∈ E (2.2) ∑ j∈V |(i,j)∈E λ sd ij - ∑ j∈V |(j,i)∈E λ sd ji =      r sd i = s, -r sd i = d, ∀ (s, d) ∈ R, i ∈ V 0 caso contrário (2.3) λ sd ij ∈ {0, 1}, ∀ (s, d) ∈ R, (i, j) ∈ E (2.4)
Nesta formulação, cada 'produto' é um caminho óptico da origem até o destino; neste caso não limita-se a capacidade das arestas, mas se necessário a capacidade pode ser entendida como o número de comprimentos de onda suportados em cada bra. Banerjee e Mukherjee [START_REF] Banerjee | A practical approach for routing and wavelength assignment in large wavelength-routed optical networks[END_REF] usaram a relaxação deste modelo juntamente com um procedimento iterativo que a partir da solução do modelo de programação matemática, encontrava possíveis caminhos para cada requisição, aleatoriamente selecionava um destes caminhos e depois realizava a alocação. Esta formulação é frequentemente utilizada para obter limites inferiores para o problema. Isto se deve ao fato de que mesmo se resolvido na integralidade o modelo não apresenta uma solução completa. Por exemplo, se resolvermos a instância apresentada na Figura 2.1 obteriamos a seguinte solução: Uma conguração de roteamento c é independente se pode realizar a c sd conexões para todo (s, d) ∈ R sobre o grafo G simultaneamente usando somente um comprimento de onda. Seja C o conjunto de todos as possíveis congurações de roteamento independentes, então a formulação de programação inteira é dada como segue:

λ max = 2 Requisição (1, 6): λ[1, 6, 1, 7] = 1.0 λ[1, 6, 7, 6] = 1.0 Requisição (1, 7): λ[1, 7, 1, 7] = 1.0 Requisição (1, 4): λ[1, 4, 1, 2] = 1.0 λ[1, 4,
(MP) min ∑ c∈C Z c (2.5) s.a: ∑ c∈C a c sd Z c ≥ r sd , ∀ (s, d) ∈ R (2.6) Z c ∈ N, ∀ c ∈ C (2.7)
Cada variável de decisão é Z c = l, se uma conguração de roteamento independente é realizada l vezes usando l comprimentos de onda distintos, onde l é um inteiro não-negativo, ou seja, uma mesma conguração de roteamento independente pode ser usada mais de uma vez, sendo que cada vez utiliza-se de um comprimento de onda diferente. A restrição (2.6) garante que todas as requisições serão atendidas.

A relaxação desta formulação pode ser obtida retirando as restrições de integralidade impostas às variáveis de decisão.

Geralmente, existe um número exponencial de congurações de roteamento independente para uma instância do RWA, isto é, o problema mestre tem um número exponencial de variáveis de decisão. É então, impraticável enumerar todas as possíveis congurações de roteamento independentes. Devido a isso, Lee et al. [START_REF] Lee | An optimization approach to routing and wavelength assignment in WDM all-optical mesh networks without wavelength conversion[END_REF] apresentaram também uma estratégia baseada em Geração de Colunas [START_REF] Gilmore | A linear programming approach to the cutting stock problem[END_REF] e um algoritmo branch-and-price para a resolução do problema. O método se mostrou capaz de conseguir boas soluções e, ao mesmo tempo, limites inferiores bem fortes.

Limites inferiores

Nesta seção serão apresentadas algumas metodologias para obtenção de limites inferiores para o problema de roteamento e alocação de comprimentos de onda com o objetivo de minimizar o número de comprimentos de onda. Geralmente, para a obtenção de limites superiores, quando o objetivo é maximizar o número de requisições atendidas, são usadas as próprias formulações apresentadas na seção anterior.

Para problemas com uma matriz de tráfego onde uma conexão deve ser estabelecida entre todos os pares de vértices (v × (v -1) requisições) Baroni e Bayvel [START_REF] Baroni | Wavelength requirements in arbitrarily connected wavelength-routed optical networks[END_REF] obtiveram limites inferiores introduzindo cortes no grafo. Seja um corte no grafo G Em 2009, Fisher et al. [START_REF] Fischer | Solving the routing and wavelength assignment problem with a multilevel distributed memetic algorithm[END_REF] adaptaram o modelo apresentado por Banerjee e Mukherjee [START_REF] Banerjee | Practical approaches for routing and wavelength assignment in large all-optical wavelength routed networks[END_REF] e relaxando a restrição de continuidade do comprimento de onda apresentaram um algoritmo para obter limites inferiores para o RWA. A Tabela 2.1, apresentada em [START_REF] Fischer | Solving the routing and wavelength assignment problem with a multilevel distributed memetic algorithm[END_REF], mostra uma comparação dos valores para os limites inferiores obtidos entre a metodologia apresentada por Fisher et al. [START_REF] Fischer | Solving the routing and wavelength assignment problem with a multilevel distributed memetic algorithm[END_REF] e Skorin-Kapov [START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF]. A primeira coluna mostra as instâncias testadas, a segunda coluna mostra os resultados do modelo (MCF) e a última coluna os resultados do método apresentado em Skorin-Kapov [START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF].

denido por V 1 e V 2 , isto é, V 1 ∩ V 2 = ⊘ e V 1 ∪ V 2 = V e seja C o
(MCF) min( max

(i,j)∈E ∑ (s,d)∈R λ sd ij + ∑ (s,d)∈R λ sd ji ) (2.8)
s.a: 

λ sd ij + λ sd ji ≤ r sd , ∀ (s, d) ∈ R, (i, j) ∈ V (2.9) ∑ j∈V |(i,j)∈E λ sd ij - ∑ j∈V |(j,i)∈E λ sd ji =      r sd , i = s -r sd , i = d, ∀ (s, d) ∈ R, i ∈ V 0, caso contrário (2.10)
λ sd ij ≥ 0, ∀ (s, d) ∈ R, (i, j) ∈ E (2.

Heurísticas e Metaheurísticas

Na literatura são encontradas diversas estratégias para a resolução do problema de roteamento e alocação de comprimentos de onda com o objetivo de minimizar o número de comprimentos de onda utilizados. Algumas dessas estratégias decompõem o problema em duas partes ( [START_REF] Li | The partition coloring problem and its application to wavelength routing and assignment[END_REF], [START_REF] Banerjee | A practical approach for routing and wavelength assignment in large wavelength-routed optical networks[END_REF], [START_REF] Noronha | Routing and wavelength assignment by partition colouring[END_REF]). Primeiramente é calculada uma rota para cada conexão, em seguida são atribuídos comprimentos de onda para cada uma dessas rotas, de acordo com uma solução de um problema de coloração de grafos [START_REF] Brelaz | New methods to color the vertices of a graph[END_REF]. Outras estratégias tratam dos dois problemas em conjunto ( [START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF], [START_REF] Manohar | Routing and wavelength assignment in optical networks from edge disjoint path algorithms[END_REF]).

Inspirados em Conway et al. [START_REF] Conway | Theory of Scheduling[END_REF], Chlamtac et al. [START_REF] Chlamtac | Lightpath communications: An approach to high-bandwidth optical WAN's[END_REF] procedimento Greedy -EDP -RW A(G, R) m Greedy -EDP -RW A Figura 2.5: Pseudocódigo do algoritmo Greedy-EDP-RWA -Adaptado de [START_REF] Manohar | Routing and wavelength assignment in optical networks from edge disjoint path algorithms[END_REF] Banerjee e Sharan [START_REF] Banerjee | A evolutionary algorithm for solving the single objective static routing and wavelength assignment problem in WDM networks[END_REF] utilizaram um algoritmo evolucionário para determinar o roteamento e resolveram o problema de alocação dos comprimentos de onda como um problema de coloração de grafos. A alocação de comprimentos de onda é resolvida como um problema de coloração de grafos onde cada conexão da topologia virtual é um vértice em um novo grafo, dito P (G). Cada vértice em P (G) é conectado a outro vértice por uma aresta não direcionada se o seu caminho divide uma mesma aresta na topologia física [START_REF] Manohar | Routing and wavelength assignment in optical networks from edge disjoint path algorithms[END_REF].

1 d ← max(diametro(G), √ E); 2 R ′ ← R; {Conjunto auxiliar com as requisições ainda não alocadas} 3 λ ← 0; {Contador do número de comp. de onda usados} 4 Enquanto (R ′ ̸ = ⊘) faça 5 λ ← λ + 1; 6 G ′ ← G;
Li e Simha [START_REF] Li | The partition coloring problem and its application to wavelength routing and assignment[END_REF] propuseram resolver o problema de roteamento e alocação de comprimentos de onda através da resolução do problema de coloração de partições (PCP), uma extensão do problema de coloração de grafos. Neste trabalho os autores adaptaram seis métodos de construção aplicados à coloração de grafos. Os melhores resultados foram obtidos com o algoritmo onestepCD (One Step Color Degree). Este algoritmo é uma variante da heurística de coloração baseada no grau de cada vértice procedimento OneStepCD(G)

1 Remova de G todas as arestas (i, j) ∈ E : i, j ∈ V k para todas as partições k = 1, . . . , q; 2 V ′ ← ⊘; {Conjunto de vértices já coloridos} 3 Enquanto |V ′ | < q faça 4 X ← ⊘; {Conjunto de vértices candidatos a receber uma cor}

5 para k = 1 até q : V k ∩ V ′ = ⊘ faça; 6 X ← X ∪ argmin{CD(i) : i ∈ V k }; 7 m-para 8 x ← argmax{CD(i) : i ∈ X}; 9 V ′ ← V ′ ∪ {x}; 10
Assinale a menor cor possível a x; {Cor que não gera conito de coloração} 11 Remova de G todos os vértices em V c(x) \ {x}; 12 m-enquanto m OneStepCD Figura 2.6: Pseudocódigo do algoritmo OneStepCD -Adaptado de [START_REF] Noronha | Routing and wavelength assignment by partition colouring[END_REF] Noronha et al. [START_REF] Noronha | Routing and wavelength assignment by partition colouring[END_REF] utilizaram a estratégia apresentada no trabalho de Manohar et al. [START_REF] Manohar | Routing and wavelength assignment in optical networks from edge disjoint path algorithms[END_REF] para gerar dois caminhos para cada conexão, o caminho é descartado caso seja criado um caminho igual, e depois utilizaram um procedimento baseado em Busca Tabu [START_REF] Glover | Tabu search[END_REF] para denir as atribuições dos comprimentos de onda como um problema de coloração de partições [START_REF] Li | The partition coloring problem and its application to wavelength routing and assignment[END_REF]. Depois de denidos os caminhos de cada requisição a solução inicial é gerada pelo algoritmo OneStepCD proposto por Li e Simha [START_REF] Li | The partition coloring problem and its application to wavelength routing and assignment[END_REF] usando (λ + 1) cores. O procedimento de Busca Tabu então aplica uma busca local como descrito a seguir: uma solução inviável com λ cores é criada recolorindo-se aleatoriamente com uma das λ primeiras cores todos os vértices originalmente coloridos com a cor (λ + 1). Um conito de coloração ocorre quando dois vértices adjacentes em duas partições diferentes são coloridos com a mesma cor.

O procedimento de busca local investiga uma a uma as componentes cujos vértices coloridos estejam envolvidos em um conito de coloração. O método procura dentro de cada componente um vértice não-colorido que possa ser colorido ou um vértice colorido que possa ser recolorido com outra cor de modo a reduzir o número total de conitos de coloração. Caso exista um vértice nesta situação, o algoritmo aplica as modicações apropriadas de coloração e move-se para uma nova solução, a partir da qual a busca recomeça. Caso contrário, uma nova componente é investigada.

A busca é interrompida quando uma solução viável com λ cores é identicada. A seguir, a viabilidade desta coloração é destruída e dispara-se a busca por outra coloração, agora com (λ -1) cores. Este procedimento termina após a realização de um número máximo de iterações ter sido efetuado sem que uma solução viável tenha sido encontrada. A cada iteração da busca tabu, um par (vértice, cor) dene um movimento a ser inserido na lista tabu. A Figura 2. [START_REF] Spears | On the virtues of parameterized uniform crossover[END_REF]. Experimentos computacionais foram conduzidos sobre as instâncias mais estudadas na literatura bem como as novas instâncias introduzidas em [START_REF] Noronha | Ecient implementation of heuristics for routing and wavelength assignment[END_REF]. O algoritmo genético proposto alcançou melhores resultados do que os métodos propostos até então. Noronha et al. [START_REF] Noronha | A biased random-key genetic algorithm for routing and wavelength assignment[END_REF] mostraram que o método apresentou soluções melhores ou iguais a aquelas encontradas por um multistart-BFD usando em média 23% de tempo a menos e reduziram em média à metade os desvios encontrados pelo esquema de decomposição apresentado em [START_REF] Noronha | Ecient implementation of heuristics for routing and wavelength assignment[END_REF].

Conclusão

Neste capítulo foi apresentada uma revisão acerca do problema de roteamento e alocação de comprimentos de onda. Foram mostradas as formas como este problema é tratado na literatura, com variações na função objetivo e na maneira em que as requisições são tratadas. Além disso, foram discutidos os principais métodos heurísticos para a resolução do RWA com o objetivo de minimizar o número de comprimentos de onda em sua versão estática.

procedimento T S -P CP (G, S, maxC) Construa uma solução S ′ recolorindo aleatoriamente com maxC -1 cores todos os vértices de cor maxC; Inicialize a Lista Tabu; Iter ← 0; Seja Q o conjunto formado por todas as componentes envolvidos em conitos em m T S -P CP Figura 2.7: Pseudocódigo do algoritmo TS-PCP -Adaptado de [START_REF] Noronha | Routing and wavelength assignment by partition colouring[END_REF] procedimento BF D -RW A(G, R) m BF D -RW A Figura 2.8: Pseudocódigo do algoritmo BFD-RWA -Adaptado de [START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF] Capítulo 3

S ′ ; Enquanto Q ̸ = ⊘ faça Aleatoriamente selecione k ∈ Q e atualize Q ← Q \ {k}; Reduziu ← .F alse; maxConf litos ← ∞; Para cada i ∈ V k para cada l = 1, . . . ,
1 d ← max(diametro(G), √ |E| 

Metaheurísticas aplicadas ao Problema de Roteamento e Alocação de Comprimentos de Onda

Neste capítulo serão apresentados alguns métodos para a resolução do problema de roteamento e alocação de comprimentos de onda com o objetivo de minimizar o número de comprimentos de onda utilizados para uma certa conguração de demanda, onde as demandas são predeterminadas, ou seja, a versão estática do problema.

Antes, denimos uma solução viável por uma partição de Γ em W subconjuntos tais que existam caminhos disjuntos para todas as requisições pertencentes a cada

Γ w , w = 1, . . . , W , em G. Cada Γ w ⊆ Γ induz um subgrafo G w = (V, E w ) de G onde E w = E - ∪ r∈Γw E r .
Em outras palavras, G w contém os arcos não usados para rotear requisições em Γ w . Nesta seção serão apresentados a forma de representação computacional de uma solução para o problema, a forma de geração de uma solução inicial, a estrutura de vizinhança e os métodos usados para a resolução do RWA, no caso, o método de descida em vizinhança variável e a metaheurística Busca Tabu. O pseudocódigo desse algoritmo, em que se considera o renamento de uma solução s utilizando uma função de avaliação f , a ser minimizada, e um conjunto Φ de k max diferentes vizinhanças Φ = {Φ (1) , Φ (2) ,

Representação da Solução

• • • , Φ (kmax) }, é apresentado pela Figura 3.2.
procedimento VND(f(.),Φ(.),k max ,s) O método BFD é usado tanto na geração da solução quanto no renamento da solução. No renamento o BFD é chamado sobre o subconjunto de requisições pertencentes aos subgrafos predenidos, de acordo com a vizinhança explorada. Caso o número de subgrafos necessários para acomodar este subconjunto de requisições seja menor ao m da chamada do método, isto signica que houve uma melhora e a solução é atualizada.

Método Híbrido VND-BT

A metaheurística Busca Tabu é um procedimento de otimização local que admite soluções de piora. Em sua forma clássica, a cada iteração procura-se um ótimo local selecionando-se o melhor vizinho s ′ de um subconjunto V da vizinhança Φ(s) da solução corrente s. Independentemente de f (s ′ ) ser melhor ou pior que f (s), s ′ será sempre a nova solução corrente. Entretanto, apenas esse mecanismo não é suciente para escapar de ótimos locais, uma vez que pode haver retorno a uma solução previamente gerada. Para evitar isso, o algoritmo usa o conceito de lista tabu. Esta lista dene todos os movimentos que têm um certo atributo como sendo tabu por um determinado número de iterações, conhecido como tempo tabu. Tais movimentos são proibidos a menos que a solução satisfaça a um certo critério de aspiração A, em geral que essa solução seja melhor que a melhor solução encontrada até então. Os atributos são escolhidos para prevenir o retorno a soluções visitadas recentemente e são escolhidos por características que são fáceis para detectar. O pseudocódigo genérico do algoritmo é apresentado pela Figura 3.5. Detalhes adicionais desse algoritmo podem ser encontrados em [START_REF] Glover | Tabu search[END_REF][START_REF] Glover | Future paths for integer programming and links to articial intelligence[END_REF].

A Busca Tabu apresentada em [START_REF] Noronha | Routing and wavelength assignment by partition colouring[END_REF] foi adaptada para fazer parte de um procedimento híbrido para a resolução do RWA. O método híbrido age da seguinte maneira: ao se esgotarem as vizinhanças exploradas pelo VND apresentado na Seção 3.2.1 temos um subconjunto de requisições alocados em um subconjunto de subgrafos (Comprimentos de Onda). Para cada requisição já temos nesse ponto dois caminhos, um gerado durante a construção da solução inicial e outro gerado na última procedimento BuscaTabu(f(.),N(.),s) Na vizinhança Φ 2 o primeiro passo é tentar arrumar um novo espaço para r no grafo G w ′ transferindo o máximo de requisições possíveis de Γ w ′ para outros subconjuntos de Γ diferentes de Γ w. Se é possível realocar ao menos uma requisição de Γ w ′ , então podemos tentar alocar r neste subconjunto. Em caso de sucesso, passamos para a próxima requisição em L w, se existir, através da vizinhança Φ 1 . Caso contrário, passamos para a vizinhança Φ 3 ainda com a mesma requisição r sob análise. Assuma que os subconjuntos da partição foram construídos em uma dada ordem, w = 1, . . . , W . Em cada nova busca através de Φ 2 somente uma partição é selecionada, de acordo com a ordem de criação dos subconjuntos. Isto é, se a busca falha, nós não tentamos aplicar um movimento considerando um outro grafo, mas passamos à vizinhança Φ 3 . Então, na próxima chamada à vizinhança Φ 2 o grafo a ser considerado será G w ′ +1 (assumindo w ̸ = w ′ + 1), se w ′ + 1 > W , recomeçamos em G 1 . Como devemos vericar a existência de um caminho para cada requisição de Γ w ′ e no pior caso iremos vericar em todos os subconjuntos, a complexidade deste

movimento é de O((|Γ w ′ | • (|E| + |V |)) • (W -2)).
Um movimento na vizinhança Φ 3 tenta trocar a requisição r com uma outra requisição pertencente a um subconjunto de Γ diferente de Γ w. Dada uma requisição u, seja min spl (u) o número de arcos do caminho mínimo entre s u e d u em G. A busca considera requisições com min spl menor que min spl (r), ordenadas em ordem crescente do min spl . Se uma requisição r ′ ∈ Γ w ′ , tal que r pode ser roteado no subgrafo induzido em G por Γ w ′ -{r ′ }, e r ′ no subgrafo induzido por Γ w -{r}, é encontrado, então o movimento de troca com r e r ′ é feito. Assim, depois de um movimento em Φ 3 nós temos r ′ ∈ Γ w e r ∈ Γ w ′ . Note que um movimento em Φ 3 não reduz |Γ w|, mas como ele troca r por r ′ , e min spl (r ′ ) < min spl (r), isto pode permitir uma realocação de r ′ usando Φ 1 ou Φ 2 na sequência. Se nenhuma troca é possível em Φ 3 , passamos à fase de perturbação. Isto signica que o método VND falhou em esvaziar L w, e ele não será aplicado a outro subconjunto da partição. Ao invés disto, um procedimento é aplicado para perturbar a solução corrente antes de uma nova tentativa do VND. A complexidade do movimento é

de O(|Γ| • (|E| + |V |)).

A Figura 3.6 ilustra os movimentos de busca através das vizinhanças do VND.

A ideia na parte 3.6a é mover uma requisição r de Γ w para um subconjunto Γ i , i = 1, . . . , W , com i ̸ = w. A parte 3.6b mostra a tentativa de acomodar r em Γ w ′ realocando o máximo possível de requisições pertencenter a Γ w ′ . A parte 3.6c representa movimentos de troca. 

′ em cada subconjunto Γ w ′ , Γ w ′ ⊆ Γ -Γ w, da partição. Seja G a w ′ = (V, E a w ′ ) o subgrafo de G onde E a w ′ = E -∪ r∈Γ w ′ -{r ′ } E r (
os arcos usados para rotear r ′ são reativados em G a w ′ ). A perturbação é feita para encontrar a melhor maneira de atribuir W -1 requisições em W -1 subconjuntos.

O custo de atribuir a requisição i ∈ Γ w i ao subconjunto Γ j é dado como segue:

• c ij = 2, se j = w i ; {Custo de retornar a requisição ao conjunto de origem}

• c ij = ∞, se não existe caminho para rotear a requisição i no grafo G a j ; Nesta seção apresentaremos algumas análises feitas sobre o impacto das componentes isoladas do método VND e -ILS 5p . Todas as análises foram feitas utilizando as mesmas instâncias usadas para a comparação com o método GA-RWA [START_REF] Noronha | A biased random-key genetic algorithm for routing and wavelength assignment[END_REF]. Estas instâncias, além de se mostrarem as mais difíceis de serem resolvidas, são bem representativas.

• c ij = 1 - min spl (i) min spl (i)(G a j ) -max{min spl (i)(G a i ) -min spl (G a j }, 0),
A primeira análise executada foi com respeito à dependência do método sobre cada uma das vizinhanças. Realizamos cinco experimentos, utilizando somente a vizinhança Φ 1 , somente a vizinhança Φ 2 , e as combinações Φ 1 + Φ 2 , Φ 1 + Φ 3 e Φ 2 + Φ 3 . A vizinhança Φ 3 não foi testada isoladamente já que ela não é capaz de mudar a cardinalidade do comprimento de onda que se deseja eliminar, pois nesta Outra análise feita foi com relação ao tempo gasto em cada etapa e a efetividade de cada uma das vizinhanças desenvolvidas. A Tabela 3.17 apresenta os resultados deste estudo. As colunas indicadas com t apresentam a porcentagem média de tempo que a etapa correspondente utilizou para cada instância. Observamos que a média foi feita sobre 5 execuções. Por exemplo, a coluna t Φ 1 indica a porcentagem de tempo gasto pelo método na vizinhança Φ 1 e t p indica a porcentagem de tempo na fase de perturbação do método. As colunas indicadas com e indicam a efetividade de cada vizinhança, ou seja, a porcentagem de vezes que o movimento foi bem sucedido, entendendo como tentativa bem sucedida quando é possível realizar um movimento na vizinhança com a requisição sob análise. No caso da coluna e p é apresentada a porcentagem de vezes em que a fase de perturbação foi bem sucedida, ou seja, conseguiu fazer ao menos uma modicação na estrutura da solução.

Como podemos observar pela Tabela 3.17 as vizinhanças Φ 1 e Φ 2 são as que consomem menos tempo na execução do método com médias de 0.5% e 2.2% respectivamente. Das vizinhanças, Φ 3 é a que consome mais tempo, tendo uma média de 24.4% do tempo total, no entanto, como mostrado na análise anterior apresentada pela Tabela 3.16, esta vizinhança, comparada as outras duas, é a que traz maiores benefícios à solução nal. De maneira global, a fase de perturbação é a que demanda mais tempo durante uma execução com uma média de 70.3% do tempo total, mas os testes preliminares mostraram que o VND sem a fase ILS produz soluções pouco melhores ou iguais ao BFD [START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF]. A fase de perturbação também demanda muito tempo devido a baixa efetividade das vizinhanças desenvolvidas. Para os testes feitos, as buscas na vizinhança Φ 1 obtêm movimentos de sucesso 5.9% das vezes em média, 7.9% para as buscas em Φ 2 e apenas 2% das vezes em Φ 3 . Isto mostra o quão difícil é rearranjar as requisições entre os grafos após uma solução ser construída e essa diculdade se torna cada vez maior à medida que nos aproximamos da solução ótima. A efetividade da fase de perturbação não apresenta um padrão único para todas as instâncias, variando entre 9.7% à 100.0% e tendo como média 69.6%.

Tabela 3.16: Análise da dependência de cada vizinhança blemas menores e estes subproblemas são resolvidos de forma exata. Dessa forma, é importante que se tenham modelos matemáticos que resolvam pequenas instâncias em um tempo razoável ( [START_REF] Martins | Grasp with hybrid heuristic-subproblem optimization for the multi-level capacitated minimum spanning tree problem[END_REF], [START_REF] Uchoa | Branch-and-cut and hybrid local search for the multi-level capacitated minimum spanning tree problem[END_REF]). Ainda apresentaremos alguns modelos baseados na estratégia de geração de colunas e uma nova abordagem será proposta.

Φ 1 Φ 2 Φ 1 + Φ 2 Φ 1 + Φ 3 Φ 2 +

Modelos compactos

Krishnaswamy e Sivarajan [START_REF] Krishnaswamy | Algorithms for routing and wavelength assignment based on solutions of lp-relaxation[END_REF] apresentaram um modelo com o objetivo de maximizar o número de requisições estabelecidas baseado em arcos. Seja x i = 1 se a requisição i é estabelecida e x i = 0 caso contrário. Seja x λ i = 1 se o comprimento de onda λ suporta a requisição i e x λ i = 0 caso contrário. Seja x λ ie = 1 se o comprimento de onda λ suporta a requisição i usando o arco e e x λ ie = 0 caso contrário. Con-sidere ω + (j) e ω -(j), respectivamente, o conjunto de arcos que saem e que entram no vértice j. Neste modelo temos um número limitado de comprimentos de onda disponíveis, assim consideramos também Λ o conjunto de comprimentos de onda.

(KS) max

∑ i∈R x i (4.1)
s.a:

∑ e∈ω + (j) x λ ie = ∑ e∈ω -(j) x λ ie , ∀ i ∈ R, j ∈ V \ {s i , d i }, λ ∈ Λ (4.2) ∑ e∈ω + (s i ) x λ ie - ∑ e∈ω -(s i ) x λ ie = x λ i , ∀ i ∈ R, λ ∈ Λ (4.3) ∑ e∈ω -(d i )
x λ ie -

∑ e∈ω + (d i ) x λ ie = x λ i , ∀ i ∈ R, λ ∈ Λ (4.4) ∑ i∈R x λ ie ≤ 1, ∀ e ∈ E, λ ∈ Λ (4.5) ∑ λ∈Λ x λ i = x i , ∀ i ∈ R (4.6) x λ ie ≤ x λ i , ∀ i ∈ R, e ∈ E, λ ∈ Λ (4.7) x i , x λ i , x λ ie ∈ {0, 1}, ∀ i ∈ R, e ∈ E, λ ∈ Λ (4.8)
Os três primeiros conjuntos de restrições garantem a continuidade do comprimento de onda. O conjunto de restrições (4.5) garante que um mesmo comprimento de onda não será usado em duas ou mais requisições utilizando um mesmo arco.

O conjunto de restrições (4.6) faz com que se uma requisição é atendida ela será atendida por um único comprimento de onda. Finalmente, o conjunto de restrições (4.7) garante a consistência entre as variáveis x λ ie e x λ i . As soluções apresentadas por este modelo podem conter ciclos; no entanto, estes ciclos não afetam o valor da função objetivo. No trabalho apresentado por Jaumard et al. [START_REF] Jaumard | Comparison of ILP formulations for the RWA problem[END_REF], o modelo (KS) é alterado eliminando-se o conjunto de variáveis x i que indicam se a requisição i é atendida ou não, substituindo as restrições (4.3), (4.4) e (4.6), respectivamente pelas restrições (4.11), (4.12) e (4.14) e introduzindo dois novos conjuntos de restrições, um para impedir que arcos sejam ativados para requisições sem que existam comprimentos de onda alocados para estas requisições (4.15), e outro de modo a eliminar os possíveis ciclos que envolvem os vértices origem e destino das requisições (4.16). O modelo é apresentado a seguir: 

x λ ie = ∑ e∈ω -(j) x λ ie , ∀ i ∈ R, j ∈ V \ {s i , d i }, λ ∈ Λ (4.10) ∑ e∈ω + (s i ) x λ ie = x λ i , ∀ i ∈ R, λ ∈ Λ (4.11) ∑ e∈ω -(d i ) x λ ie = x λ i , ∀ i ∈ R, λ ∈ Λ (4.12) ∑ i∈R x λ ie ≤ 1, ∀ e ∈ E, λ ∈ Λ (4.13) ∑ λ∈Λ x λ i ≤ 1, ∀ i ∈ R (4.14) x λ ie ≤ x λ i , ∀ i ∈ R, e ∈ E, λ ∈ Λ (4.15) ∑ e∈ω -(s i ) x λ ie = ∑ e∈ω + (d i )
x λ ie = 0, ∀ i ∈ R, λ ∈ Λ (4.16)

x λ i , x λ ie ∈ {0, 1}, ∀ i ∈ R, e ∈ E, λ ∈ Λ (4.17)
Uma comparação de modelos de programação matemática para o RWA com o objetivo de maximizar o número de conexões estabelecidas pode ser encontrada em [START_REF] Jaumard | ILP Formulations and Optimal Solutions for the RWA Problem[END_REF], [START_REF] Jaumard | ILP formulations for the RWA problem for symmetrical systems[END_REF] 

∑ λ∈Λ ∑ e∈ω + (s i ) x λ ie = x i , ∀ i ∈ R (4.18) ∑ λ∈Λ ∑ e∈ω -(d i ) x λ ie = x i , ∀ i ∈ R (4.19) ∑ λ∈Λ ∑ e∈ω -(s i ) x λ ie = ∑ λ∈Λ ∑ e∈ω + (d i ) x λ ie = 0, ∀ i ∈ R (4.
x λ ie - ∑ e∈ω -(j) x λ ie = 0 , ∀ i ∈ R, j ∈ V \ {s i , d i }, λ ∈ Λ (4.23) ∑ λ∈Λ ∑ e∈ω + (s i ) x λ ie = x i , ∀ i ∈ R (4.24) ∑ λ∈Λ ∑ e∈ω -(d i ) x λ ie = x i , ∀ i ∈ R (4.25) ∑ i∈R x λ ie ≤ 1 , ∀ e ∈ E, λ ∈ Λ (4.26) ∑ λ∈Λ ∑ e∈E x λ ie ≤ (|V | -1) × x i , ∀ i ∈ R (4.27) ∑ λ∈Λ ∑ e∈ω -(s i ) x λ ie = ∑ λ∈Λ ∑ e∈ω + (d i )
x λ ie = 0 , ∀ i ∈ R, λ ∈ Λ (4.28)

x i , x λ ie ∈ {0, 1} , ∀ i ∈ R, e ∈ E, λ ∈ Λ (4.29) 
Repare que neste modelo as variáveis x λ i foram eliminadas. 

∑ λ∈Λ ∑ e∈ω + (s i ) x λ ie = ∑ λ∈Λ x λ i , ∀ i ∈ R (4.30) ∑ λ∈Λ ∑ e∈ω -(d i ) x λ ie = ∑ λ∈Λ x λ i , ∀ i ∈ R (4.31) ∑ λ∈Λ ∑ e∈ω -(s i ) x λ ie = ∑ λ∈Λ ∑ e∈ω + (d i )
x λ ie = 0, ∀ i ∈ R (4.32)

Para impedir ciclos formados por requisições não atendidas podemos substituir a restrição (4.15) do modelo (JMT) por: 

∑ λ∈Λ ∑ e∈E x λ ie ≤ (|V | -1) × ∑ λ∈Λ x λ i , ∀ i ∈ R (4.
∑ e∈ω + (j) x λ ie - ∑ e∈ω -(j) x λ ie = 0 , ∀ i ∈ R, j ∈ V \ {s i , d i }, λ ∈ Λ (4.35) ∑ λ∈Λ ∑ e∈ω + (s i ) x λ ie = ∑ λ∈Λ x λ i , ∀ i ∈ R (4.36) ∑ λ∈Λ ∑ e∈ω -(d i ) x λ ie = ∑ λ∈Λ x λ i , ∀ i ∈ R (4.37) ∑ i∈R x λ ie ≤ 1 , ∀ e ∈ E, λ ∈ Λ (4.38) ∑ λ∈Λ x λ i ≤ 1 , ∀ i ∈ R (4.39) ∑ λ∈Λ ∑ e∈E x λ ie ≤ (|V | -1) × ∑ λ∈Λ x λ i , ∀ i ∈ R (4.40) ∑ λ∈Λ ∑ e∈ω -(s i ) x λ ie = ∑ λ∈Λ ∑ e∈ω + (d i )
x λ ie = 0 , ∀ i ∈ R (4.41)

x λ i , x λ ie ∈ {0, 1} , ∀ i ∈ R, e ∈ E, λ ∈ Λ (4.42)
Repare que para o modelo RWA2 as variáveis permanecem as mesmas do modelo JMT.

A seguir apresentamos um exemplo para ilustrar que as soluções providas pelos dois modelos modicados são soluções viáveis para o problema de roteamento e alocação de comprimentos de onda. O teste foi feito sobre a mesma instância da seção anterior.

As soluções encotrandas pelos dois modelos foram exatamente iguais e são apresentadas pela Figura 4.4. Note que a solução apresentada não apresenta ciclo algum, apesar disto não ter sido evitado explicitamente. 

c(w l ) = -u 0 + ∑ (s,d)∈R a l sd u 1 sd
Assim, o subproblema pode ser escrito como:

max c AU X-M AX-IS (α) = -u 0 + ∑ (s,d)∈R ∑ p∈P sd u 1 sd α p (4.48)
s.a: 

α p + α p ′ ≤ 1, ∀ (r p , r p ′ ) ∈ E W (4.49) α p ∈ {0, 1}, ∀ p ∈ P ( 4 
∑ c∈C a c sd w c ≤ r sd , ∀ (s, d) ∈ R (4.53) w c ∈ N, ∀ c ∈ C (4.54)
Sejam (u 0 , u 1 sd ) as variáveis duais da solução ótima do modelo IRC relaxado. O custo reduzido c(w c ) pode ser calculado como:

c(w c ) = -u 0 + ∑ (s,d)∈R
(1 -u 1 sd )a c sd . O subproblema do modelo IRC apresenta as mesmas restrições do subproblema MAX-IRC que será apresentado a seguir. A diferença é somente a função objetivo.

Em [START_REF] Jaumard | On column generation formulations for the RWA problem[END_REF] é feita uma revisão acerca de modelos de geração de colunas para o RWA com o objetivo de maximizar o número de conexões estabelecidas e algumas melhorias são sugeridas. Além disso, combinando as ideias de Ramaswami e Sivarajan [START_REF] Ramaswami | Routing and wavelength assignment in all-optical networks[END_REF] e Lee et al. [START_REF] Lee | Optimal routing and wavelength assignment in WDM ring networks[END_REF], Jaumard et al. [START_REF] Jaumard | On column generation formulations for the RWA problem[END_REF] 

α sd e = ∑ e∈ω -(i) α sd e , ∀ (s, d) ∈ R, i ∈ V \ {s, d} (4.62) ∑ e∈ω + (s) α sd e ≤ r sd , ∀ (s, d) ∈ R (4.63) ∑ e∈ω -(s) α sd e = 0, ∀ (s, d) ∈ R ( 4 
a c 1 = ( 1 0 
) , a c 2 = ( 0 1 
)

, a c 3 = ( 0 2 
) .

Repare que o vetor de coecientes a c 2 indica que é possível construir uma conguração de roteamento independente com apenas um caminho atendendo a requisição 2, sem especicar qual caminho será este (caminho implícito).

Para o modelo MAX-IS os coecientes seriam representados por:

a l 1 =   1 0 0   , a l 2 =   0 1 0   , a l 3 =   0 0 1   , a l 3 =   0 1 1   .
Se as demandas forem unitárias e se utilizarmos as restrições ( 

y sd ≤ ∑ l∈Lr a l sd w l + ∑ c∈Cmax a c sd w c , ∀ (s, d) ∈ R (4.73) y sd ≤ r sd , ∀ (s, d) ∈ R (4.74) w c ∈ N, ∀ c ∈ C max (4.75) w l ∈ N, ∀ l ∈ L r ( 4 

Trabalhos Futuros

Como trabalhos futuros sugere-se aprofundar o estudo da nova abordagem para geração de colunas proposta e o desenvolvimento de um algoritmo Branch-andprice para a resolução do problema. Também sugere-se a implementação de outros métodos heurísticos e o estudo da inuência de certas requisições que dicultam a resolução do problema.

Ainda como trabalhos futuros sugerimos o estudo sobre o problema de concentração de tráfego (trac grooming), uma extensão do problema de roteamento e

v

  UNIVERSIDADE FEDERAL DE MINAS GERAIS DEPARTAMENTO DE ENGENHARIA ELÉTRICA PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA Metaheurísticas e Formulações para a resolução do Problema de Roteamento e Alocação de Comprimentos de Onda em Redes Ópticas Autor: Alexandre Xavier Martins PPGEE -EEUFMG Orientador: Rodney Rezende Saldanha Co-orientador: Mauricio Cardoso de Souza Université Blaise Pascal Orientador: Philippe Mahey Co-orientador: Christophe Duhamel Tese apresentada ao Programa de Pós-Graduação em Engenharia Elétrica do Departamento de Engenharia Elétrica da Universidade Federal de Minas Gerais, como parte integrante dos requisitos para a obtenção do título de Doutor em Engenharia Elétrica, área de concentração: Engenharia de Computação e Telecomunicações. Belo Horizonte, 3 de Abril de 2013 Cardinalidade do conjunto de vértices ou número de vértices Γ Conjunto de Requisições por caminhos ópticos r Requisição individual denido por um par origem-destino s r Origem da requisição r d r Destino da requisição r R Matriz de requisições r sd Número de requisições entre os vértices s e d λ sd ij Número de requisições entre os vértices s e d que utilizam o arco (i, j) c Conguração de Roteamento Independente a c Vetor que representa c a c sd Número de caminhos entre os vértices s e d na conguração c C Conjunto de todas as possíveis congurações de roteamento independentes Z c Número de vezes que uma determinada conguração de roteamento independente é utilizada P Conjunto de todos os caminhos elementares P sd Conjunto de todos os caminhos elementares entre os vértices s e d Λ Conjunto de comprimentos de onda disponíveis δ pl Indica se o caminho p pertence ao conjunto independente l w l Número de comprimentos de onda associado ao conjunto independente l y sd Número de requisições atendidas entre os vértices s e d xv Lista de Figuras

  Le multiplexage à répartition fréquentielle (Wavelength Division Multiplexing -WDM): il consiste à séparer le lien en canaux, généralement 1nm; ces canaux correspondent à diérentes longueurs d'onde. Plusieurs données sont envoyées en même temps sur diérents canaux. Techniquement, on utilise des diodes lasers émettant à des longueurs d'ondes diérentes mais assez proches et des multiplexeurs/démultiplexeurs optiques. Ce multiplexage n'est possible qu'avec des bres optiques monomodes. Grâce au WDM, il est possible d'atteindre un débit de 10 Térabits. En plus, il est indépendant du protocole utilisé. L'utilisation du multiplexage par division de longueur d'onde est devenu nécesxx saire pour faire face à la croissance rapide de la demande pour les informations qui circulent à travers les réseaux. Le multiplexage est l'envoi d'un nombre de canaux par les mêmes moyens de communication. Cette technique permet d'expansion de la capacité des systèmes optiques sans besoin d'installer de nouvelles bres. Cette technique permet d'expansion de la capacité des systèmes optiques sans besoin d'installer de nouvelles bres, il permet d'utiliser une bre optique unique comme plusieursbres virtuelles, portant chacune l'une de ces signaux de longueurs d'onde diérentes, quelque soit le format de données eectué. Les connexions entre les n÷uds d'un réseau WDM tout-optique sont établies par des chemins optiques (Lightpaths). Les chemins optiques peuvent concerner un ou plusieurs n÷uds du réseau. Le chemin optique exige l'utilisation d'une longueur d'onde (canal), c'est à dire chaque requête est associée à une longueur d'onde spécique. Un sommet du réseau se compose d'un émetteur/récepteur, multiplexeur/démultiplexeur (MUX / DEMUX), un amplicateur optique et Ajoute/Extrait (Add / Drop -OADM), qui vise à extraire ou à ajouter le trac qui circule sur le réseau.

  d'onde correspond à l'utilisation d'une seule longueur d'onde pour chaque chemin optique d'une origine à une destination [5]. Dans la litérature, le problème de routage et aectation de longueur d'onde (Routing and Wavelength Assignement -RWA) est souvent considéré de deux manières diérentes : soit maximiser le nombre de requêtes traitées, soit minimiser le nombre de longueurs d'onde utilisées. Routage et l'aectation de longueur d'onde -RWA Soit G = (V ; E) un graphe orienté où V est l'ensemble des v = |V | sommets (les commutateurs) et E est l'ensemble des arcs (les bres optiques). On note Γ l'ensemble des requêtes qui exigent de chemins optiques où chaque r ∈ Γ est déni par une paire source-destination (s r , d r ) ∈ V × V . Notez que nous pouvons avoir deux requêtes diérentes pour la même paire source-destination et dans ce cas si elles sont acheminées vers la même longueur d'onde, alors elles doivent être achemineés par des chemins disjoints dans G. Il existe essentiellement deux types de problème de routage et d'allocation de longueurs d'onde, le problème statique dans lequel les requêtes entre les paires source destination sont pré-établies et le problème dynamique dans lequel les requêtes arxxii rivent de temps en temps. Initialement pour qu'une planication du réseau soit plus pratique pour résoudre le problème statique, le trac initial sera évalué et mesuré. Au cours du temps, occasionnellement il y aura l'émergence de nouvelles exigences et des préoccupations ainsi il y aura une attribution successive de chemins individuels, provenant sur la scène dans le problème dynamique. Le RWA est habituellement traité avec deux objectifs distincts. Le premier objectif est de minimiser le nombre de longueurs d'onde, où le problème est de trouver une partition minimum de Γ sur W sous-ensembles telles que les requêtes pour chaque Γ w , w = 1, . . . , W , peuvent être acheminées sur les chemins disjoints dans G. L'autre alternative est de maximiser le nombre de connexions établies pour un nombre limité de longueurs d'onde. Pour répondre à chaque demande, nous avons besoin de déterminer une route et d'aecter une longueur d'onde à cette demande.

Fit

  (BF), First Fit Decreasing (FFD) et Best Fit Decreasing (BFD) sont quatre heuristiques connues pour résoudre le problème du Bin Packing. FF et BF font le tri des éléments au hasard, tandis que FFD et BFD sont triés selon le plus court chemin. FF et FFD font l'aectation à la première longueur d'onde faisable, tandis que BF et BFD font l'aectation à la meilleure longueur d'onde faisable.

  Dans la seconde stratégie le focus du mouvement devient les requêtes individuelles. Nous présentons une heuristique hybride, combinant deux méthodes approchées, une autre version du VND et une heuristique ILS. La solution initiale est construite par une heuristique classique, EDP ou BFD. La VND est utilisée comme Recherche Locale pour améliorer la solution courante. Ses voisinages reposent sur la modication de la longeur d'onde aectée à chaque connexion. La VND est intégrée dans une ILS. La solution obtenue à la n de la VND est perturbée puis ré-optimisée par la VND. Le principe est d'explorer les bassins de solutions proches de la solution courante en essayant de conserver la plupart des bonnes caractéristiques de celle-ci. De plus, en partant d'une solution proche d'un optimum local, l'eort lié à la nouvelle recherche locale est fortement réduit. Nous proposons aussi une perturbation ne modiant pas le nombre total de longueurs d'onde utilisées. Avant d'appliquer un mouvement, il est nécessaire de choisir un sous-graphe. Nous considérons deux alternatives pour choisir sous-graphe. Dans la première variante, notée V N D r , le sous-graphe choisi est celui avec le moins de requêtes, c'est un choix naturel puisque l'objectif est de vider le sous-graphe. Dans la deuxième variante, notée V N D e , le sous-graphe choisi est celui qui a le plus grand nombre d'arcs sans utilisation. Soit une solution réalisable, le VND r ou VND e applique trois types de mouvements pour réorganiser les requêtes entre les sous-graphes an d'éliminer l'un d'eux. Dans les deux cas, les requêtes appartenant au sous-graphe choisis appartiennent à xxviii une liste triée par ordre décroissant en fonction de la taille du plus court chemin dans le graphe G. Le VND parcourt la liste en utilisant les voisinages Φ 1 , Φ 2 et Φ 3 pour essayer de déplacer les requêtes. Si le VND est réussi, le sous-graphe est vide et, par conséquent le nombre de longueurs d'onde peuvent être réduit. Si l'algorithme VND échoue dans le voisinage Φ 3 phase ILS de la méthode est appelée. Nous attirons l'attention sur un mouvement d'amélioration, si cela se produit, ce sera uniquement lorsque la dernière requête du sous-graphe sera transférée dans un autre sous-graphe. Un mouvement dans le voisinage Φ 1 tente d'aecter la première requête, requête r, dans la liste dans un autre sous-graphe de la solution. En cas de succès, nous prenons la prochaine requête de la liste, le cas échéant, on met à jour nombre de longueurs d'onde dans le cas où la liste est vide. En cas d'échec, on passe à la recherche suivante dans le voisinage Φ 2 .

1. 4

 4 Organização do TrabalhoEste trabalho está organizado como segue: No Capítulo 1 é apresentada uma breve introdução e os objetivos são denidos. No Capítulo 2 é feita uma revisão da literatura a respeito do problema de roteamento e alocação de comprimentos de onda, sendo apresentados alguns modelos de programação matemática. Também são discutidos alguns métodos para a obtenção de limites inferiores e métodos baseados em heurísticas e metaheurísticas são apresentados. No Capítulo 3 é apresentada a metodologia proposta e desenvolvida para a obtenção de soluções para o problema de roteamento e alocação de comprimentos de onda; ao m, os resultados são apresentados e comparados com métodos da literatura. No Capítulo 4 são apresentadas duas simplicações em modelos já existentes na literatura além de uma nova abordagem para a geração de colunas aplicada ao RWA. Por m, no Capítulo 5, são apresentadas as conclusões e o que se pretende desenvolver posteriormente.

  representa o conjunto de vértices (comutadores) e E o conjunto de arestas (bras óticas). Nós denotamos por Γ o conjunto de requisições por caminhos ópticos onde cada r ∈ Γ é denido por um par origem-destino (s r , d r ) ∈ V × V . Note que podemos ter duas diferentes requisições com o mesmo par origem-destino e neste caso se elas são roteadas com o mesmo comprimento de onda, então elas devem ser roteadas através de caminhos disjuntos por arestas em G.Basicamente existem dois tipos de problemas de roteamento e alocação de comprimentos de onda, o estático no qual as requisições entre os pares origem destino já estão pré-estabelecidas, e o dinâmico em que as requisições chegam ao longo do tempo.Na literatura do RWA podemos encontrar usualmente pelo menos duas aborda-gens em se tratando do objetivo a ser alcançado. A primeira variante consiste em minimizar o número de comprimentos de onda utilizados, onde o problema é encontrar a mínima partição de Γ em W subconjuntos tal que as requisições em cada Γ w , w = 1, . . . , W , podem ser roteadas em caminhos disjuntos por arestas em G. A outra alternativa é maximizar o número de conexões estabelecidas para um número limitado de comprimentos de onda. Para atender cada requisição entre os pares, origem e destino, necessitamos determinar um caminho direcionado e alocar um comprimento de onda a esta requisição. A restrição que se impõe é que um mesmo comprimento de onda não pode ser utilizado para atender duas ou mais requisições diferentes, se os caminhos dessas requisições utilizam um mesmo arco. Além disso, podemos ter a restrição de continuidade, onde o comprimento de onda alocado a um caminho deve ser utilizado do início ao m deste caminho, sem conversão. Essa restrição será adotada em todo trabalho.

Figura 2 . 1 :

 21 Figura 2.1: Instância estática do RWA

Figura 2 . 2 :

 22 Figura 2.2: Representação da Solução

Figura 2 . 3 :

 23 Figura 2.3: Exemplos de topologias em árvores

2 , 4 ] = 1. 0

 240 Por esta solução, podemos ver que o número de comprimentos de onda é igual a 2. Através da variável λ podemos recuperar os caminhos de cada requisição, onde os dois primeiros índices representam respectivamente a origem e o destino e os dois últimos representam o arco usado, por exemplo λ[1, 4, 1, 2] = 1.0 indica que a requisição (1, 4) utiliza o arco (1, 2), mas não sabemos como os comprimentos de onda foram alocados. Para este exemplo seria fácil encontrar a alocação ótima, mas para instâncias realísticas isso não é trivial. Além disso, outro problema com este modelo é que ele não impede a conversão do comprimento de onda, ou seja, uma mesma requisição pode utilizar vários comprimentos de onda ao longo do caminho. Na verdade o modelo nos indica um limite com relação ao arco mais congestionado, o que não quer dizer, necessariamente, que usando este limite em número de comprimentos de onda se consiga estabelecer todas as conexões. A Figura 2.4 apresenta uma solução viável para uma rede qualquer utilizando três comprimentos de onda. Pelo modelo apresentado anteriormente o número de comprimentos de onda necessários seriam de apenas dois, já que os arcos mais congestionados suportam somente dois comprimentos de onda, mas na verdade o número necessário seria realmente de três, já que os três comprimentos de onda dividem ao menos um arco na solução.

Figura 2 . 4 :

 24 Figura 2.4: Exemplo de solução viável com 3 comprimentos de onda

[ 10 ]

 10 , adaptada ao PCP. Primeiramente, todas as arestas que conectam vértices na mesma partição são removidas. O grau-cor de cada vértice é denido como o número de vértices já coloridos que são a ele adjacentes, CD(i) retorna o grau-cor do vértice i. A cada iteração, o vértice com o menor grau-cor em cada componente da partição é determinado. O vértice com o maior grau-cor dentre estes últimos é selecionado. Este vértice é colorido com a menor cor que não provoca conitos e todos os demais vértices na mesma componente são removidos. Estes passos são repetidos até que cada componente tenha um vértice colorido. No m, o número de cores utilizadas representa o número de comprimentos de onda usados. A Figura 2.6 apresenta o pseudocódigo do método OneStepCD, onde V k representa os vértices da partição k para k = 1, . . . , q.

  7 apresenta um pseudocódigo do algoritmo descrito, onde Conf litos(S) retorna o número de conitos em uma dada solução S, os conitos indicam que vértices adjacentes possuem a mesma cor. A variável maxC representa o número de cores usadas na solução e mais uma vez V k é o conjunto de vértices da partição k.Skorin-Kapov[START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF] propõe quatro heurísticas construtivas similares baseadas em algoritmos utilizados na resolução do Bin Packing. Bin Packing é um problema clássico na literatura da otimização combinatória[START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. Seja uma lista de n itens de vários tamanhos e um conjunto de bins idênticos com capacidade limitada. O problema consiste em armazenar todos os itens da lista no número mínimo de bins sem violar a restrição de capacidade. Como o problema é NP-difícil[START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] diversos algoritmos têm sido propostos para a sua resolução. Um estudo mais aprofundado sobre o problema pode ser encontrado nos trabalhos de Alvim et al.[START_REF] Alvim | A hybrid improvement heuristic for the one-dimensional bin packing problem[END_REF], Coman et al.[START_REF] Coman | Bin packing approximation algorithms: A survey[END_REF] e Coman et al.[START_REF] Coman | Bin packing theory[END_REF]. First Fit (FF), Best Fit (BF), First Fit Decreasing (FFD) e Best Fit Decreasing (BFD) são quatro heurísticas conhecidas para a resolução do problema de Bin Packing. As heurísticas FF e BF ordenam aleatoriamente os itens e percorrem o conjunto de bins em uma ordem sequencial alocando os itens. O algoritmo FF coloca o item no primeiro bin possível enquanto o algoritmo BF analisa cada bin e aloca o item naquele considerado "melhor". No caso do RWA, cada requisição é considerada um item. O conceito de melhor bin muda para o problema original e na abordagem adotada para a resolução do RWA. No Bin Packing clássico o melhor bin é aquele que ca com menos espaço vazio após a alocação de um item, enquanto no RWA o melhor Bin é aquele que aloca uma requisição utilizando o menor número de arcos [50]. Os algoritmos FFD e BFD ordenam os itens em ordem decrescente de tamanho e depois alocam esses itens da mesma maneira dos algoritmos FF e BF respectivamente. Noronha et al. [43] melhoraram o desempenho dos métodos apresentados em [50], trabalharando na estrutura de dados e em estratégias de implementação, tais como, lista de adjacência duplamente encadeada e atualização dinâmica dos caminhos mínimos. Os melhores resultados são observados com uma variante do algoritmo BFD, em que as requisições são ordenadas em ordem decrescente de acordo com o tamanho do menor caminho (tamanho do caminho denido pelo número de arestas) entre a origem e o destino no grafo original. Iterativamente para cada demanda e cada comprimento de onda já atribuido é checado se a requisição pode ser roteada com este mesmo comprimento de onda. O melhor comprimento de onda é denido como aquele com o menor caminho viável entre a origem e o destino. Se nenhum comprimento de onda pode ser atribuido a esta demanda ou se todos os menores caminhos são maiores que um determinado limite, um novo comprimento de onda é gerado e atribuído a esta demanda. A diculdade do algoritmo BFD [50] é que muitas requisições apresentam o mesmo tamanho. Sendo assim as requisições de mesmo tamanho são ordenadas aleatoriamente. Para contornar o fato do BFD ordenar muitas requisições de maneira aleatória, Noronha et al. [44] propuseram um algoritmo genético com chaves randômicas para ordenar as requisições. Os elementos são ordenados segundo seu tamanho e o valor da chave. Os cromossomos são vetores de números reais, denominadas chaves. A cada requisição é associada uma chave de valor entre [0, 1]; na população inicial esse valor é gerado aleatoriamente. As chaves são usadas para a decodicação gerando as soluções viáveis. As requisições são ordenadas de acordo com a soma do tamanho do seu caminho mínimo, entre a origem e o destino, e o valor da chave, depois, então o BFD é aplicado. A resposta do BFD, o número de comprimentos de onda, é usada como tness de cada indivíduo. Para gerar os lhos é utilizada a metodologia proposta em Spears e deJong

A

  solução é representada por um conjunto de caminhos, um caminho para cada requisição, e um conjunto de índices que representa em qual subgrafo a requisição está alocada, lembrando que cada subgrafo representa um comprimento de onda. A Figura 3.1 mostra uma representação parcial de uma solução. A Figura 3.1 (a) mostra uma matriz em que cada linha representa uma requisição, na primeira coluna mostramos o índice da requisição e sua origem e destino. As outras colunas representam os vértices. Esta matriz é responsável por guardar os caminhos que podem ser recuperados pelos predecessores. Por exemplo, a requisição 1 deve ser uma ligação entre os vértices 1 e 4. Pela matriz podemos ver que para chegar em 4 passamos antes pelo vértice 2 e antes desse pelo vértice 1, que é o vértice origem da requisição 1. A Figura 3.1 (b) mostra o vetor usado para representar a alocação dos comprimentos de onda. Em cada posição este vetor nos diz a qual subgrafo a requisição e seu respectivo caminho estão alocados. A Figura 3.1 (c) apresenta os caminhos para as três requisições do exemplo.

Figura 3 . 1 :

 31 Figura 3.1: Representação da Solução

3. 2 . 1

 21 Descida em Vizinhança VariávelO Método de Descida em Vizinhança Variável (Variable Neighborhood Descent, VND), proposto por Mladenovic e Hansen[START_REF] Mladenovic | A variable neighborhood search[END_REF], é um método de renamento que consiste em explorar o espaço de soluções através de trocas sistemáticas de estru-turas de vizinhança, aceitando somente soluções de melhora da solução corrente e retornando à primeira estrutura quando uma solução melhor é encontrada.

Figura 3 . 2 :

 32 Figura 3.2: Algoritmo VND

Figura 3 . 3 :Figura 3 . 4 :

 3334 Figura 3.3: Subgrafos sem os arcos já utilizados

Figura 3 . 5 :

 35 Figura 3.5: Algoritmo Busca Tabu

3. 3 . 1

 31 Descida em Vizinhança Variável Propomos aqui um algoritmo VND com k max = 3. Seja Γ w um subconjunto da partição que caracteriza uma solução viável. Nós consideramos duas alternativas para escolher Γ w. Na primeira alternativa, denotada por V N D r , Γ w é o subconjunto da partição com o menor número de requisições, isto é, w = arg min{|Γ w | : w = 1, . . . , W }, esta é uma escolha natural já que o objetivo é de esvaziar o conjunto. Na segunda alternativa, denotada por V N D e , Γ w é o subconjunto no qual o grafo induzido G w tem o maior número de arcos, isto é, w = arg max{|E w | : w = 1, . . . , W }. A ideia aqui é que mesmo que exista um conjunto possuindo um número menor de requisições, como este conjunto utiliza menos arcos, provavelmente ele possui um número grande de requisições com caminhos mínimos pequenos, que, teoricamente, serão mais fáceis de serem realocados. Em ambos os casos, as requisições pertencentes a Γ w formam uma lista L w ordenada em ordem decrescente segundo o tamanho do caminho mínimo em G entre os nós origem e destino. O método VND percorre L w utilizando as vizinhanças Φ 1 , Φ 2 e Φ 3 para tentar realocar as requisições. Se o VND for bem sucedido, o subconjunto Γ w cará vazio e consequentemente o número de comprimentos de onda poderá ser reduzido. Se o VND falha para alguma requisição na vizinhança Φ 3 a fase de perturbação do método é chamada. Chamamos atenção para que um movimento de melhora, se ele acontece, ocorre somente quando a última requisição de Γ w é realocada em outro subconjunto, enquanto para |Γ w| ≥ 2 os movimentos não reduzem o valor da função objetivo. Quando o VND consegue esvaziar Γ w, nós atualizamos os subconjuntos restantes com respeito ao critério para selecionar o próximo subconjunto no qual o VND será aplicado, de acordo com as alternativas V N D r ou V N D e . Suponha que a busca considere uma requisição r. Um movimento na vizinhança Φ 1 tenta realocar r em outro subconjunto de Γ. Se a vizinhança Φ 1 não é vazia com respeito a uma partição e uma requisição, então existe Γ w ′ ⊆ Γ, w ′ ̸ = w, no qual o grafo induzido G w ′ tem um caminho entre s r e d r . Neste caso a busca em Φ 1 é interrompida quando o primeiro grafo G w ′ para acomodar r é encontrado, e r é transferido de Γ w para Γ w ′ . A busca então continua com a próxima requisição em L w, ou o número de comprimentos de onda é reduzido se r foi a última requisição em L w. Se Φ 1 é vazio, o VND passa para a vizinhança Φ 2 com a mesma requisição r sob análise. Para vericar a existência de um caminho em cada conjunto utilizamos um algoritmo de busca em largura de ordem O(|E| + |V |) [13], logo a complexidade total deste movimento é de O((|E| + |V |) • (W -1)).

  Figura 3.6: Vizinhanças

FiguraFigura 3 . 9 :

 39 Figura 3.8: Instância Finland

Figura 3 . 10 : 20 Figura 3 . 11 :Figura 3 . 12 : 38 Figura 3 . 13 :Figura 3 . 14 :Figura 3 . 16 :Figura 3 . 18 :

 3102031131238313314316318 Figura 3.10: Gráco para instância Att -Alvo 20

6 3. 5 4 Formulações

 654 3 50.1 46.7 3.9 1.4 0.7 74.0 y.4.100.1 0.1 2.5 32.1 64.3 4.5 5.8 3.2 47.1 y.5.100.1 0.1 1.3 37.5 60.2 3.9 2.9 1.5 25.3 y.5.100.2 0.1 0.6 47.0 49.[START_REF] Barr | Grooming telecommunication networks[END_REF] 5.1 2.6 0.8 73.6 Média 0.5 2.2 24.4 70.3 5.9 7.9 2.0 69.Conclusões Neste capítulo foi apresentado o principal método proposto para obtenção de construção de soluções para o Problema de Roteamento e Alocação de Comprimentos de Onda com o objetivo de minimizar o número de comprimentos de onda em sua versão estática com relação às requisiçoes, o Best Fit Decreasing (BFD). Para tentar um renamento maior das soluções geradas, foi proposto um algoritmo baseado em VND que utilizava em sua busca local o próprio método de geração da solução para um pequeno conjunto de requisições. Também foi acrescentado um método híbrido que usava uma Busca Tabu sempre que a busca local do VND era encerrada. Nesta comparação foi vericado que o VND-BFD apresentou os melhores resultados para a maioria das instâncias. Depois apresentamos uma nova abordagem para o VND onde o foco se concentra nas requisições e alguns movimentos podem não causar uma melhora imediata na função objetivo. Para perturbar as soluções geradas pelo VND criamos um algoritmo ILS com duas variações, a primeira onde todas as requisições têm a mesma probabilidade de fazer parte de um problema de atribuição criado para a perturbação e o segundo onde certas requisições apresentam uma probabilidade cinco vezes maior de fazer parte deste problema. Vericamos através de testes computacionais que esta segunda versão, chamada de VND e -ILS 5p , apresentou os melhores resultados. Para esta variante mostramos que os melhores resultados são encontrados quando utillizamos o BFD para a geração da solução inicial, mas mesmo utilizando outro método, o EDP, o algoritmo é capaz de encontrar boas soluções. Foi mostrada uma comparação do VND e -ILS 5p com o Algoritmo Genético apresentado em [44] que até então apresenta os melhores resultados para este problema. O método VND e -ILS 5p proposto se mostrou eciente, tendo melhorado a maioria das instâncias ainda em aberto. Para nalizar, apresentamos um estudo das componentes do VND e -ILS 5p , mostrando o tempo de cada uma das fases e a efetividade destas. Nesta parte, concluímos que as componentes que demandam mais tempo são as que geram maior benefício para a função objetivo. Capítulo para maximizar o número de requisições estabelecidas Neste capítulo serão apresentadas algumas formulações para o RWA. Na literatura, a grande parte dos modelos e métodos exatos são voltados para a resolução do problema com o objetivo de maximizar o número de requisições atendidas. Apresentaremos ainda modicações aos modelos matemáticos baseados em arcos existentes para o problema. O objetivo aqui é deixar os modelos mais 'leves' e com isso conseguirmos resolver instâncias de mesmo tamanho em um tempo menor ou até mesmo instâncias maiores que não são resolvidas pelos modelos existentes. Na literatura recente podemos encontrar trabalhos onde se combinam métodos exatos e métodos heurísticos, em que as heurísticas dividem o problema original em subpro-

  Figura 4.1: NSFnet -[45]

Figura 4 . 2 :

 42 Figura 4.2: Solução do modelo KS

4. 1 . 1

 11 Formulações propostasNesta seção será feita uma análise de algumas restrições dos modelos (KS) e (JMT) e algumas alterações serão sugeridas de forma a facilitar a resolução dos modelos.

Figura 4 . 3 :

 43 Figura 4.3: Solução do modelo JMT

33 )O

 33 segundo modelo é obtido com as modicações sobre o modelo (JMT) que chamaremos de (RWA2) e é apresentado a seguir pelas equações (4.34)-(4

Figura 4 . 4 :

 44 Figura 4.4: Solução dos modelos RWA1 e RWA2

Figura 4 . 5 :

 45 Figura 4.5: Exemplo de conjuntos independentes[START_REF] Jaumard | On column generation formulations for the RWA problem[END_REF] 

. 50 )

 50 onde α p = 1 se o vértice r p pertence ao conjunto independente e 0 caso contrário.O problema deste modelo é que o grafo de conitos pode envolver um número exponencial de vértices. Lee et al.[START_REF] Lee | Optimal routing and wavelength assignment in WDM ring networks[END_REF] introduziram o conceito de conguração de roteamento independente (Independent Routing Conguration), onde cada conguração é implicitamente associada a um conjunto de caminhos que podem ser usados para satisfazer uma fração das requisições utilizando o mesmo comprimento de onda. Uma conguração de roteamento independente C é representada por um vetor a c tal que: a c sd = número de requisições entre (s, d) suportadas em C a c sd ≤ r sd para todo (s, d) ∈ R. Seja C o conjunto de todas as possíveis congurações de roteamento independentes. Seja w c a variável que indica quantas vezes uma dada conguração de roteamento independente é usada, sendo a cada ocorrência associado um comprimento de onda diferente. O modelo, denotado por IRC, pode ser expresso como:(IRC) max Z IRC (w) = ∑

Figura 4 . 6 :

 46 Figura 4.6: Exemplo de Instância[START_REF] Jaumard | On column generation formulations for the RWA problem[END_REF] 

Figura 4 . 7 :

 47 Figura 4.7: Conjunto Convexo para o problema MAX-IS

  Apresentamos duas variações que chamamos de RWA1 e RWA2. As duas propostas apresentaram um desempenho em termos de tempo de computação superior (menor tempo) aos modelos que usamos para fazer as comparações.Depois apresentamos uma nova proposta em termos de geração de colunas, também, para a resolução do MAX-RWA. Na verdade, combinamos duas estratégias já apresentadas na literatura, MAX-IRC e MAX-IS, para a resolução dos problemas.Observamos que a estratégia MAX-IS ainda não tinha sido utilizada devido à limitação de se ter a necessidade de que todos os possíveis caminhos entre os pares origem e destino tenham sido gerados para que se possa ter garantia que a solução gerada é ótima. Para tentar resolver esta limitação desenvolvemos uma boa estratégia para a geração de caminhos que chamamos de Path-Gen. Mesmo com a estratégia de geração de caminhos vimos que as vezes o modelo MAX-IS não é capaz de encontrar a solução ótima para o problema original. Sendo assim, surgiu a ideia de combinar os modelos MAX-IS e MAX-IRC, onde em cada iteração temos a opção de gerar variáveis utilizando um ou outro subproblema. No caso, a estratégia usada é de gerar variáveis com o subproblema do MAX-IRC somente quando o subproblema MAX-IS não é capaz de encontrar uma variável de custo reduzido maior que zero.A nova estratégia se mostrou capaz de resolver todas as instâncias testadas em um tempo inferior ao modelo MAX-IRC.Neste trabalho foi feita uma revisão sobre o problema de roteamento e alocação de comprimentos de onda em redes ópticas WDM. Foram apresentados alguns modelos matemáticos e as principais heurísticas e metaheurísticas propostas na literatura. Em relação aos métodos heurísticos para a minimização do número de comprimentos de onda foi vericado que o principal método de geração de soluções até então é o Best Fit Decreasing, proposto em 2007 por Skorin-Kapov [50]. Como método de renamento, primeiramente foi desenvolvido um algoritmo baseado na metaheurística VND e também um método híbrido usando a Busca Tabu apresentada por Noronha et al. [45], respectivamente VND-BFD e VND-BT. Estes métodos não apresentaram melhoras signicativas com relação aos métodos já apresentados na literatura. Desenvolvemos então uma nova abordagem, também através do VND, onde o foco é o rearranjo das requisições. Esta nova versão do VND é utilizada como busca local de um procedimento baseado na metaheurística Iterated Local Search e desenvolvemos uma perturbação baseada em um problema de atribuição que não afeta o valor da função objetivo. Desenvolvemos quatro variantes desta abordagem que variavam pela maneira de escolher um subgrafo para ser eliminado e na maneira de escolher as requisições para o problema de atribuição na fase de perturbação. Esta abordagem se mostrou muito eciente e competitiva em comparação com os métodos propostos na literatura, com destaque para a variante VND e -ILS 5p , na qual o subgrafo escolhido para eliminação é aquele que possui o maior número de arcos não utilizados e as requisições que utilizam arcos adjacentes à origem ou o destino da requisição que se deseja rearranjar possuem cinco vezes mais chances de serem escolhidas para o problema de atribuição na fase de perturbação. Com esta variante todos os limites superiores das instâncias ainda em aberto foram melhorados e o método foi capaz de resolver todas as instâncias realísticas. Conduzimos testes computacionais com o intuito de estudar cada uma das componentes do VND e -ILS 5p mostrando, assim, a importância de cada uma.Com relação aos métodos exatos, começamos apresentando dois modelos compactos propostos na literatura para a resolução do problema de roteamento e alocação de comprimentos de onda com o objetivo de maximizar o número de requisições atendidas. Propusemos, então, algumas simplicações sobre estes modelos e mostramos através de testes computacionais que as simplicações não prejudicam os limites encontrados pelos modelos e aceleram a resolução dos problemas. Além disso, apresentamos alguns modelos baseados em geração de colunas presentes na literatura, também para a resolução do RWA com o objetivo de maximizar o número de requisições atendidas. Para nalizar, apresentamos uma nova abordagem para a geração de colunas combinando os modelos já existentes. Nos experimentos computacionais conduzidos, a abordagem proposta é capaz de resolver todas as instâncias em um tempo menor do que o modelo mais eciente da literatura até então garantindo que a solução encontrada é ótima.

  

  

  

  

  

  

  

  

  

  

  1.1 Uma bra transmitindo três comprimentos de onda distintos -[START_REF] Huiban | O problema da reconguração nas redes WDM multibras[END_REF] . 2.1 Instância estática do RWA . . . . . . . . . . . . . . . . . . . . . . . . Exemplo de Instância (Rede Z) -[43] . . . . . . . . . . . . . . . . . . 3.10 Gráco para instância Att -Alvo 20 . . . . . . . . . . . . . . . . . . . 3.11 Gráco para instância Finland -Alvo 46 . . . . . . . . . . . . . . . . 3.12 Gráco para instância NSF.12 -Alvo 38 . . . . . . . . . . . . . . . . Gráco para instância y.5.100.2 -Alvo 73 . . . . . . . . . . . . . . . . 3.16 Gráco para instância y.4.80.1 -Alvo 72 . . . . . . . . . . . . . . . . 3.17 Gráco para instância y.4.100.1 -Alvo 89 . . . . . . . . . . . . . . . . 3.18 Gráco para instância z.10x10.60 -Alvo 86 . . . . . . . . . . . . . . . 3.19 Gráco para instância z.10x10.80 -Alvo 114 . . . . . . . . . . . . . . 4.1 NSFnet -[45] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Solução do modelo KS . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Solução do modelo JMT . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Solução dos modelos RWA1 e RWA2 . . . . . . . . . . . . . . . . . .

	Lista de Siglas
	BF Best Fit
	BFD Best Fit Decreasing
	DEMUX Demultiplexador
	EDP Edge Disjoint Path
	FDM Frequency-Division Multiplexing
	FF First Fit
	FFD First Fit Decreasing
	LD Laser Diode
	LED Light Emitting Diode
	MUX Multiplexador
	OXC Optical Crossconnect
	PCT Problema de Concentração de Tráfego
	PM Problema Mestre
	PMR Problema Mestre Restrito
	PTD Physical Topology Design
	RWA Routing and Wavelength Assignment
	SDM Space-Division Multiplexing
	TDM Time-Division Multiplexing
	TS-PCP Tabu Search-Partition Coloring Problem
	WDM Wavelength Division Multiplexing
	VTD Virtual Topology Design
	xvii

2.2 Representação da Solução . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Exemplos de topologias em árvores . . . . . . . . . . . . . . . . . . . 2.4 Exemplo de solução viável com 3 comprimentos de onda . . . . . . . 2.5 Pseudocódigo do algoritmo Greedy-EDP-RWA -Adaptado de [39] . . 2.6 Pseudocódigo do algoritmo OneStepCD -Adaptado de [45] . . . . . . 2.7 Pseudocódigo do algoritmo TS-PCP -Adaptado de [45] . . . . . . . . 2.8 Pseudocódigo do algoritmo BFD-RWA -Adaptado de [50] . . . . . . 3.1 Representação da Solução . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Algoritmo VND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Subgrafos sem os arcos já utilizados . . . . . . . . . . . . . . . . . . . 3.4 Seleção dos subgrafos para a primeira vizinhança . . . . . . . . . . . 3.5 Algoritmo Busca Tabu . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Vizinhanças . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Perturbação ILS por meio de um problema de atribuição . . . . . . . 3.8 Instância Finland . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 3.13 Gráco para instância y.4.20.4 -Alvo 19 . . . . . . . . . . . . . . . . 3.14 Gráco para instância y.5.80.2 -Alvo 59 . . . . . . . . . . . . . . . . xvi 3.15 4.5 Exemplo de conjuntos independentes [27] . . . . . . . . . . . . . . . . 4.6 Exemplo de Instância [27] . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Conjunto Convexo para o problema MAX-IS . . . . . . . . . . . . . .

  Imagine que todas as requisições sejam atendidas utilizando-se o caminho mínimo entre a origem e o destino da requisição. No me-

	lhor caso vamos precisar de ⌈ acomodar estas requisições, sendo assim, ⌈ ∑ r∈R l(CM r )/(2 × |E|)⌉ comprimentos de onda para ∑ r∈R l(CM r )/(2 × |E|)⌉ é um limite in-
	ferior para o RWA. Obviamente os dois limites inferiores podem apresentar valores
	diferentes, assim podemos considerar aquele que resultar o maior valor.

conjunto de arestas do corte, isto é, C é o subconjunto de arestas de E com uma extremidade em V 1 e outra em V 2 . Temos então |V 1 | × |V 2 | pares de vértices que demandam uma conexão através das arestas de C. O número mínimo de comprimentos de onda para um determinado conjunto C pode ser obtido por: LI C = ⌈ |V 1 |×|V 2 | |C| ⌉, onde ⌈x⌉ é igual ao menor inteiro maior ou igual a x. Vários conjuntos de arestas podem ser utilizadas para formar C obtendo-se valores diferentes para LI C . O conjunto que determinar o maior valor para LI C determina o limite inferior desta metodologia.

Sharafat e Ma'rouzi

[START_REF] Sharafat | The most congested cutset: deriving a tight lower bound for the chromatic number in the RWA problem[END_REF] 

apresentaram uma generalização do trabalho de Baroni e Bayvel

[START_REF] Baroni | Wavelength requirements in arbitrarily connected wavelength-routed optical networks[END_REF] 

calculando limites inferiores para grafos com matrizes de tráfego distintas e topologias arbitrárias. Skorin-Kapov

[START_REF] Skorin-Kapov | Routing and wavelength assignment in optical networks using bin packing based algorithms[END_REF]

, inspirada na metodologia apresentada por Ramaswami e Sivarajan

[START_REF] Ramaswami | Design of logical topologies for wavelengthrouted optical networks[END_REF] 

para problemas de denição de topologias virtuais, apresentou uma metodologia simples para obtenção de limites inferiores. Neste trabalho são considerados dois limites inferiores, sendo o primeiro calculado da seguinte maneira: para cada vértice, dividimos o número de requisições que devem ser estabelecidas a partir do vértice (grau lógico) pelo número de arestas que saem do vértice (grau físico), o maior valor entre todos os vértices é o primeiro limite inferior. Matematicamente falando temos max i∈V ⌈∆ l(i) /∆ f (i) ⌉. O outro limite inferior é obtido pelo somatório dos tamanhos (em número de arestas ou número de saltos) dos caminhos mínimos de todas as requisições dividido pelo dobro do número de arestas. Matematicamente temos, ⌈ ∑ r∈R l(CM r )/(2 × |E|)⌉.

  . A ideia é semelhante ao trabalho apresentado por Chlamtac et al.[START_REF] Chlamtac | Lightpath communications: An approach to high-bandwidth optical WAN's[END_REF] de alocar o mesmo comprimento de onda aos caminhos disjuntos, mas, aqui, os caminhos são gerados a cada iteração e a ordem de todas as requisições é

	estabelecida aleatoriamente. Além disso o caminho mínimo inserido em uma solução
	é limitado por max(diametro(G),	√	|E|), onde diametro(G) representa o diâmetro
	do grafo que é dado pelo tamanho do maior dos caminhos mínimos do grafo. Este
	limite foi proposto por Kleinberg [32] para a resolução do problema de maximizar
	o número de caminhos com arestas disjuntas em um grafo. O pseudocódigo deste
	algoritmo pode ser visto na Figura 2.5.
	também são apresentadas heurísticas para outras variações do problema, por exem-
	plo, com o número de comprimentos de onda limitado e com requisições chegando
	dinamicamente.		
	Manohar et al. [39] propuseram um algoritmo construtivo randomizado para o

desenvolveram uma heurística gulosa para a alocação dos comprimentos de onda. Neste trabalho os caminhos são determinados por algum algoritmo de caminho mínimo. Depois são ordenados em ordem decrescente de tamanho, então aloca-se cada comprimento de onda a todos os possíveis caminhos disjuntos. A ideia é que caminhos maiores são mais difíceis de serem roteados e portanto devem ser roteados primeiro. Neste trabalho RWA ao qual chamaram de Greedy-EDP-RWA. O algoritmo é utilizado como um algoritmo de multipartida, executado um número xo de iterações, retornando a me-lhor solução encontrada

  ); 2 S ← ⊘; {Conjunto que guarda a solução} 3 B ← ⊘; {Conjunto que guarda as cópias do grafo original DEFINIR} 4 para i = 1 até |R| faça

5 se caminho disjunto ≤ d em nenhuma cópia de G ∈ B então 6 Crie uma nova cópia G de G; 7 B ← B ∪ {G}; 8 m-se 9 Encontre a j-ésima cópia G j ∈ B onde a i-ésima requisição possui o menor caminho; 10 c ← o menor caminho para i no grafo G j ; 11 S ← S ∪ {(i, c, j)}; {Para cada requisição i guarda-se o caminho c e o índice j em que ela foi alocada} 12 Remova os arcos do caminho c da cópia G j ; 13 m-para 14 Retorne S;

  1 enquanto o VND-BT é capaz de encontrar um limite melhor para a instância y.3.80.5. ILS 5p com outros métodos da literatura. A Tabela 3.10 apresenta os resultados de quatro métodos, multistart-BFD, BFD-VND e , VND e -ILS 5p e EDP-VND e -ILS 5p , para as instâncias realísticas. O objetivo deste teste é mostrar que a variante VND e -ILS 5p é capaz de encontrar melhores soluções que o multistart-BFD. Na variante BFD-VND e eliminamos a fase de perturbação e assim podemos ver o seu impacto. Na variante EDP-VND e -ILS 5p utilizamos o EDP para a geração da solução inicial e assim podemos observar a robustez do método proposto. Para cada método executamos novamente cinco rodadas sobre cada instância, apresentando a melhor solução e o gap médio, com limite de tempo -ILS 5p é capaz de encontrar melhores desvios para 42 das 75 instâncias e que o EDP-VND e -ILS 5p é capaz de encontrar melhores desvios em 35 destas 42 instâncias. O uso do BFD como solução inicial, contudo, conduz a melhores soluções como podemos ver pelos resultados do VND e -ILS 5p em comparação com o EDP-VND e -ILS 5p . -ILS p VND r -ILS p VND e -ILS 5p VND r -ILS 5p -ILS p VND r -ILS p VND e -ILS 5p VND r -ILS 5p Instâncias λ min gap(%) λ min gap(%) λ min gap(%) λ min gap(%) LI -ILS p VND r -ILS p VND e -ILS 5p VND r -ILS 5p Instâncias λ min gap(%) λ min gap(%) λ min gap(%) λ min gap(%) LI Resultados VND-ILS -Conjunto Y5 Métodos VND e -ILS p VND r -ILS p VND e -ILS 5 p VND r -ILS 5 p Instâncias λ min gap(%) λ min gap(%) λ min gap(%) λ min gap(%) LI Podemos observar pela Tabela 3.15 que o VND e -ILS 5p apresenta um desempenho superior ao método GA-RWA. Para todas as instâncias em que o GA-RWA ainda não havia encontrado a solução ótima o VND e -ILS 5p consegue um limite superior melhor mesmo se olharmos somente as 5 primeiras execuções. A média do VND e -Tabela 3.10: Comparação com o multistart-BFD sobre as instâncias realísticas Multistart-BFD BFD-VND e VND e -ILS 5p EDP-VND e -ILS 5p Tabela 3.11: Comparação com o multistart-BFD sobre o conjunto Z Multistart-BFD BFD-VND e VND e -ILS 5p EDP-VND e -ILS 5p Tabela 3.12: Comparação com o multistart-BFD sobre o conjunto Y3 Multistart-BFD BFD-VND e VND e -ILS 5p EDP-VND e -ILS 5p Instâncias λ min gap(%) λ min gap(%) λ min gap(%) λ min Para as instâncias realísticas, Figuras 3.10, 3.11 e 3.12, podemos ver que o VND e -ILS 5p não apresenta diculdade em encontrar a solução alvo para nenhuma das instâncias, sendo as soluções das instâncias ATT e Finland encontradas em menos de 10 segundos e para a instância NSF.12 os piores casos não passam de 2 segundos. Tabela 3.14: Comparação com o multistart-BFD sobre o conjunto Y5 Multistart-BFD BFD-VND e VND e -ILS 5p EDP-VND e -ILS 5p Instâncias λ min gap(%) λ min gap(%) λ min gap(%) λ min

	Tabela 3.2: Resultados VND-BFD X VND-BT -Instâncias Realísticas Métodos VND-BFD VND-BT Instâncias λ min gap(%) λ min gap(%) LI ATT 23 18.0 23 18.0 ATT2 113 0.7 113 0.0 Brasil 48 0.0 48 0.0 EON 22 0.0 22 0.0 Finland 47 2.2 46 1.7 NSF.3 22 2.7 23 4.6 NSF.12 39 2.6 39 2.6 NSF2.12 35 0.0 35 0.0 Média 3.3 3.4 Tabela 3.3: Resultados VND-BFD X VND-BT -Instâncias Z Métodos VND-BFD VND-BT Instâncias λ min gap(%) λ min gap(%) LI z.10x10.20 30 14.07 31 14.81 z.8x13.20 35 6.06 35 6.06 z.6x17.20 46 4.55 46 4.55 z.5x20.20 54 1.48 54 1.48 z.4x25.20 68 3.03 68 3.03 z.10x10.40 56 9.80 56 11.37 z.8x13.40 66 4.76 66 4.76 z.6x17.40 86 2.38 86 2.38 z.5x20.40 103 1.98 103 1.98 z.4x25.40 129 2.38 129 2.38 z.10x10.60 84 9.09 84 9.09 z.8x13.60 100 4.17 100 4.17 z.6x17.60 131 2.34 131 2.50 z.5x20.60 157 1.95 157 1.95 z.4x25.60 196 2.08 196 2.08 z.10x10.80 111 7.77 111 7.77 z.8x13.80 133 3.10 133 3.10 z.6x17.80 174 2.11 174 2.22 z.5x20.80 207 1.27 208 1.46 z.4x25.80 260 1.17 260 1.17 z.10x10.100 136 8.80 136 8.80 z.8x13.100 170 1.19 170 1.19 z.6x17.100 219 1.39 219 1.39 z.5x20.100 254 1.68 254 1.92 z.4x25.100 318 1.92 318 1.99 Média 4.02 4.14 3.4.2 Resultados para o VND-ILS Nesta seção apresentamos os resultados das variações para o VND-ILS. Foram tes-tadas 4 versões do VND-ILS, combinando as variantes VND e e VND r com as vari-antes ILS p e ILS 5p . Relembrando que no VND e o subconjunto a ser elimanado é o que apresenta o maior número de arcos sem utilização, no VND r é o que apresenta o menor número de requisições; no ILS p todas as requisições têm as mesmas chances de fazer parte do problema de atribuição, e no ILS 5p as requisições roteadas por os métodos que utilizam o ILS 5p capazes de encontrar a solução ótima para outras As versões com o ILS apresentam desvios menores que o multistart-BFD, em par-Tabela 3.6: Resultados VND-ILS -Conjunto Z Tabela 3.7: Resultados VND-ILS -Conjunto Y3 variação. Das 30 instâncias o método proposto consegue melhorar o limite superior Z nas quais os algoritmos apresentaram os maiores desvios. No caso as instâncias não foi resolvida todas as vezes em menos de 5 minutos. Contudo, vemos pela Figura arcos adjacentes a s Tabela 3.4: Resultados VND-BFD X VND-BT -Conjunto Y Métodos VND-BFD VND-BT Instâncias λ min gap(%) λ min gap(%) LI y.4.20.4 20 5.26 20 7.37 19 y.3.40.5 60 13.21 60 13.21 53 y.3.60.5 86 12.73 87 12.99 77 y.4.60.5 57 17.55 57 17.55 49 y.5.60.1 37 12.12 37 12.12 33 y.3.80.1 122 15.47 122 15.66 106 y.3.80.5 114 9.62 113 9.42 104 y.4.80.1 72 53.19 72 53.19 47 y.4.80.5 74 14.77 74 14.46 65 y.5.80.1 48 13.49 48 13.02 43 y.5.80.2 60 2.37 60 2.37 59 y.4.100.1 88 16.84 89 17.11 76 y.5.100.1 59 7.27 59 7.27 55 y.5.100.2 76 4.11 76 4.11 73 Média 14.14 14.28 Nas Tabelas 3.7, 3.8 e 3.9 novamente podemos ver que o ILS 5p causa um im-pacto positivo nas soluções e o VND e -ILS 5p apresenta limites melhores em quatro instâncias, y.3.20.5, y.3.60.5, y.3.100.4 e y.4.100.1. Todas as variações são capazes de encontrar a solução ótima para quarenta e cinco instâncias deste conjunto, sendo As Tabelas 3.12 a 3.14 apresentam os resultados para as instâncias do conjunto Y. Comparando os quatro métodos eles seguem a tendência das tabelas anteriores. Tabela 3.5: Resultados VND-ILS -Instâncias Realísticas Métodos VND e Instâncias λ min gap(%) λ min gap(%) λ min gap(%) λ min gap(%) LI Atlanta20 1256 0.0 1256 0.0 1256 0.0 1256 0.0 ATT 20 0.0 20 0.0 20 0.0 20 0.0 ATT2 113 0.0 113 0.0 113 0.0 113 0.0 Brasil 48 0.0 48 0.0 48 0.0 48 0.0 Cost266 446 0.0 446 0.0 446 0.0 446 0.0 Dfn-bwin 73 0.0 73 0.0 73 0.0 73 0.0 Dfn-gwin 316 0.0 316 0.0 316 0.0 316 0.0 EON 22 0.0 22 0.0 22 0.0 22 0.0 Finland 46 0.0 46 0.0 46 0.0 46 0.0 France 946 0.0 946 0.0 946 0.0 946 0.0 Germany50 147 0.0 147 0.0 147 0.0 147 0.0 Giul 379 0.0 379 0.0 379 0.0 379 0.0 Janos-us 207 0.0 207 0.0 207 0.0 207 0.0 Nobel-eu 214 0.0 214 0.0 214 0.0 214 0.0 Nobel-germany 78 0.0 78 0.0 78 0.0 78 0.0 Nobel-us 39 0.0 39 0.0 39 0.0 39 0.0 Norway 274 0.0 274 0.0 274 0.0 274 0.0 NSF.1 22 0.0 22 0.0 22 0.0 22 0.0 NSF.3 22 0.0 22 0.0 22 0.0 22 0.0 NSF.12 38 0.0 38 0.0 38 0.0 38 0.0 NSF.48 41 0.0 41 0.0 41 0.0 41 0.0 NSF2.1 21 0.0 21 0.0 21 0.0 21 0.0 NSF2.3 21 0.0 21 0.0 21 0.0 21 0.0 NSF2.12 35 0.0 35 0.0 35 0.0 35 0.0 NSF2.48 39 0.0 39 0.0 39 0.0 39 0.0 Sun 59 0.0 59 0.0 59 0.0 59 0.0 Média 0.0 0.0 0.0 0.0 Métodos VND e z.10x10.20 29 7.41 29 7.41 29 7.41 29 7.41 z.8x13.20 34 3.03 34 3.03 34 3.03 34 3.03 z.6x17.20 45 2.27 44 1.82 44 1.36 44 0.91 z.5x20.20 54 0.00 54 0.00 54 0.00 54 0.00 z.4x25.20 66 0.91 66 0.61 66 0.00 66 0.61 z.10x10.40 56 9.80 56 9.80 55 8.63 55 8.24 z.8x13.40 65 3.17 65 3.17 64 2.54 64 2.22 z.6x17.40 85 1.43 85 1.19 85 1.19 85 1.19 z.5x20.40 102 0.99 101 0.79 101 0.59 101 0.40 z.4x25.40 127 0.95 127 0.79 127 0.79 127 0.79 z.10x10.60 85 10.39 85 10.39 84 9.09 84 9.35 z.8x13.60 99 3.13 98 2.92 98 2.08 98 2.08 z.6x17.60 129 0.78 129 0.94 129 0.78 129 0.78 z.5x20.60 155 0.65 155 0.65 154 0.26 154 0.39 z.4x25.60 193 0.62 193 0.52 193 0.52 193 0.52 z.10x10.80 113 9.90 113 9.90 112 9.51 112 9.13 z.8x13.80 131 1.55 131 1.55 130 1.09 130 1.24 z.6x17.80 172 0.58 172 0.58 171 0.47 172 0.58 z.5x20.80 206 0.49 206 0.49 206 0.49 206 0.49 z.4x25.80 259 0.78 258 0.62 258 0.47 258 0.54 z.10x10.100 140 12.00 140 12.00 139 11.52 139 11.36 z.8x13.100 174 3.57 174 3.57 173 3.21 173 3.33 z.6x17.100 220 1.94 220 1.94 220 1.85 220 1.85 z.5x20.100 253 1.52 253 1.52 253 1.52 253 1.28 z.4x25.100 317 1.73 317 1.73 317 1.60 317 1.60 Média 3.18 3.12 2.80 2.77 Métodos VND e y.3.20.1 30 11.11 30 11.11 29 8.89 8.89 27 y.3.20.2 33 0.00 33 0.00 33 0.00 0.00 33 y.3.20.3 29 0.00 29 0.00 29 0.00 0.00 29 y.3.20.4 28 10.00 28 8.46 28 8.46 9.23 26 y.3.20.5 29 3.57 29 3.57 28 2.86 3.57 28 y.3.40.1 58 9.43 57 9.06 57 7.55 7.55 53 y.3.40.2 59 0.00 59 0.00 59 0.00 0.00 59 y.3.40.3 61 0.00 61 0.00 61 0.00 0.00 61 y.3.40.4 54 8.80 54 9.20 54 8.00 8.40 50 y.3.40.5 57 7.55 57 7.55 56 6.79 6.42 53 y.3.60.1 87 8.15 87 8.40 87 7.41 7.41 81 y.3.60.2 89 0.00 89 0.00 89 0.00 0.00 89 y.3.60.3 91 0.00 91 0.00 91 0.00 0.00 91 y.3.60.4 80 3.59 81 3.85 80 2.82 2.56 78 y.3.60.5 83 8.05 83 8.05 82 7.53 7.79 77 y.3.80.1 116 9.81 116 9.43 115 9.25 9.06 106 y.3.80.2 117 0.00 117 0.00 117 0.00 0.00 117 y.3.80.3 118 0.00 118 0.00 118 0.00 0.00 118 y.3.80.4 107 1.90 107 1.90 106 1.14 1.33 105 y.3.80.5 110 5.77 110 5.96 109 4.81 5.00 104 y.3.100.1 144 10.08 144 10.08 143 9.31 9.16 131 y.3.100.2 146 0.00 146 0.00 146 0.00 0.00 146 y.3.100.3 146 0.00 146 0.00 146 0.00 0.00 146 y.3.100.4 133 1.83 133 1.83 132 1.22 1.53 131 y.3.100.5 137 6.51 137 6.51 136 5.58 5.74 129 Média 4.25 4.20 3.66 3.75 3.4.3 Comparações com a literatura Nesta seção serão apresentadas algumas comparações com a literatura. As instâncias utilizadas nestes testes são um subconjunto das instâncias apresentadas na Seção 3.4.2. Serão apresentados somente os resultados de algumas instâncias que apresen-taram maior diculdade de serem resolvidas segundo estudos realizados por Noronha et al. [44]. Os testes foram realizados da seguinte maneira: Cada instância foi re-solvida pelo VND y.5.20.1 13 0.00 13 0.00 13 0.00 0.00 13 y.5.20.2 17 0.00 17 0.00 17 0.00 0.00 17 y.5.20.3 13 8.33 12 6.67 12 5.00 5.00 12 y.5.20.4 17 0.00 17 0.00 17 0.00 0.00 17 y.5.20.5 15 0.00 15 0.00 15 0.00 0.00 15 y.5.40.1 24 1.67 24 1.67 24 0.00 0.00 24 y.5.40.2 31 0.00 31 0.00 31 0.00 0.00 31 y.5.40.3 23 4.55 23 4.55 23 4.55 4.55 22 y.5.40.4 33 0.00 33 0.00 33 0.00 0.00 33 y.5.40.5 28 0.00 28 0.00 28 0.00 0.00 28 y.5.60.1 36 9.09 35 8.48 35 6.67 7.27 33 y.5.60.2 45 0.00 45 0.00 45 0.00 0.00 45 y.5.60.3 34 0.00 34 0.00 34 0.00 0.00 34 y.5.60.4 48 0.00 48 0.00 48 0.00 0.00 48 y.5.60.5 40 0.00 40 0.00 40 0.00 0.00 40 y.5.80.1 46 8.37 46 7.91 46 6.98 6.98 43 y.5.80.2 59 0.34 59 0.00 59 0.00 0.00 59 y.5.80.3 44 3.26 44 3.26 44 2.33 2.33 43 y.5.80.4 63 0.00 63 0.00 63 0.00 0.00 63 y.5.80.5 53 0.00 53 0.00 53 0.00 0.00 53 y.5.100.1 57 4.36 57 4.00 57 3.64 3.64 55 y.5.100.2 73 1.10 73 1.10 73 0.00 0.00 73 y.5.100.3 55 3.77 55 3.77 54 3.40 3.40 53 y.5.100.4 77 0.00 77 0.00 77 0.00 0.00 77 y.5.100.5 66 0.00 66 0.00 66 0.00 0.00 66 Média 1.79 1.66 1.30 1.33 a melhor solução foi encontrada ( tbest ). ILS 5p é exatamente igual para 5 ou 30 execuções e o maior desvio padrão observado é igual a 0.5 que mostra que as soluções encontradas pelo método apresentam pouca Instâncias λ min gap(%) λ min gap(%) λ min gap(%) λ min gap(%) LI Atlanta20 1342 6.91 1284 2.37 1256 0.00 1256 0.00 ATT 25 25.00 24 20.00 20 0.00 20 0.00 ATT2 113 0.71 113 0.71 113 0.00 113 0.00 Brasil 48 0.00 48 0.00 48 0.00 48 0.00 Cost266 * 446 0.00 446 0.00 446 0.00 446 0.00 Dfn-bwin * 73 0.00 73 0.00 73 0.00 73 0.00 Dfn-gwin * 316 0.00 316 0.00 316 0.00 316 0.00 EON 22 0.00 22 0.00 22 0.00 22 0.00 Finland 47 2.17 47 2.17 46 0.00 46 0.00 France * 946 0.00 946 0.00 946 0.00 946 0.00 Germany50 169 15.37 169 15.37 147 0.00 147 0.00 Giul 402 6.07 401 5.91 379 0.00 379 0.00 Janos-us * 215 4.15 215 4.15 207 0.00 207 0.00 Nobel-eu 304 0.00 304 0.00 304 0.00 304 0.00 Nobel-germany 89 4.94 89 4.71 85 0.00 85 0.00 Norway 543 0.00 543 0.00 543 0.00 543 0.00 NSF.1 23 4.55 22 0.00 22 0.00 22 0.00 NSF.3 22 3.64 22 2.73 22 0.00 22 0.00 NSF.12 39 2.63 39 2.63 38 0.00 38 0.00 NSF.48 41 0.49 41 0.00 41 0.00 41 0.00 NSF2.1 21 0.00 21 0.00 21 0.00 21 0.00 NSF2.3 21 0.00 21 0.00 21 0.00 21 0.00 NSF2.12 35 1.71 35 0.00 35 0.00 35 0.00 NSF2.48 39 0.00 39 0.00 39 0.00 39 0.00 Sun 61 3.39 60 1.69 59 0.00 59 0.00 Média 3.27 2.50 0.00 0.00 solução ótima é encontrada em todas as execuções. Para nalizar esta seção de testes o VND e -ILS 5p foi executado 200 vezes para al-gumas instâncias, também variando-se a semente utilizada pelo gerador de números pseudo-aleatórios. O algoritmo foi programado para terminar sua execução quando encontrasse uma solução com um número de comprimentos de onda para cada ins-tância dado a priori. Nas Figuras 3.10 à 3.19, cada ponto da curva associada ao gap(%) λ min gap(%) λ min gap(%) λ min gap(%) LI Z.10x10.20 31 17.04 31 17.04 29 7.41 11.11 27 Z.8x13.20 35 8.48 35 8.48 34 3.03 3.03 33 Z.6x17.20 46 4.55 46 4.55 44 1.36 2.27 44 Z.5x20.20 55 1.85 55 1.85 54 0.00 0.00 54 Z.4x25.20 68 3.03 68 3.03 66 0.00 2.12 66 Z.10x10.40 59 15.69 58 14.51 55 8.63 12.16 51 Z.8x13.40 67 6.35 67 6.35 64 2.54 4.76 63 Z.6x17.40 87 4.29 87 3.57 85 1.19 2.38 84 Z.5x20.40 104 2.97 104 2.97 101 0.59 2.18 101 Z.4x25.40 129 2.70 129 2.38 127 0.79 2.38 126 Z.10x10.60 88 14.29 87 14.03 84 9.09 12.99 77 Z.8x13.60 101 5.63 101 5.21 98 2.08 4.38 96 Z.6x17.60 133 3.91 133 3.91 129 0.78 2.66 128 Z.5x20.60 158 2.60 158 2.60 154 0.26 2.60 154 Z.4x25.60 195 2.08 195 1.98 193 0.52 2.71 192 Z.10x10.80 116 12.62 116 12.62 112 9.51 13.98 103 Z.8x13.80 134 4.50 134 4.50 130 1.09 3.88 129 Z.6x17.80 176 3.39 176 3.27 171 0.47 2.57 171 Z.5x20.80 209 1.95 209 1.95 206 0.49 2.63 205 Z.4x25.80 261 1.56 261 1.56 258 0.47 2.72 257 Z.10x10.100 142 13.60 142 13.60 139 11.52 17.44 125 Z.8x13.100 175 4.17 175 4.17 173 3.21 6.31 168 Z.6x17.100 222 3.06 222 3.06 220 1.85 4.17 216 Z.5x20.100 256 2.56 256 2.48 253 1.52 4.16 250 Z.4x25.100 319 2.24 318 2.18 317 1.60 4.42 312 Média 5.80 5.67 2.80 5.20 tempo para alcançar uma solução tão boa quanto o valor alvo. Utilizamos neste último teste três instâncias realísticas que usamos para com-parar com o GA-RWA, ATT, Finland e NSF.12, todas tendo como alvo a solução ótima de cada uma das instâncias. Ainda utilizamos as instâncias y.4.20.4, y.5.80.2 e y.5.100.2 também tendo como alvo a solução ótima de cada uma das instâncias. Para nalizar utilizamos também duas instâncias do conjunto Y e duas do conjunto gap(%) LI y.3.20.1 33 22.22 33 22.22 29 8.89 30 11.11 y.3.20.2 33 0.00 33 0.00 33 0.00 33 0.00 y.3.20.3 31 6.90 31 6.90 29 0.00 29 0.00 y.3.20.4 31 19.23 31 19.23 28 8.46 29 11.54 y.3.20.5 31 10.71 31 10.71 28 2.86 29 3.57 y.3.40.1 62 18.49 62 18.11 57 7.55 59 11.32 y.3.40.2 59 0.00 59 0.00 59 0.00 59 0.00 y.3.40.3 61 0.00 61 0.00 61 0.00 61 0.00 y.3.40.4 58 16.00 58 16.00 54 8.00 56 12.00 y.3.40.5 60 13.21 60 13.21 56 6.79 58 9.43 y.3.60.1 93 14.81 93 14.81 87 7.41 90 12.35 y.3.60.2 89 0.00 89 0.00 89 0.00 89 0.00 y.3.60.3 91 0.00 91 0.00 91 0.00 91 0.00 y.3.60.4 85 9.23 85 8.97 80 2.82 83 6.41 y.3.60.5 86 12.73 86 12.73 82 7.53 85 11.69 y.3.80.1 123 16.04 123 16.04 115 9.25 122 15.09 y.3.80.2 117 0.00 117 0.00 117 0.00 117 0.00 y.3.80.3 118 0.17 118 0.17 118 0.00 118 0.00 y.3.80.4 112 6.67 111 6.48 106 1.14 110 5.71 y.3.80.5 114 9.62 114 9.62 109 4.81 114 9.62 y.3.100.1 151 15.27 151 15.57 143 9.31 152 16.03 y.3.100.2 146 0.00 146 0.00 146 0.00 146 0.00 y.3.100.3 146 0.00 146 0.00 146 0.00 146 0.00 y.3.100.4 138 5.80 138 5.80 132 1.22 139 6.87 y.3.100.5 141 9.30 141 9.30 136 5.58 143 10.85 Média 8.26 8.23 3.66 6.14 Para as instâncias y.4.20.4, y.5.80.2 e y.5.100.2, que também tiveram como alvo a solução ótima, podemos ver pelas Figuras 3.13 a 3.15 que apenas a última instância gap(%) LI y.5.20.1 14 7.69 14 7.69 13 0.00 0.00 13 y.5.20.2 17 0.00 17 0.00 17 0.00 0.00 17 y.5.20.3 13 8.33 13 8.33 12 5.00 8.33 12 y.5.20.4 17 0.00 17 0.00 17 0.00 0.00 17 y.5.20.5 15 0.00 15 0.00 15 0.00 0.00 15 y.5.40.1 25 4.17 25 4.17 24 0.00 0.83 24 y.5.40.2 31 1.29 31 1.29 31 0.00 0.00 31 y.5.40.3 24 9.09 24 9.09 23 4.55 6.36 22 y.5.40.4 33 0.00 33 0.00 33 0.00 0.00 33 y.5.40.5 28 0.00 28 0.00 28 0.00 0.00 28 y.5.60.1 36 11.52 36 11.52 35 6.67 9.09 33 y.5.60.2 45 1.33 45 0.89 45 0.00 0.00 45 y.5.60.3 35 2.94 35 2.94 34 0.00 0.00 34 y.5.60.4 48 0.00 48 0.00 48 0.00 0.00 48 y.5.60.5 40 0.00 40 0.00 40 0.00 0.00 40 y.5.80.1 47 11.16 47 11.16 46 6.98 9.30 43 y.5.80.2 60 1.69 60 1.69 59 0.00 1.02 59 y.5.80.3 45 4.65 45 4.65 44 2.33 5.12 43 y.5.80.4 63 0.00 63 0.00 63 0.00 0.00 63 y.5.80.5 53 0.00 53 0.00 53 0.00 0.00 53 y.5.100.1 59 7.27 59 7.27 57 3.64 5.82 55 y.5.100.2 75 2.74 75 2.74 73 0.00 1.37 73 y.5.100.3 56 5.66 56 5.66 54 3.40 5.66 53 y.5.100.4 77 0.00 77 0.00 77 0.00 0.00 77 y.5.100.5 66 0.00 66 0.00 66 0.00 0.00 66 Média 3.18 3.16 1.30 2.12 algoritmo representa um par (t Instâncias λ min cos descreve uma aproximação da distribuição de probabilidade da variável aleatória e 114. 3.4.4 Análise de componentes VND e -ILS 5p
	três instâncias.

r e d r têm cinco vezes mais chances. As soluções iniciais de todas as variantes são geradas pelo BFD. A Tabela 3.5 apresenta os resultados das variações do VND-ILS para as instâncias realísticas. Todas as variações foram capazes de encontrar a solução ótima para todas as instâncias em todas as execuções. A Tabela 3.6 apresenta os resultados das variações do VND-ILS para as instâncias do conjunto Z. Podemos observar que as variações VND e e VND r não causam tanto impacto nas soluções, mas o ILS 5p apresenta resultados melhores que o ILS p . A diferença na média das soluções do VND e -ILS 5p e VND r -ILS 5p é mínima, 2.80 e 2.77, no entanto o VND e -ILS 5p é capaz de encontrar um limite superior melhor, no caso, para a instância z.6x17.80. Para todas as outras instâncias o limite superior foi sempre o mesmo. O VND e -ILS 5p é capaz de encontrar a solução ótima para seis instâncias deste conjunto. A partir dos resultados expostos serão feitas comparações da variante VND e -de 5 minutos. Como observamos anteriormente, as instâncias realísticas são mais fáceis de resolver do que as instâncias dos conjuntos Y e Z, contudo, mesmo para aquelas instâncias os métodos multistart-BFD e BFD-VND e não foram capazes de encontrar as soluções ótimas em todos os casos, enquanto o VND e -ILS 5p e EDP-VND e -ILS 5p são capazes. Podemos observar que o BFD-VND e é capaz de melhorar os resultados do multistart-BFD reduzindo a média geral de 3.27% para 2.50%, mas ainda apresenta alguns desvios bem grandes como 20% e 15.37%. No entanto, quando o ILS 5p é combinado ao VND e , todas as soluções ótimas são encontradas, independentemente da solução inicial. A Tabela 3.11 apresenta os resultados dos quatro métodos para o conjunto Z. Como podemos observar o multistart-BFD não foi capaz de encontrar nenhum dos limites inferiores e que o VND e -ILS 5p foi capaz de obter desvios melhores em todas as instâncias deste conjunto. Além disso, o VND e -ILS 5p foi capaz de encontrar a solução ótima para 6 instâncias. O uso do VND e o ILS é robusto, mesmo partindo de soluções iniciais diferentes como podemos ver pelo EDP-VND e -ILS 5p que encontra melhores desvios em relação ao multistart-BFD para 14 instâncias. ticular para instâncias em que o multistart-BFD não é capaz de encontrar a solução ótima. Podemos observar que o VND e e -ILS 5p 5 vezes partindo-se de sementes aleatórias diferentes. O tempo máximo para cada método foi de 5 minutos. Para ns de vericar o desvio padrão da função objetivo, cada instância foi resolvida mais vezes. O algoritmo foi implementado na linguagem C++ usando o compilador Borland Tabela 3.9: conhecido em 26 e obtem os mesmos limites nas outras 4 instâncias. Além disso o

VND e -ILS 5p encontra a solução ótima para 11 instâncias sendo que em 9 destas a i , p i ), para cada execução de i = 1, . . . , 200, onde t i é o tempo da i-ésima execução mais rápida deste algoritmo e p i = (i -0.5)/200.

De acordo com a metodologia descrita em

[START_REF] Aiex | Probability distribution of solution time in GRASP: An experimental investigation[END_REF] 

e

[START_REF] Aiex | TTT plots: a pearl program to create time-to-target plots[END_REF] 

(time-to-target (TTT) plots) e utilizada em vários trabalhos, veja por exemplo

[START_REF] Festa | Randomized heuristics for the MAX-CUT problem[END_REF][START_REF] Resende | A GRASP with pathrelinking for private virtual circuit routing[END_REF][START_REF] Noronha | Routing and wavelength assignment by partition colouring[END_REF][START_REF] Noronha | A biased random-key genetic algorithm for routing and wavelength assignment[END_REF]

, cada um destes grá-y.4.80.1, y.4.100.1, z.10x10.60 e z.10x10.80, com alvos iguais a uma unidade a menos da melhor solução encontrada pelo algoritmo GA-RWA, respectivamente, 72, 89, 86 3.15 que mais de 90% das rodadas a solução ótima foi encontrada antes deste tempo.

A instância y.4.20.4 é sempre resolvida com menos de 1 minuto como podemos ver

  Tabela 3.15: Resultados GA-RWA × VND e -ILS 5p Φ 1 já é possível obter uma média geral melhor que os resultados dos métodos apre- sentados na literatura até então. A vizinhança Φ 2 quando utilizada sozinha é a que apresenta os piores resultados. É interessante observar que a vizinhança Φ 3 apesar de não ter efeito algum se utilizada isoladamente mostra-se indispensável ao método como podemos ver pelos resultados das combinações Φ 1 + Φ 3 e Φ 2 + Φ 3 que apresentam resultados próximos ao VND e -ILS 5p .

	Métodos	GA-RWA (5) VND e -ILS 5p	(30) VND e -ILS 5p
	Instâncias λ min gap(%) λ min	gap(%) λ min gap(%) σ tbest LI
	ATT	24	20.0 20	0.0 20	0.0 0.0	1.9
	ATT2	113	0.0 113	0.0 113	0.0 0.0	4.3
	Finland	46	0.4 46	0.0 46	0.0 0.0	1.6
	NSF.3	22	0.9 22	0.0 22	0.0 0.0	0.1
	NSF.12	39	2.6 38	0.0 38	0.0 0.0	0.3
	NSF2.12	35	0.6 35	0.0 35	0.0 0.0	0.1
	z.10x10.20 31	15.6 29	7.4 29	7.4 0.0 75.1
	z.6x17.40	87	4.0 85	1.2 85	1.2 0.0 54.9
	z.10x10.60 87	13.2 84	9.1 84	9.1 0.0 202.8
	z.4x25.60 195	2.0 193	0.5 193	0.5 0.0 152.8
	z.10x10.80 115	12.4 112	8.7 112	8.7 0.0 238.1
	z.8x13.80 134	3.9 130	0.8 130	1.0 0.4 209.8
	z.6x17.80 176	3.0 171	0.2 171	0.3 0.5 190.8
	z.5x20.80 209	2.0 206	0.5 205	0.4 0.4 151.0
	z.4x25.80 260	1.3 258	0.5 258	0.4 0.3 184.2
	z.5x20.100 257	2.8 253	1.3 253	1.3 0.3 227.7
	y.4.20.4	20	6.3 19	0.0 19	0.0 0.0 24.0
	y.3.40.5	59	12.8 56	6.0 56	6.2 0.5 160.0
	y.3.60.5	86	12.5 82	6.8 82	6.7 0.4 215.7
	y.4.60.5	58	18.4 55	12.2 55	12.2 0.0 132.5
	y.5.60.1	36	9.7 35	6.7 35	6.6 0.4 140.2
	y.3.80.1	122	15.5 115	8.5 114	8.4 0.3 237.9
	y.3.80.5	113	8.8 109	4.8 108	4.8 0.3 203.0
	y.4.80.1	73	55.3 70	48.9 70	48.9 0.0 152.6
	y.4.80.5	75	16.0 72	10.8 72	10.8 0.0 204.7
	y.5.80.1	47	11.2 46	7.0 46	7.2 0.3 124.5
	y.5.80.2	60	1.7 59	0.0 59	0.0 0.0 51.2
	y.4.100.1	90	18.4 86	13.9 86	13.4 0.4 242.3
	y.5.100.1	58	5.5 57	3.6 57	3.7 0.2 184.4
	y.5.100.2	74	1.6 73	0.0 73	0.0 0.0 100.6
	Média		9.3	5.3		5.3
	vizinhança apenas trocas são aceitas. Os testes foram rodados como anteriormente,
	ou seja, cada instância foi resolvida 5 vezes por cada variação do método tendo como
	limite 5 minutos para cada execução. A fase de perturbação foi utilizada em todos
	os testes.					

A Tabela 3.16 apresenta os resultados da análise da dependência de cada vizinhança. Para cada variação apresentamos a melhor solução obtida e o desvio médio com relação ao limite inferior. Vemos que quando utilizamos somente a vizinhança

  Φ 3 Instâncias λ min gap(%) λ min gap(%) λ min gap(%) λ min gap(%) λ min gap(%) LI Tabela 3.17: Porcentagem de tempo e efetividade de cada etapa Instâncias t Φ 1 t Φ 2 t Φ 3 t p e Φ 1 e Φ 2 e Φ 3

							e p
		ATT		1.0 2.8 27.1 65.8 8.0 5.8 1.2 93.6
		ATT2	0.8 0.1 5.3 66.9 27.5 24.3 11.2 100.0
		Finland	0.8 1.7 17.7 75.6 8.7 9.4 3.8 100.0
		NSF.3	5.5 2.6 24.6 61.9 5.4 2.9 1.7 100.0
		NSF.12	1.4 0.1 8.5 87.1 6.4 3.6 1.7 100.0
		NSF2.12 3.1 3.1 12.0 75.8 19.5 10.7 5.3 100.0
		z.10x10.20 0.1 1.9 14.6 83.2 0.9 1.4 0.6	9.7
		z.6x17.40 0.1 2.1 22.4 74.9 1.2 3.5 0.5 97.1
	ATT	20 z.10x10.60 0.1 2.1 22.6 74.9 2.6 4.5 1.5 48.3 0.0 26 33.3 20 0.0 20 0.0 20	0.0
	ATT2	113 z.4x25.60 0.2 4.9 6.1 87.3 7.1 20.9 0.8 100.0 0.0 115 2.0 113 0.0 113 0.0 113	0.0
	Finland	46 z.10x10.80 0.1 2.2 23.2 73.9 3.1 4.5 1.4 66.4 0.0 48 5.2 46 0.0 46 0.0 46	0.0
	NSF.3	22 z.8x13.80 0.1 2.9 24.3 71.7 3.4 7.0 1.8 96.7 0.0 22 0.0 22 0.0 22 0.0 22	0.0
	NSF.12	38 z.6x17.80 0.2 4.3 11.6 82.1 6.8 15.1 1.7 100.0 0.0 38 0.0 38 0.0 38 0.0 38	0.0
	NSF2.12	35 z.5x20.80 0.2 5.3 7.4 84.8 8.7 21.6 1.3 100.0 0.0 35 0.0 35 0.0 35 0.0 35	0.0
	Z.10x10.20 30 z.4x25.80 0.2 4.0 4.5 88.7 9.5 27.9 0.8 100.0 14.1 32 20.7 30 11.1 29 7.4 29	7.4
	Z.6x17.40	87 z.5x20.100 0.2 5.8 6.0 84.6 9.2 24.7 1.3 100.0 3.6 88 5.5 85 2.1 86 2.4 85	1.2
	Z.10x10.60 88 y.4.20.4 14.3 89 0.1 1.1 31.1 67.0 3.2 2.3 1.6 11.3 15.8 86 12.7 85 10.4 85	10.4
	Z.4x25.60 195 y.3.40.5 2.2 196 0.1 1.3 32.2 66.0 1.6 1.6 0.7 52.0 3.1 193 1.0 195 1.7 193	0.9
	Z.10x10.80 115 y.3.60.5 12.2 116 0.1 1.5 34.7 62.7 2.6 3.3 1.4 73.8 13.6 115 11.8 114 10.7 113	9.7
	Z.8x13.80 134 y.4.60.5 3.9 135 0.1 2.1 34.6 62.7 3.1 3.5 2.2 28.7 5.0 132 2.9 131 1.9 131	1.6
	Z.6x17.80 175 y.5.60.1 2.7 177 0.1 0.8 37.3 61.4 2.3 1.8 0.9 14.2 4.0 173 1.3 173 1.2 172	0.7
	Z.5x20.80 209 y.3.80.1 2.1 210 0.1 2.0 27.4 69.1 5.3 6.8 2.9 93.0 2.8 206 0.9 207 1.4 206	0.6
	Z.4x25.80 260 y.3.80.5 1.5 262 0.1 1.8 29.0 67.7 3.9 4.4 1.7 86.1 2.2 259 0.8 260 1.3 259	0.8
	Z.5x20.100 256 y.4.80.1 2.5 257 0.1 2.0 31.5 65.7 3.7 4.4 2.8 36.3 3.0 254 1.9 255 2.3 254	1.7
	y.4.20.4	19 y.4.80.5 0.0 21 0.1 1.7 32.2 65.2 3.6 4.1 2.8 38.5 11.6 19 4.2 19 0.0 19	0.0
	y.3.40.5	58 y.5.80.1 10.9 60 0.1 1.3 36.1 61.9 3.14.7 58	9.4 57	7.5 57	7.5
	y.3.60.5	85	11.4 87	13.5 84	10.1 83	8.3 83	7.8
	y.4.60.5	58	18.4 59	21.2 58	18.4 55	13.5 55	12.2
	y.5.60.1	36	10.9 37	14.5 36	10.3 35	6.7 35	8.5
	y.3.80.1	121	14.5 123	17.2 119	12.8 116	10.0 116	9.6
	y.3.80.5	113	8.7 114	10.0 111	7.5 110	5.8 109	5.4
	y.4.80.1	73	55.7 74	58.3 73	55.3 70	49.4 70	49.4
	y.4.80.5	75	15.7 76	17.8 75	15.4 73	12.3 72	11.7
	y.5.80.1	47	11.2 49	14.0 47	11.2 46	7.0 46	7.9
	y.5.80.2	59	1.4 60	2.7 59	1.0 59	0.0 59	0.0
	y.4.100.1	90	18.9 91	20.3 90	18.7 87	14.5 87	14.5
	y.5.100.1	58	5.5 59	8.4 58	5.5 57	3.6 57	3.6
	y.5.100.2	74	1.4 76	4.1 74	1.4 73	0.5 73	0.5
	Média		8.1		11.5	7.6	6.0	5.8

  e[START_REF] Jaumard | Comparison of ILP formulations for the RWA problem[END_REF]. Nestes trabalhos podemos vericar que, apesar das abordagens diferentes dadas aos modelos, os limites superiores encontrados por eles são sempre 14} no grafo associado ao comprimento de onda 1. Este ciclo foi gerado no atendimento à requisição 8 entre os vértices {7, 1}. Contudo, como já dito anteriormente, isso não prejudica a recuperação da solução e a eliminação deste ciclo não inuencia o valor da função objetivo, que para o exemplo é igual a 10, ou seja, todas as requisições são atendidas.

	os mesmos e que a relaxação fornece valores muito próximos ou iguais aos valores
	ótimos. Com algumas adaptações na formulação baseada em arcos, Jaumard et
	al. [26] foram capazes de resolver algumas instâncias realísticas pela primeira vez.
	A seguir será mostrado que o modelo (JMT), apesar de impedir ciclos envolvendo
	os vértices origem e destino de cada requisição, não é capaz de prevenir todos os cic-
	los. Para alguns testes preliminares será usada a rede realística NSFnet apresentada
	na Figura 4.1. A Tabela 4.1 mostra as requisições com suas origens e seus destinos.
	Para o número de comprimentos de onda igual a dois a solução apresentada
	pelo modelo (KS) pode ser observada na Figura 4.2. São apresentados na gura
	somente os arcos que foram usados na solução, os arcos que não foram usados foram
	eliminados. Cada subgrafo representa as requisições atendidas por um mesmo com-
	primento de onda; no exemplo, o comprimento de onda 1 atende às requisições
	({3, 11}; {4, 12}; {6, 14}; {7, 1}; {11, 5}; {13, 4}), enquanto o comprimento de onda 2
	atende às requisições ({1, 11}; {2, 14}; {4, 14}; {5, 1}).
	Tabela 4.1: Requisições da rede NSFnet
	Requisição Origem Destino
	1	1	11
	2	2	14
	3	3	11
	4	4	12
	5	4	14
	6	5	1
	7	6	14
	8	7	1
	9	11	5
	10	13	4
	Observe que na solução apresentada pelo modelo (KS) existe um ciclo entre
	os vértices {8,		

  [START_REF] Gilmore | A linear programming approach to the cutting stock problem[END_REF] Note que, dessa forma, se uma requisição for atendida, as restrições (4.18) e (4.[START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] não garantem que o mesmo comprimento de onda que sai do vértice origem chegue ao vértice destino, mas ao combinarmos essas duas restrições à restrição (4.2) isso

		(RWA1) max	∑	x i	(4.22)
					i∈R
	passa a ser garantido, respeitando-se a restrição de continuidade do comprimento
	de onda.	∑		s.a:
	Continuando, para evitar ciclos onde requisições estejam desativadas podemos
	usar a seguinte restrição no modelo (KS): e∈ω + (j)
		∑	∑	x λ ie ≤ (|V | -1) × x i , ∀ i ∈ R	(4.21)
		λ∈Λ	e∈E	
	já que para qualquer grafo o maior caminho sem ciclo é sempre menor ou igual a
	(|V | -1). Dessa forma, se uma requisição estiver ativa permitimos que arcos sejam
	associados a ela, senão, o número de arcos associados a ela deve ser igual a zero.
	A restrição (4.7) garante que um arco só pode ser usado para uma requisição
	usando um comprimento de onda se este comprimento de onda estiver associado a
	esta requisição. Isto além de contribuir para a continuidade do comprimento de onda,
	ainda impede a formação de ciclos para requisições que não foram ativadas. Como
	a continuidade do comprimento de onda já é garantida pelas restrições mostradas
	anteriormente e a formação de ciclos não impede a recuperação da solução e nem
	afeta o valor da função objetivo esta restrição pode ser eliminada, diminuindo |R| ×
	|E| × |Λ| restrições do modelo.
	Com isso obtemos a formulação modicada, sobre o modelo (KS), que chamare-
	mos de (RWA1) mostrada pelas equações (4.22)-(4.29), a seguir:

  o objetivo de maximizar o número de requisições atendidas. Seja G p , dito grafo de conitos, um novo grafo onde cada vértice corresponde a um caminho em G e dois vértices em G p são adjacentes se os dois caminhos correspondentes em G têm pelo menos um arco em comum. Os caminhos podem ser um dado de entrada ou podem ser gerados por algum procedimento (Note que o número de caminhos entre os vértices origem-destino pode crescer exponencialmente[START_REF] Ramaswami | Routing and wavelength assignment in all-optical networks[END_REF]). A parte da alocação é tratada como um problema de conjuntos independentes. Em outras palavras, um conjunto de caminhos em G pode receber um mesmo comprimento de onda se e somente se os correspondentes vértices em G p formam um conjunto independente.

	4.2 Modelos Estendidos		
	Baseados na ideia de conjuntos independentes, Ramaswami e Sivarajan [46] apresen-
	taram uma formulação para o problema de roteamento e alocação de comprimentos
	4.1.2 Resultados Computacionais Nesta seção serão apresentados os testes comparando os modelos propostos com os modelos da literatura. Serão utilizadas nos testes desta seção dois conjuntos de instâncias. Um conjunto com a rede NFSnet com variações no número de requisições, com NFS.1 represen-tando a instância com 100% de requisições, ou seja, requisições entre todos os pares de vértices, NFS.08 com 80% e assim sucessivamente, onde a matriz de tráfego foi construída aleatoriamente. O outro conjunto de instâncias foi criado de acordo com a metodologia proposta em [43] para as instâncias do conjunto Z. De acordo com esta metodologia foram criadas duas redes com 12 e 16 vértices e são apresentadas variações no número de requisições da mesma maneira descrita anteriormente. As instâncias foram resolvidas utlizando o software CPLEX versão 9.1 em um 2 4 6 5 4 6 5 2 P 1 P 2 P 3 P 5 P 4 P 1 P 2 P 4 P 3 de onda com 1 3 1 3 P 5
	computador Dell Studio Core 2 Duo, 2.10 GHz, com 4 GB de RAM sob sistema
	operacional Ubuntu. (a) Rede KK	(b)	Caminhos Ópticos	(c)	Grafo de Conflitos
	A Tabela 4.2 apresenta os resultados para as quatro variações de modelos matemáti-
	cos com relação ao GAP encontrado pela relaxação linear e o tempo necessário para
	resolver o modelo relaxado. Na última coluna é apresentado o número de compri-
	mentos de onda disponíveis que nos testes foi variado de 3, 5 e 7. Estes resultados
	são para as instâncias do conjunto Z. A Tabela 4.3 apresenta os mesmos resultados
	com relação à variações na matriz de tráfego da instância NFSnet.

  Os caminhos denidos para realizar as requisições são p 1 = {1, 2, 3}, p 2 = {1, 2, 4}, p 3 = {2, 4, 5}, p 4 = {6, 4, 2, 3} e p 5 = {6, 4, 5}, veja Figura 4.5 (b). A Figura 4.5 (c) apresenta o grafo de conitos, onde cada vértice representa um caminho e cada aresta representa que os dois caminhos compartilham um arco no grafo original. As arestas do grafo de conitos pertencem ao conjunto E W . Pelo grafo de conito podemos ver que os conjuntos independentes deste exemplo são {p 1 }, {p 2 }, {p 3 }, {p 4 }, {p 5 }, {p 1 , p 3 }, {p 1 , p 5 }, {p 2 , p 4 }, {p 2 , p 5 } e {p 3 , p 4 }, onde os conjuntos com dois elementos são os conjuntos independentes maximais. O conjunto de comprimentos de onda disponíveis é denotado por Λ = λ 1 , λ 2 , . . . , λ W com W = |Λ|. Seja P o conjunto de todos os caminhos elementares (isto é, caminhos sem ciclos) e P sd o conjunto de caminhos elementares entre s e d. Seja L max o conjunto contendo todos os conjuntos independentes em G p . Seja δ pl a matriz que indica se um caminho p pertence ao conjunto independente l e ∑ p∈P sd δ pl = a l sd , para l ∈ L max . Seja w l o número de comprimentos de onda associado ao conjunto independente l, ou seja, cada conjunto independente pode ser usado w l vezes, e a l Jaumard et al. [27] mostraram como resolver este modelo usando geração de colunas. Seja lp-MAX-IS a relaxação do modelo ao trocarmos a restrição (4.47) por w l ≥ 0 para todo l ∈ L max . Como o número de conjuntos independentes maximais pode ser exponencial, trabalha-se no então chamado Problema Mestre Restrito (PMR) com todas as variáveis y sd tal que (s, d) ∈ R e um subconjunto de {w l : l ∈ L max }.

	Para vericar se a solução ótima do PMR é também solução ótima para o problema
	original é necessário vericar se existe uma variável w l com um custo reduzido pos-
	itivo. Se existe tal variável, ela é adicionada ao PMR, senão a solução é ótima para
	o problema original.			
	Seja u 0 a variável dual associada à restrição (4.44) e u 1 sd a variável dual associada
	à restrição (4.45). O custo reduzido para w l é:			
					sd
	o número de requisições entre o par {s, d} atendidas pelo conjunto l. O modelo
	MAX-IS é dado como segue:			
	(MAX-IS) max Z max-is (w, y) =	∑	y sd	(4.43)
	(s,d)∈R	
	s.a:			
	∑	w l ≤ W	(4.44)
	l∈Lmax y sd ≤ ∑	a l sd w l ,	∀ (s, d) ∈ R	(4.45)
	l∈Lmax		
	y sd ≤ r sd ,	∀ (s, d) ∈ R	(4.46)
		w l ∈ N,	∀ l ∈ L max	(4.47)

A variável y sd conta o número de requisições atendidas entre os vértices s e d para todo (s, d) em R. Ramaswami e Sivarajan

[START_REF] Ramaswami | Routing and wavelength assignment in all-optical networks[END_REF] 

propuseram a formulação MAX-IS mas não a utilizaram.

  apresentaram uma nova formulação em que utilizam somente as congurações de roteamento independentes maximais, onde uma conguração de roteamento independente C é maximal se não existe outra conguração de roteamento independente C ′ tal que a ′ c ≥ a c .Seja C max o conjunto de todas as congurações de roteamento independentes maximais e seja w c o número de vezes que uma determinada conguração é utilizada.

	O modelo pode ser dado como segue:	
	(MAX-IRC) max Z M AX-IRC (w, y) =	∑	y sd	(4.55)
						(s,d)∈R
				s.a:
						∑	w c ≤ W	(4.56)
				c∈Cmax y sd ≤ ∑	a c sd w c ,	∀ (s, d) ∈ R	(4.57)
						c∈Cmax
						y sd ≤ r sd ,	∀ (s, d) ∈ R	(4.58)
						w c ∈ N,	∀ c ∈ C max	(4.59)
	Sejam u 0 e u 1 sd as variáveis duais associadas respectivamente às restrições (4.56) e
	(4.57) na solução ótima do problema (MAX-IRC). O custo reduzido para a variável
	w c é -u 0 +	∑	a C sd u 1 sd . O subproblema pode ser denido como segue:
		(s,d)∈R			
	max c AU X-M AX-IRC (α) = -u 0 +	∑	∑	u 1 sd α sd e	(4.60)
			(s,d)∈R	e∈ω + (s)
			s.a:	
					∑	α sd e ≤ 1,	∀ e ∈ E	(4.61)
			∑	(s,d)∈R
			e∈ω + (i)	

  .2.1 Abordagem proposta Recapitulando, o modelo MAX-IS foi proposto por Ramaswami e Sivarajan[START_REF] Ramaswami | Routing and wavelength assignment in all-optical networks[END_REF] e não foi utilizado pelo fato de que para se ter garantia que a solução ótima será encontrada é necessário que todos os caminhos para cada uma das requisições sejam denidos a priori ou pelo menos todos os caminhos que farão parte da solução ótima. IS impedindo que um conjunto independente possa ser gerado com um número maior de caminhos explícitos do que a demanda solicitada. Seja a l um vetor de coecientes para uma variável w l em MAX-IS, onde cada elemento a l sd ≤ r sd para todo (s, d) ∈ R. Cada elemento do vetor representa o número de caminhos explícitos que podemos utilizar para atender uma fração da demanda com um mesmo comprimento de onda. Todos os caminhos usados para construir o vetor a l são disjuntos; logo, existe um vetor a c , de coecientes para uma variável w c em MAX-IRC, igual a a l . Assim, se as restrições (4.66) forem introduzidas no subproblema MAX-IS, qualquer variável em MAX-IS tem uma variável equivalente em MAX-IRC, logo, Z LP M AX-IS ≤ Z LP M AX-IRC . Por outro lado, se o modelo MAX-IS possui todos os caminhos possíveis para cada (s, d) ∈ R, cada vetor a c de caminhos implícitos em MAX-IRC pode ser convertido em pelo menos um vetor a l em MAX-IS, mesmo com as restrições (4.66), já que

	Jaumard et al. [27] aproveitaram as ideias do modelo MAX-IS e do modelo IRC [35] e propuzeram o modelo MAX-IRC. Neste trabalho foi mostrado que se relaxarmos as restrições (4.63), o modelo resultante, MAX-IRC-RL, apresenta soluções lineares iguais ao modelo MAX-IS, ou seja, Z LP M AX-IS = Z LP M AX-IRC-RL ≥ Z LP M AX-IRC . Note que esta restrição impede que uma conguração de roteamento independente seja formada atendendo um par origem destino com mais caminhos do que demandado. Note também que no modelo MAX-IRC os caminhos são gerados a cada chamada ao subproblema (caminhos implícitos), enquanto no modelo MAX-IS os caminhos são pré-denidos e apenas a combinação é denida no subproblema (caminhos ex-plícitos). Se o modelo MAX-IS gera soluções com limites piores que o modelo MAX-IRC pelo fato de poder gerar conjuntos independentes que não respeitam a demanda podemos introduzir a restrição (4.66), a seguir, ∑ p∈P sd α p ≤ r sd , ∀ (s, d) ∈ R (4.66) sd ≤ r sd para todo (s, d) ∈ R. Assim temos que se as restrições (4.66) forem utilizadas Z LP M AX-IS = Z LP M AX-IRC . 1 3 2 4 P 1 P 2 P 3 P 1 P 2 P 3 no subproblema MAX-a c (a) Grafo (b) (c) Caminhos Ópticos Grafo de Conflitos	
			.64)
	α sd e ∈ {0, 1},	∀ (s, d) ∈ R, e ∈ E	(4.65)
	Jaumard et al. [27] mostraram que esta formulação apresenta limites superi-	

ores tão bons quanto o modelo apresentado em

[START_REF] Lee | Optimal routing and wavelength assignment in WDM ring networks[END_REF]

, mas, no entanto, usam menos variáveis. Sendo assim, no mesmo trabalho foi apresentado um algoritmo Branchand-price baseado nesta última formulação. 4

  Até então o modelo MAX-IS não foi utilizado pela necessidade de se ter todos os caminhos possíveis para que a solução encontrada tenha garantia de ser ótima.Como o número de caminhos pode ser exponencial, o subproblema pode ser intratável. Suponhamos então que tenhamos a priori todos os caminhos da solução ótima faltando apenas denir a atribuição de cada caminho ao comprimento de onda que lhe convém. Assim podemos trabalhar usando somente os caminhos denidos a priori, ou seja, teremos um subconjunto L r ⊂ L max de variáveis w l que poderão fazer parte do problema.O modelo apresentado por[START_REF] Banerjee | Practical approaches for routing and wavelength assignment in large all-optical wavelength routed networks[END_REF] pode ser reformulado para dar uma boa previsão de quais serão os caminhos presentes em uma solução ótima. Dessa forma apresentamos um modelo de geração de colunas que fornecerá os caminhos que serão usados na fase de atribuição. Seja x p o número de vezes que o caminho p será utilizado e a ideia pode ser visualizada pela Figura 4.7. A área maior representa o conjunto convexo formado quando temos a priori todos os caminhos possíveis para a resolução do modelo MAX-IS. Nessa situação resolvemos o problema P , que tem a solução ótima indicada pela letra (a). A situação ideal para o modelo Path-Gen é gerar um subconjunto representado pelo problema P ′ , que apesar de não englobar todas as soluções de P , engloba a solução ótima. Como não podemos garantir que ao nal da execução do modelo Path-Gen todas os caminhos da solução ótima serão gerados, podemos chegar à situação apresentada pelo problema P ′′ em que a solução mostrada pela letra (b) não é a solução ótima do problema original.

						(a)
		P '		
						(b)
		P ''			
	P				
					∑	x p	(4.67)
		(s,d)∈R	p∈P sd
	s.a:				
	∑	∑	a e x p ≤ W	∀ e ∈ E	(4.68)
	(s,d)∈R	p∈P sd ∑	x p ≤ r sd ,	∀ (s, d) ∈ R	(4.69)
		p∈P sd		
					x p ∈ N,	∀ p ∈ P	(4.70)
	O subproblema da formulação Path-Gen pode ser resolvido por um algoritmo de
	caminho mínimo para cada par (s, d) em que o custo dos arcos é dado pelo valor
	dual das restrições (4.68). Assim, o primeiro algoritmo apresentado, PG-MAX-IS,
	utiliza somente os caminhos gerados pela formulação Path-Gen no modelo MAX-

4.63) no subproblema do modelo MAX-IRC e as restrições (4.66) no subproblema do modelo MAX-IS, as variáveis que utilizam os coecientes a c 3 e a l 4 não serão geradas. e = 1 se o caminho p utiliza o arco e e a e = 0 caso contrário. O modelo pode ser denido como segue: (Path-Gen) max Z path-gen (x) = ∑ IS. Obviamente a otimalidade da solução encontrada por esta estratégia não pode ser garantida, já que não se pode garantir que os caminhos gerados pelo modelo Path-Gen estarão realmente na solução ótima.

A

  Os testes computacionais foram executados da seguinte maneira: para cada método rodamos todas as instâncias com o número de comprimentos de onda disponíveis entre 10, 20 e 30. Os métodos executados são a versão de geração de colunas da literatura (MAX-IRC[START_REF] Jaumard | On column generation formulations for the RWA problem[END_REF]), o modelo de geração de caminhos combinado com o modelo MAX-IS (PG-MAX-IS) e o modelo de Path-Gen combinado com o modelo MAX-IS-IRC (PG-MAX-IS-IRC). Tabela 4.7 apresenta os resultados da comparação entre o método proposto em[START_REF] Jaumard | On column generation formulations for the RWA problem[END_REF] e os métodos propostos neste trabalho, somente com relação à função objetivo.Podemos ver que a estratégia de geração de caminhos desenvolvida para a utilização do modelo MAX-IS apresenta um bom desempenho e não compromete a qualidade das soluções para nenhuma das instâncias testadas quando usamos W = 10. Obeservamos isso analisando que todas as instâncias onde o método não consegue chegar na solução linear ótima, os valores são sempre menores que uma unidade, dessa maneira, por exemplo, para a instância brasil, onde a solução linear ótima é 721.50, sabemos que o limite superior para solução inteira será então 721, valor encontrado pelo método PG-MAX-IS. Podemos observar também que o método PG-MAX-IS-IRC é capaz de contornar as limitações do PG-MAX-IS como era de se esperar e encontra todas as soluções lineares ótimas. Observe que para a instância att2 o método MAX-IRC é interrompido com uma solução igual a 351.00 devido ao estouro Na Tabela 4.8 podemos ter uma visão mais esclarecedora sobre o desempenho do método PG-MAX-IS. Observamos que a metodologia é bastante eciente e encontra soluções tão boas quanto as outras para a maioria das instâncias, contudo podemos vericar nas instâncias att e f rance que as perdas começam a ser maiores que uma unidade, respectivamente, 1.5 e 7. Vericamos ainda que, novamente, a metodologia PG-MAX-IS-IRC foi capaz de encontrar as soluções ótimas com limites tão bons quanto o método MAX-IRC. Mais uma vez observamos que o método MAX-IRC não foi capaz de resolver a instância att2 devido a estouro de memória. Na Tabela 4.9 apresentamos os resultados somente para instâncias em que são necessários mais que 30 comprimentos de onda para atender todas as requisições. Vemos nesta tabela que para W = 30 o desempenho do método PG-MAX-IS é comparável aos demais e que a perda para estes testes, no pior caso foi de 0.50 para a instância nobel-us. Novamente o método PG-MAX-IS-IRC é capaz de encontrar exatamente os mesmos limites superiores do método MAX-IRC, que por sua vez novamente não foi capaz de resolver a instância att2. Apesar de ter apresentado um bom desempenho, o método PG-MAX-IS não pode garantir que a solução encontrada é verdadeiramente a solução ótima. Sendo assim, as tabelas (4.10) a (4.12) mostram uma comparação de desempenho somente dos métodos MAX-IRC e PG-MAX-IS-IRC. Nestas tabelas apresentamos o tempo gasto para encontrar a solução ótima de cada método e o número de variáveis geradas. Podemos ver que o método PG-MAX-IS-IRC sempre foi capaz de resolver as instâncias em um tempo inferior ao MAX-IRC. Das instâncias resolvidas pelo MAX-IRC a instância Finland foi a que demandou mais tempo deste método, 27780.5 segundos. Para esta instância, o método proposto, PG-MAX-IS-IRC, gasta apenas 269.2 segundos. Com relação ao número de variáveis geradas observamos que em geral o MAX-IRC necessita gerar um número menor de variáveis para encontrar a solução ótima, mas isto nem sempre é verdade como podemos vericar nas instâncias brasil, df n-gwin, f rance e nsf 3 por exemplo. Na Tabela 4.11 apresentamos a comparação de desempenho entre o MAX-IRC e o PG-MAX-IS-IRC para W = 20. Observamos que o comportamento permanece semelhante ao apresentado anteriormente. O método PG-MAX-IS-IRC sempre encontra a solução ótima em um tempo inferior ao MAX-IRC, este, por sua vez, não é capaz de encontrar a solução ótima para a instância att2. Também podemos ver que a instância F inland é a que demanda mais tempo do método MAX-IRC, 14078.7 segundos, enquanto o PG-MAX-IS-IRC gasta 629.2 segundos. Novamente, com relação ao número de variáveis geradas, o MAX-IRC, em geral, é capaz de encontrar a solução ótima com menos variáveis, mas isso nem sempre ocorre. Para nalizar apresentamos a Tabela 4.12 com os resultados do desempenho entre o MAX-IRC e o PG-MAX-IS-IRC para W = 30. O mesmo comportamento dos testes anteriores pode ser observado. O MAX-IRC em geral resolvendo as instâncias com menos variáveis, mas sempre utilizando um tempo maior. Dessa vez a instância que demandou mais tempo do MAX-IRC foi a instância giul, 21809.4 segundos. capítulo apresentamos primeiramente algumas variações nos modelos existentes para a resolução do max-RWA com o objetivo de simplicar esses modelos e assim poder resolver instâncias um pouco maiores dos que as resolvidas até então.

	Tabela 4.10: Resultados para W = 10 Tabela 4.11: Resultados para W = 20 4.3 Conclusão
	Modelos Modelos	MAX-IRC MAX-IRC		PG-MAX-IS-IRC MAX-IS-IRC
	Instâncias Instâncias	Tempo(s) ♯Var Tempo(s) ♯Var Tempo(s) ♯Var Tempo(s) ♯Var
	att att	653.9 106 254.9 106	18.2 44.7 531 325
	att2* att2*	-	-	1 1	567.4 3074.4 1626 997
	4.2.2 Resultados Computacionais Os algoritmos foram implementados na linguagem C++ usando o compilador Visual Tabela 4.6: Instâncias Realísticas Instâncias Requisições Arestas Nós att 359 137 90 att2 2918 175 71 brasil 1370 70 27 cost266 6543 57 37 dfn-bwin 4840 45 10 dfn-gwin 3771 47 11 eon 373 39 20 n 930 51 31 france 15398 45 25 giul 14732 86 39 janos-us 3262 42 26 nobel-eu 1898 41 28 nobel-germany 660 26 17 nobel-us 478 21 14 norway 5348 51 27 nsf1 284 21 14 nsf3 285 21 14 nsf12 551 21 14 nsf48 547 21 14 nsf2-1 284 22 14 nsf2-3 285 22 14 nsf212 551 22 14 nsf2-48 547 22 14 sun 952 51 27 nsf212 280.33 280.00 280.33 nsf2-48 266.33 266.00 266.33 sun 264.00 264.00 264.00 A de memória. Tabela 4.7: MAX-IRC × PG-MAX-IS -W = 10 Modelos MAX-IRC PG-MAX-IS PG-MAX-IS-IRC Instâncias Fo Fo Fo att 253.00 253.00 253.00 att2 351.00(*) 895.00 895.00 brasil 721.50 721.00 721.50 cost266 788.50 788.00 788.50 dfn-bwin 884.00 884.00 884.00 dfn-gwin 874.00 874.00 874.00 eon 285.00 285.00 285.00 n 444.77 444.00 444.77 france 610.00 610.00 610.00 giul 1561.00 1561.00 1561.00 janos-us 600.00 600.00 600.00 nobel-eu 346.00 346.00 346.00 nobel-germany 228.00 228.00 228.00 nobel-us 190.00 190.00 190.00 norway 834.00 834.00 834.00 nsf1 197.00 197.00 197.00 nsf3 195.50 195.00 brasil 7809.6 663 44.5 598 brasil 11111.6 930 110.8 967 Tabela 4.9: MAX-IRC × PG-MAX-IS -W = 30 cost266 2002.7 178 27.0 265 cost266 11498.2 828 220.9 832 Tabela 4.8: MAX-IRC × PG-MAX-IS -W = 20 Modelos MAX-IRC PG-MAX-IS PG-MAX-IS-IRC Instâncias Fo Fo Fo att 359.00 357.50 359.00 att2 351.00(*) 1298.00 1298.00 brasil 1080.67 1080.00 1080.67 cost266 1325.00 1325.00 1325.00 dfn-bwin 1733.00 1733.00 1733.00 dfn-gwin 1519.00 1519.00 1519.00 eon 369.00 369.00 369.00 n 642.00 642.00 642.00 france 1188.00 1181.00 1188.00 giul 2519.00 2519.00 2519.00 janos-us 981.00 981.00 981.00 nobel-eu 596.00 596.00 596.00 nobel-germany 384.00 384.00 384.00 nobel-us 326.50 326.50 326.50 norway 1377.00 1377.00 1377.00 nsf1 278.00 278.00 278.00 nsf3 277.00 277.00 277.00 nsf12 408.00 408.00 408.00 nsf48 389.00 389.00 Modelos dfn-bwin 0.3 3 0.0 9 dfn-bwin 1.8 23 0.0 25 MAX-IRC PG-MAX-IS PG-MAX-IS-IRC Instâncias Fo Fo dfn-gwin 4.0 31 0.1 28 dfn-gwin 12.1 105 0.2 75 Fo att2 351.00(*) 1648.00 eon 109.9 132 2.8 207 eon 21.2 64 3.8 270 1648.00 brasil 1241.00 1241.00 n 27780.5 1285 269.2 1308 n 14078.7 660 629.2 1554 1241.00 cost266 1728.94 1728.71 france 9.8 9 1.1 7 france 22.1 16 1.5 18 1728.94 dfn-bwin 2555.50 2555.50 giul 4015.8 409 102.0 525 giul 12400.4 572 107.9 492 2555.50 dfn-gwin 1945.00 1945.00 janos-us 105.6 67 5.6 97 janos-us 512.4 268 20.1 319 1945.00 n 774.00 774.00 nobel-eu 54.3 54 1.5 61 nobel-eu 108.6 113 3.2 108 774.00 france 1730.00 1730.00 nobel-germany 2.6 25 0.1 19 nobel-germany 6.9 59 0.4 70 1730.00 giul 3307.50 3307.50 3307.50 janos-us 1239.00 1239.00 nobel-us 0.9 17 0.1 37 norway 134.9 61 7.8 118 nobel-us 4.7 82 0.2 78 norway 1269.1 468 Tabela 4.12: Resultados para W = 30 29.1 393 1239.00 nobel-eu 822.00 822.00 822.00 nobel-germany 489.00 489.00 489.00 nobel-us 432.50 432.00 432.50 norway 1782.00 1782.00 1782.00 nsf12 499.00 499.00 499.00 nsf48 469.00 469.00 469.00 nsf212 522.00 522.00 522.00 nsf2-48 505.00 505.00 505.00 sun 722.00 722.00 nsf1 17.9 108 0.8 144 nsf3 22.0 138 0.6 107 nsf12 14.6 102 0.8 128 nsf48 22.8 139 0.7 118 nsf2-1 22.0 114 0.8 149 nsf2-3 19.0 110 0.8 160 nsf212 17.6 118 1.0 110 nsf2-48 23.7 134 1.1 125 sun 6.0 11 0.1 10 nsf1 9.6 99 1.1 197 nsf3 8.8 95 Modelos MAX-IRC PG-MAX-IS-IRC 0.8 146 nsf12 25.3 181 Instâncias Tempo(s) ♯Var Tempo(s) ♯Var 1.1 169 nsf48 17.4 116 att2* -1 7149.7 0.8 135 nsf2-1 7.0 71 brasil 1242.6 198 58.8 0.6 125 nsf2-3 10.8 111 cost266 19060.1 1226 339.2 0.6 126 nsf212 24.8 159 dfn-bwin 2.8 36 0.1 1.0 160 nsf2-48 24.8 151 dfn-gwin 7.5 63 0.2 1.1 171 sun 21.9 35 n 15849.0 777 717.0 0.3 70 france 30.9 24 1.7 722.00 giul 21809.4 702 128.3 389.00 nsf2-1 282.00 282.00 282.00 nsf2-3 284.00 284.00 janos-us 649.2 300 22.8 Para esta instância, o PG-MAX-IS-IRC gasta apenas 128.3 segundos para encontrar nobel-eu 324.9 272 7.2 284.00 nsf212 427.00 427.00 427.00 nsf2-48 413.00 413.00 nobel-germany 10.7 95 0.5 a solução ótima. nobel-us 11.3 180 0.6 413.00 sun 502.00 502.00 norway 1996.2 609 45.7 502.00 nsf12 16.4 134 0.8 195.50 nsf12 264.00 264.00 nsf48 11.1 87 0.6 264.00 nsf48 254.00 254.00 nsf212 17.7 151 1.2 254.00 nsf2-1 205.00 205.00 nsf2-48 21.1 148 1.1 205.00 nsf2-3 206.00 206.00 206.00 sun 78.3 112 1.8
	Studio e testados em um microcomputador Dell Optiplex 780, 3.00 GHz, com 3.25
	GB de RAM sob sistema operacional Windows XP.
	Para os testes foram usadas 24 instâncias disponíveis na literatura, conhecidas

.76) Repare que, agora, com o modelo MAX-IS-IRC, temos a opção de gerar variáveis w l e w c , utilizando os subproblemas já apresentados anteriormente para cada um dos modelos. Em nosso algoritmo, PG-MAX-IS-IRC, utilizamos a seguinte estratégia: primeiramente geramos os caminhos através do modelo Path-Gen e geramos o grafo de conitos. Em seguida, utilizamos o modelo MAX-IS-IRC sempre gerando variáveis w l , que em geral é mais fácil de ser resolvido já que os caminhos já estão calculados. Somente tenta-se gerar uma variável w c quando o custo reduzido da variável w l for menor ou igual zero. Se os custos reduzidos de w l e w c são menores ou iguais a zero em uma iteração signica que a solução é ótima. como instâncias realísticas. As características, como número de requisições, número de arestas e número de nós, de cada uma das instâncias estão descritas na Tabela 4.6. A Tabela 4.10 apresenta a comparação entre o MAX-IRC e o PG-MAX-IS-IRC para W = 10. O método MAX-IRC não foi capaz de resolver a instância att2. Neste

de VND r -ILS p , VND e -ILS p , VND r -ILS 5p e VND e -ILS 5p .