SOLUÇÕES HEURÍSTICAS PARA O PROBLEMA DE ATRIBUIÇÃO DE LOCALIDADES A ANÉIS EM REDES SONET
Metaheurísticas
Otimização Combinatória
Particionamento em Grafos
Projeto de redes de telecomunicações
Problema de atribuição de localidades a anéis SONET
Reconexão de caminhos
Otimização combinatória (Computação)
Heurística
Rede de comunicação de computadores
Metaheurística GRASP
Tomada de decisão
Abstract
Neste trabalho, abordaremos um problema de otimização combinatória que surge no projeto de redes de telecomunicações. Este problema é conhecido como Problema de Atribuição de Localidades a Anéis SONET (SONET ring assignment problem) (SRAP). Neste problema, cada localidade cliente deve ser atribuída a exatamente um anel SONET e um anel especial, chamado de Anel Federal, interliga os anéis entre si. É imposta sobre cada anel uma restrição de capacidade. O objetivo do problema é encontrar uma atribuição de localidades clientes que minimize o número total de anéis utilizados. Descreveremos um procedimento GRASP, incluindo o conceito de reconexão de caminhos, para encontrar soluções de boa qualidade para o SRAP. Em adição às instâncias disponíveis na literatura, desenvolvemos instâncias maiores para testar nossos algoritmos. Experimentos computacionais sobre as instâncias disponíveis para teste são reportados, comparando o GRASP com reconexão de caminhos com o GRASP proposto previamente (sem reconexão de caminhos) e com outros algoritmos encontrados na literatura. Os resultados dos experimentos ilustram a eficiência do método proposto, sobre outros métodos, em obter soluções ótimas ou muito próximas do valor ótimo
[Texto sem Formatação]
[Texto sem Formatação]
Document type
DissertaçãoSource
BASTOS, Lucas de Oliveira. Soluções heurísticas para o problema de atribuição de localidades a anéis em redes SONET. 2005. 86 f. Dissertação (Mestrado em Computação) - Programa de Pós-Graduação em Computação, Instituto de Computação, Universidade Federal Fluminense, Niterói, 2005.Subject(s)
GRASPMetaheurísticas
Otimização Combinatória
Particionamento em Grafos
Projeto de redes de telecomunicações
Problema de atribuição de localidades a anéis SONET
Reconexão de caminhos
Otimização combinatória (Computação)
Heurística
Rede de comunicação de computadores
Metaheurística GRASP
Tomada de decisão