Navegando por Autor "Libório, Felipe Tenório de Holanda Rocha"

Agora exibindo 1 - 1 de 1

Algoritmos Exatos e Heurísticos para os Problemas de Steiner e de Conexão de Terminais com Número Restrito de Roteadores e Elos
(2019-07-08) Libório, Felipe Tenório de Holanda Rocha; Pinheiro, Rian Gabriel Santos; http://lattes.cnpq.br/1447954471683870; http://lattes.cnpq.br/1881833645223497
Neste trabalho foram apresentadas soluções para o Problema de Conexão de Terminais com Número Restrito de Roteadores e Elos (TCP, do inglês Terminal Connection Problem). O TCP consiste em encontrar uma árvore que conecte um subconjunto de vértices de um dado grafo. Ele se diferencia do problema de Steiner pela introdução de uma restrição adicional ao número de vértices de Steiner que podem fazer parte de uma solução. O TCP pode ser aplicado nos mesmos tipos de problema em que se pode fazer uso do problema de Steiner, o que inclui: projetos de circuitos VLSI; roteamento multicast; modelar e resolver problemas de planejamento em telecomunicações; e distribuição de eletricidade. Como o TCP é uma generalização do problema de Steiner em grafos, também foram feitos testes em instâncias deste problema. Além disso, foram geradas diversas instâncias de diferentes níveis de dificuldade para o TCP, que trabalhos posteriores poderão utilizar para a comparação da performance de futuras soluções. Os resultados obtidos nas instâncias do Problema de Steiner foram comparados ao de outra solução da literatura e a meta-heurística utilizada na solução, a Large Neighborhood Search (LNS), se mostrou viável como uma forma simples e de baixo custo computacional, tanto em tempo de execução quanto em requisitos de memória, de se obter resultados satisfatórios para este problema. Conseguindo uma taxa de erro média abaixo de 2% nas instâncias avaliadas, a depender do tempo de execução dado ao algoritmo. Além disso, este é o primeiro trabalho a apresentar soluções para o TCP de que se tem conhecimento. Foi implementada, além da solução meta-heurística, uma solução exata com o uso do solver IBM Ilog CPLEX. Para as instâncias avaliadas cujos valores ótimos foram encontrados pela solução exata apresentada, a implementação da LNS obteve taxa de erro média de 0,66% ao mesmo tempo em que apresentou um tempo de execução 22 vezes menor que a solução exata e conseguiu obter o valor ótimo em 14 das 18 instâncias testadas. Os resultados obtidos na resolução das instâncias do TCP, juntamente às próprias instâncias geradas, formaram uma base para comparações de soluções futuras que possam vir a ser propostas para o problema.