Algoritmos Heurísticos e Meta-Heurísticas Híbridas Aplicadas ao Planejamento de Uma Rede de Telecomunicações com Topologia Anel-Estrela

O problema apresentado surge no planejamento de uma rede de telecomunicações, sendo conhecido como Problema do Ciclo Mediano sem Restrições de Capacidade. No PCMRC a meta é localizar um anel através de um subconjunto de nós com objetivo de minimizar a soma dos custos de roteamento, ou seja, o custo de ligação dos nós do anel, e de atribuição dos nós fora do anel aos nós mais próximos no anel. Foram propostas metaheurísticas híbridas Simulated Annealing + Busca Tabu (BT), GRASP + BT e GRASP + GVNS, onde experimentos computacionais compravaram a eficiência da metaheurística GRASP associada a outra metaheurística que expanda a vizinhança, assim dentre as metaheurísticas testadas a GGVNS destacou-se quanto à qualidade das soluções obtidas quando comparada às outras metaheurísticas propostas e também à técnica VNTS proposta na literatura.