[en] ALGORITHMS FOR OPTIMIZATION PROBLEMS APPLIED TO ROUTING AND WAVELENGTH ASSIGNMENT

[pt] ALGORITMOS PARA PROBLEMAS DE OTIMIZAÇÃO APLICADOS A ROTEAMENTO E ATRIBUIÇÃO DE COMPRIMENTOS DE ONDA

[pt] THIAGO FERREIRA DE NORONHA

[pt] OTIMIZACAO COMBINATORIA

[pt] ATRIBUICAO DE COMPRIMENTOS DE ONDA

[pt] ALGORITMOS EXATOS

[pt] ROTEAMENTO

[pt] HEURISTICA

[en] COMBINATORIAL OPTIMIZATION

[en] ROUTING

[en] HEURISTICS

[pt] O problema de roteamento e atribuição de comprimentos de onda em redes óticas WDM consiste em rotear um conjunto de caminhos óticos e atribuir um comprimento de onda para cada um deles de modo que dois caminhos óticos cujas rotas compartilham alguma fibra ótica tenham comprimentos de onda diferentes. O objetivo é minimizar o número total de comprimentos de onda utilizados para rotear todos os caminhos óticos. Este problema é conhecido na literatura como min-RWA e está provado que ele pertence à classe dos problemas NP-Difíceis. Primeiramente, são propostos nesta tese algoritmos e estruturas de dados que permitem a implementação eficiente das melhores heurísticas na literatura. Em seguida propõe-se um algoritmo genético com chaves aleatórias para min-RWA. Este algoritmo estende a melhor heurística na literatura adaptando-a a um paradigma evolucionário. Por fim, propõe-se um algoritmo de Branch-and-Cut para o problema de coloração de partições (PCP), o qual é uma generalização do problema de coloração de grafos. Algoritmo para PCP vem sendo usados na literatura como ferramentas para construção de algoritmos para min-RWA. São propostas uma formulação por programação linear inteira para PCP, desigualdades válidas e um algoritmo de planos de corte. Experimentos computacionais são apresentados para instâncias em grafos aleatórios e instâncias de PCP originadas de instâncias de min-RWA.

[en] The problem of routing and wavelength assignment in WDM optical networks consists in routing a set of lightpaths and assigning a wavelength to each of them, such that lightpaths whose routes share a common fiber are assigned to different wavelengths. The objective is to minimize the total number of wavelengths used for routing all connections. This problem is called min-RWA and was shown to be NP-hard. In this thesis, we first propose efficient implementations of the state-of-art heuristics in the literature and reevaluate them on a broader set of test instances. Following, we propose a random-keys genetic algorithm for min-RWA. This algorithm extends the best heuristic in the literature by embedding it into an evolutionary framework. Computational results showed that the new heuristic improves the state-of-the-art algorithms in the literature even when they were close to the optimal solution. Finally, we propose a branch-and-cut algorithm for the Partition Coloring Problem (PCP), which is a generalization of the graph coloring problem. Algorithms for PCP have been used in the literature as building blocks for algorithms for min-RWA. An integer programming formulation, valid inequalities, and a cutting plane procedure are proposed. Computational experiments are reported for random graphs and for PCP instances originating from min-RWA instances.

CELSO DA CRUZ CARNEIRO RIBEIRO

CARLOS JOSE PEREIRA DE LUCENA

CARLOS JOSE PEREIRA DE LUCENA

CELSO DA CRUZ CARNEIRO RIBEIRO

EDWARD HERMANN HAEUSLER

CID CARVALHO DE SOUZA

LUCIANA SALETE BURIOL

SIMONE DE LIMA MARTINS

2009-06-08

2008-09-05

[pt] TEXTO

application/pdf

application/pdf

application/pdf

application/pdf

application/pdf

application/pdf

application/pdf

application/pdf

PORTUGUÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=13749@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=13749@2