Utilize este identificador para referenciar este registo:
https://hdl.handle.net/10316/40445
Título: | Encaminhamento de ligações multiponto | Autor: | Barbosa, Rui Miguel Lopes Ribeiro Ferreira | Orientador: | Martins, Lúcia Maria dos Reis Albuquerque | Palavras-chave: | problema de Steiner; otimização multi-objetivo; tabu search; ligações multiponto-multiponto; Steiner problem; multi-objective optimization; tabu search; multipoint-tomultipoint virtual connections | Data: | 29-Jul-2014 | Local de edição ou do evento: | Coimbra | Resumo: | 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. |
Descrição: | 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 | Direitos: | openAccess |
Aparece nas coleções: | UC - Dissertações de Mestrado FCTUC Eng.Electrotécnica - Teses de Mestrado |
Ficheiros deste registo:
Ficheiro | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Encaminhamento de ligacoes multiponto.pdf | 1.18 MB | Adobe PDF | Ver/Abrir |
Google ScholarTM
Verificar
Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.