Use este identificador para citar ou linkar para este item: http://hdl.handle.net/1843/BUOS-9AXH2H
Tipo: Tese de Doutorado
Título: Metaheurísticas e formulações para a resolução do problema de roteamento e alocação de comprimentos de onda em redes ópticas
Autor(es): Alexandre Xavier Martins
Primeiro Orientador: Rodney Rezende Saldanha
Segundo Orientador: Philippe Mahey
Primeiro Coorientador: Mauricio Cardoso de Souza
metadata.dc.contributor.advisor-co2: Christophe Duhamel
Resumo: Nesta tese, apresenta-se um estudo sobre o Problema de Roteamento e Alocação de Comprimentos de Onda em redes ópticas WDM independentemente da topologia física subjacente. Inicialmente é feita uma revisão da literatura apresentando alguns modelos matemáticos formulados para a resolução do problema, também são revistosmétodos para denição de limites inferiores e métodos heurísticos. Por se tratar de um problema da classe NP-difícil muitas heurísticas vêm sendo propostas para a sua resolução. Apresentamos neste trabalho uma metodologia baseada na metaheurística Descida em Vizinhança Variável (Variable Neighborhood Descent-VND ), que chamamosVND-BFD, primeiramente com o foco na eliminação dos comprimentos de onda e um método híbrido VND-BT para a resolução do problema.Depois introduzimos uma nova abordagem também baseada no VND, mas dessa vez com o foco voltado para o rearranjo das requisições, quando esta nova versão do VND falha o método ativa um procedimento de perturbação. O novo método alterna entre uma busca através do VND e de uma perturbação, como na metaheurística Iterated Local Search. Denimos quatro variantes para este método, que chamamos de VNDr-ILSp, VNDe-ILSp, VNDr-ILS5p e VNDe-ILS5p. As comparações feitas mostram que a abordagem com foco nas requisições semostrou a mais eciente com destaque para a versão VNDe-ILS5p. O método proposto é competitivo com relação aos melhores métodos apresentados na literatura até então, e foi capaz de melhorar a grande maioria dos limites superiores para as instâncias ainda em aberto. Por m, apresentamos modelos compactos voltados para a maximização da quantidade de requisições atendidas e algumas simplicações são propostas com o intuito de acelerar a resolução dos problemas. Ainda apresentamos alguns modelos da literatura baseados em geração de colunas e uma nova metodologia é proposta. Nos testes realizados esta nova metodologia, que chamamos PG-MAX-IS-IRC, foi capaz de resolver todas as instâncias em tempo sempre inferior ao método da literaturaque usamos na comparação e sempre encontrado o mesmo limite superior deste.
Abstract: This work deals with the routing and Wavelength assignment (RWA) in optical WDM networks independently on the underlying physical topology. We begin with a review of the literature presented some mathematical models formulated to solve the problem, are also reviewed methods for setting lower bounds and heuristic methods. This problem has been shown to be NP-Hard and several heuristic algorithms have been developed to solve it. We present in this work a methodology based on metaheuristic Variable Neighborhood Descent (VND), which we call VND-BFD, primarily with the focus on the elimination of wavelengths and a hybrid method VND-BT to solve the problem. Then we introduce a new approach also based on VND, but this time with the focus on the rearrangement of the requests, when this new version of the VND failsthe procedure activates a disturbance, as the metaheuristic Iterated Local Search. We dene four variants to this method, which we call VNDr-ILSp, VNDe-ILSp, VNDr-ILS5p and VNDe-ILS5p. The computational experiments show that the approach with the focus on requests proved more ecient, especially the version VNDe-ILS5p. The proposed method is competitive with respect to the best methods in the literature. Finally, we present compact models aimed at maximizing the number of requestsaccepted and some simplications are proposed in order to hasten the resolution of problems. Although we present some models of literature based on column generation and a new methodology is proposed. The new methodology, which we call PG-MAX-IS-IRC, was able to solve all instances faster than the method of the literature and always found the same upper bound.
Assunto: Engenharia elétrica
Idioma: Português
Editor: Universidade Federal de Minas Gerais
Sigla da Instituição: UFMG
Tipo de Acesso: Acesso Aberto
URI: http://hdl.handle.net/1843/BUOS-9AXH2H
Data do documento: 22-Ago-2011
Aparece nas coleções:Teses de Doutorado

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
219d.pdf1.35 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.