Uma abordagem via metaheurística híbrida para o problema de atribuição de localidade a anéis sonet/sdh

Abstract

The Telecommunication systems are in the phase of major transformations and expansions, which make telecommunication network planning problems increasingly larger and complex. In this context, many of these problems can be formulated as combinatorial optimization models, and the use of heuristic algorithms can help solve these issues in the planning phase. This paper proposes an implementation of the BRKGA (Biased Random-Key Genetic Algorithm) metaheuristic - in addition to two hybrid implementations - BRKGA with Vocabulary Building (BRKGA + VB) and BRKGA with Q-learning (BRKGA + QL) - to be applied to problem SONET Ring Assignment Problem – SRAP. In this problem, each customer location must be assigned to exactly one SONET ring, also called the local ring and a special ring, called the Federal Ring, which interconnect the local rings with each other. A capacity constraint is imposed on each ring. The solution looking for the problem is to find an allocation of customer locations that minimize the total number of rings used, since the fewer rings the lower the cost of the telecommunication network planning. This problem is the class NP-hard, so it can not be guaranteed to obtain the best results for all instances using the exact algorithms, with a viable computational time. It is proposed to solve this problem with the heuristic methods mentioned above. The algorithms were implemented in the JAVA programming language and used the instances of classes C1, C2, C3 and C4 to perform computational experiments. The analysis of the experiments showed the competitiveness of the proposed algorithms against the best results found in the literature