Sistemas eixo-raio de múltipla atribuição:: modelos e algoritmos

by de Camargo, Ricardo Saraiva

Em sistemas de telecomunicações e de transporte, o problema localização de concentradores com atriuição múltipla surge quando demandas entre muitos pares de origem-destino devem ser enviadas.Ao invés de servir cada demanda entre uma origem e um destino com uma conexão direta, os fluxos são reunidos a partir de concentradores (\textit{hubs}) e enviados, através de uma rede de concentradores, para serem então entregues aos respectivos destinos. Sistemas com esse tipo de topologia são chamados de sistemas do tipo eixo-raio ou redes do tipo eixo-raio. Essas redes são projetadas para usufruírem da economia de escala obtida ao se concentrar o fluxo durante o transporte e/ou transmissão entre concentradores. Portanto, o problema consiste em encontrar a configuração de rede eixo-raio com o menor custo possível selecionando quais locais a se instalar um concentrador e atribuindo o tráfego a cada um, dados os custos de instalação, de transporte e a demanda entre os pares de origem e destino. No presente trabalho, três versões diferentes do problema são estudadas: o problema clássico, a economia de escala dependente do fluxo e o congestionado. Algoritmos eficientes baseados no métodode Decomposição de Benders foram empregados na resolução dos problemas, resolvendo instâncias de grande porte, consideradas fora do alcance'' de métodos exatos, em um tempo aceitável.