Metaheurísticas e formulações para a resolução do problema de roteamento e alocação de comprimentos de onda em redes ópticas

• Ano de defesa: 2011
• Autor(a) principal: Alexandre Xavier Martins
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Minas Gerais; UFMG
• Palavras-chave em Português: Engenharia Elétrica; Engenharia elétrica
• Link de acesso: http://hdl.handle.net/1843/BUOS-9AXH2H

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.