Please use this identifier to cite or link to this item: https://repository.ufrpe.br/handle/123456789/1428
Title: Algoritmos Exatos e Heurísticos para os Problemas de Steiner e de Conexão de Terminais com Número Restrito de Roteadores e Elos
Authors: Libório, Felipe Tenório de Holanda Rocha
metadata.dc.contributor.authorLattes: http://lattes.cnpq.br/1881833645223497
metadata.dc.contributor.advisor: Pinheiro, Rian Gabriel Santos
metadata.dc.contributor.advisorLattes: http://lattes.cnpq.br/1447954471683870
Keywords: Computação;Algoritmos
Issue Date: 8-Jul-2019
Citation: LIBÓRIO, Felipe Tenório de Holanda Rocha.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.60 f. Trabalho de Conclusão de Curso (Bacharelado em Ciência da Computação) – Unidade Acadêmica de Garanhuns, Universidade Federal Rural de Pernambuco, Garanhuns, 2019.
Abstract: This work presents solutions for the Terminal Connection Problem with Bounded Number of Routers and Links (TCP). The TCP consists in finding a spanning tree to a subset of vertices of a given graph. It differentiates itself from the Steiner’s problem by having additional restrictions to the number of Steiner nodes allowed in a solution. The TCP can be applied in the same types of problems on which you can make use of the Steiner’s problem, which includes: VLSI circuit project; multicast routing; to model and solve telecomunications planning problems; and electricity distribution. As the TCP is a generalization on the Steiner’s problem in graphs, tests in instances of this problem were also made. Moreover, a multitude of instances of different difficulty levels was generated for the TCP, instances which posterior works on the problem will be ablem to use for comparing the performance of future solutions. The results obtained for the Steiner Problem instances were compared to those of another solution found in the literature, and the metaheuristic utilised to solve them, the Large Neighborhood Search (LNS), has shown to be viable as a simple and low cost, both in time and in memory requirements, way of reaching satisfactory results for this problem. Achieving a mean error below 2% for the evaluated instances, depending on the time given for the aolgorithm. Furthermore, this is the first known work to present a solution to the TCP. Besides the LNS metaheurístic, an exact solution was implemented by the means of the IMB ILOG CPLEX solver. For the tested instances whose optimal values were found by the presented exact solution, the LNS implementation managed to get an mean error rate of 0.66% meanwhile having a run time 22 times smaller than that of the exact solution and found the optimal value in 14 out of the 18 tried instances. The results obtained on the solving of the TCP instances, alongside the generated instances themselves, have formed a base for the comparison of future solutions that may come to be Proposed for this problem.
Description: 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.
URI: https://repository.ufrpe.br/handle/123456789/1428
Appears in Collections:TCC - Bacharelado em Ciência da Computação (UAG)

Files in This Item:
File Description SizeFormat 
tcc_felipetenóriodeholandarochalibório.pdf906,15 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.