Um algoritmo do tipo Beam Search para alocação de células a centrais de telefonia celular

Abstract

O problema de atribuição de células as centrais de telefonia móvel é um problema combinatório do tipo NP-completo. Isto significa que a alternativa para a solução deste tipo de problema é a utilização de métodos heurísticos, pois eles permitem que se encontre uma solução de boa qualidade num tempo computacional bastante satisfatório. Neste artigo é apresentado um algoritmo de Beam Search, para resolver o Problema de Atribuição de Células às Centrais de Telefonia Móvel. São também apresentadas algumas modificações deste algoritmo, que permitem sua implementação em paralelo. Foram feitos testes computacionais com problemas considerados grandes obtendo-se boas soluções. Observou-se que as versões modificadas do algoritmo, em muitos casos, produziram soluções de melhor qualidade.