Encaminhamento de ligações multiponto

Abstract

O objetivo deste trabalho foi o estudo do problema de Steiner em grafos e sua aplicação na determinação de ligações multiponto-multiponto em redes de Telecomunicações, em particular em redes de transporte. Sendo assim, estudou-se mais profundamente uma heurística de referência para o problema de Steiner e ainda uma meta-heurística que obtém muito bons resultados para este problema. Em problemas reais, para além de se querer obter as árvores de menor custo (aditivo) para a interligação de um subconjunto de nós da rede envolvidos em cada ligação multipontomultiponto, custo esse que pode representar, por exemplo, a ocupação de cada link, também se pode pretender obter as árvores com um número mínimo de arcos, por forma a que as ligações multiponto-multiponto possam ser implementadas com o mínimo de recursos da rede. Assim formula-se um problema de Steiner bi-critério para o qual se propõe uma extensão da meta-heurística anterior de modo a resolver esse problema. Os resultados obtidos pela implementação da meta-heurística original (mono-critério) são comparados exaustivamente com os resultados obtidos pelos seus autores, o que permitiu tirar conclusões sobre a forma pouco clara como estes últimos resultados foram conseguidos, bem como identificar aspetos em que a meta-heurística poderia ser melhorada. Estas conclusões foram fundamentais para o desenvolvimento de uma meta-heurística, baseada em princípios idênticos à anteriormente referida, para a resolução do problema bi-critério. No problema bi-critério, a meta-heurística desenvolvida revelou-se bastante superior a três outras heurísticas desenvolvidas anteriormente para a resolução do mesmo problema. Os resultados obtidos permitem ainda identificar aspetos que podem vir a ser melhorados em trabalhos futuros.

The main purpose of this master thesis was the study of the Steiner problem in graphs for the obtaining of multipoint-to-multipoint virtual connections in communication transport networks. Therefore, a reference heuristic and also a meta-heuristic that obtains very good results for this problem were studied and implemented. In real problems it may be advantageous not only the obtaining of the lowest-cost trees for interconnecting a given subset of network nodes involved in each multipoint-to-multipoint virtual connection, where the cost can represent, for instance, the occupancy of each link, but also the obtaining of trees with the minimum number of arcs, so that multipoint-to-multipoint virtual connections might be implemented with the minimum of network resources. So a bi-criteria Steiner tree problem was formulated and in order to solve it an extension of the previous meta-heuristic was proposed. The results obtained by the implementation of the original meta-heuristic (single-criterion) are compared in detail with the results obtained by their authors. From this comparison, two main conclusions were achieved: i) some very good results presented by the authors of the meta-heuristic were obtained through procedures not clearly documented; ii) some aspects of the meta-heuristic can be improved. These conclusions were taken into account in the development of a meta-heuristic for the bi-criteria problem, based on identical principles. The last meta-heuristic proved to be superior to three other previously developed heuristics for the same problem. The results also allowed the identification of some aspects that may be improved in future work.