A carregar...
Publicação
Uma variante do problema da floresta de Steiner em grafos com aplicações em biologia da conservação
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 855.37 KB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
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.
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
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
Contexto Educativo
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.
Editora
Instituto Superior de Economia e Gestão