Soluções heurísticas para o problema de atribuição de localidades a anéis em redes SONET

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