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.