Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.5/6124
Título: Uma variante do problema da floresta de Steiner em grafos com aplicações em biologia da conservação
Autor: Brás, Raúl Massano
Orientador: Cerdeira, Jorge
Pinto, Leonor Santiago
Palavras-chave: Optimização Combinatória
Grafos
Heurísticas
Árvores Mínimas de Steiner
Conexidade
Programação Inteira
Combinatorial optimization
Graphs
Heuristics
Minimum Steiner Trees
Connectivity
Integer Programming
Data de Defesa: 2013
Editora: Instituto Superior de Economia e Gestão
Citação: Brás, Raúl Massano. 2013. "Uma variante do problema da floresta de Steiner em grafos com aplicações em biologia da conservação". Tese de Doutoramento. Universidade de Lisboa. Instituto Superior de Economia e Gestão.
Resumo: A fragmentação de habitats é uma ameaça séria à sustentabilidade das espécies ecológicas. Assim, a identificação de ligações eficientes entre unidades ecológicas, é uma questão importante em biologia da conservação. O estabelecimento de ligações eficientes, deve levar em conta que as áreas que são adequadamente permeáveis para a dispersão de algumas espécies, podem agir como obstáculos para outras. A determinação de ligações eficazes, com custo míınimo, é uma generalização dos problemas da árvore Steiner com custos nos nós e da floresta de Steiner com custos dos nós. A tese apresenta e compara formulações e heurísticas para este problema. As heurísticas foram especialmente concebidas para lidar com instâncias de grande dimensão, que ocorrem em biologia da conservação. As heurísticas são comparadas utilizando dados simulados e reais para a Península Ibérica. Uma vez que o problema da floresta de Steiner com custos nos nós é um caso particular do problema estudado, as heurísticas propostas são também comparadas com uma heurística bem conhecida para este caso. A elaboração da tese, levou ao desenvolvimento de uma aplicação informática de código aberto, que foi colocada à disposição da comunidade científica.
Habitat fragmentation is a serious threat for the sustainability of species. Thus, the identification of effective linkages to connect valuable ecological units is an important issue in conservation biology. The design of effective linkages should take into account that areas which are adequately permeable for some species’ dispersal may act as obstructions for other species. The determination of minimum cost effective linkages is a generalization of both node-weighted Steiner tree and node-weighted Steiner forest problems. The thesis presents and compares formulations and heuristics to this problem. The heuristics were specially conceived to handle large instances that occur in conservation biology. The heuristics are compared using both simulated and real data for the Iberian Peninsula. Since the node weighted Steiner forest problem is a special case of the problem studied, the proposed heuristics are also compared to a well established heuristic for this case. The dissertation resulted in the development of an open source application that was made available to the scientific community.
Descrição: Doutoramento em Matemática Aplicada à Economia e à Gestão
URI: http://hdl.handle.net/10400.5/6124
Aparece nas colecções:BISEG - Teses de Doutoramento / Ph.D. Thesis
DM - Teses de Doutoramento / Ph.D. Thesis

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
TD-RMB-2013.pdf855,37 kBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.