Please use this identifier to cite or link to this item:
Title: Soluções heurísticas para o problema de atribuição de localidades a anéis em redes SONET
Keywords: Ciência da computação;  Otimização combinatória (Computação);  Heurística;  Rede de comunicação de computadores;  GRASP;  Metaheurísticas;  Particionamento em grafos;  Problema de atribuição de localidades a anéis SONET;  Projeto de redes de telecomunicações;  Reconexão de caminhos
Issue Date: 2-Dec-2005
Abstract: In this work, we consider a combinatorial optimization problem that arises in telecommunications networks design. It is known as the SONET ring assignment problem (SRAP). In this problem, each client site has to be assigned to exactly one SONET ring and a special ring, called Federal Ring, interconnects the other rings together. A capacity constraint on each ring is also imposed. The problem is to find a feasible assignment of the client sites minimizing the total number of rings used. We describe a greedy randomized adaptive search procedure (GRASP), including the path-relinking concept, for finding good-quality solutions of the SRAP. In addition to instances found in literature, we have developed new larger instances to test our algorithms. Computational experiments on benchmark instances are reported, comparing the GRASP with path-relinking with previously proposed pure GRASP (without path-relinking) and with other algorithms found in the literature. Experimental results illustrate the effectiveness of the proposed method, over other methods, to obtain solutions that are either optimal or very close to it.
Appears in Collections:TEDE sem arquivo

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.