Algoritmos Exatos e Heurísticos para os Problemas de Steiner e de Conexão de Terminais com Número Restrito de Roteadores e Elos

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.