Please use this identifier to cite or link to this item: https://hdl.handle.net/10316/40445
Title: Encaminhamento de ligações multiponto
Authors: Barbosa, Rui Miguel Lopes Ribeiro Ferreira 
Orientador: Martins, Lúcia Maria dos Reis Albuquerque
Keywords: problema de Steiner; otimização multi-objetivo; tabu search; ligações multiponto-multiponto; Steiner problem; multi-objective optimization; tabu search; multipoint-tomultipoint virtual connections
Issue Date: 29-Jul-2014
Place of publication or event: Coimbra
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.
Description: Dissertação de Mestrado Integrado em Engenharia Electrotécnica e de Computadores apresentada à Faculdade de Ciências e Tecnologia da Universidade de Coimbra
URI: https://hdl.handle.net/10316/40445
Rights: openAccess
Appears in Collections:UC - Dissertações de Mestrado
FCTUC Eng.Electrotécnica - Teses de Mestrado

Files in This Item:
File Description SizeFormat
Encaminhamento de ligacoes multiponto.pdf1.18 MBAdobe PDFView/Open
Show full item record

Page view(s) 20

633
checked on Mar 26, 2024

Download(s)

1,190
checked on Mar 26, 2024

Google ScholarTM

Check


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