1 |
[pt] O PROBLEMA MULTI-PERÍODO DA ÁRVORE DE STEINER COM COLETAS DE PRÊMIOS E RESTRIÇÕES DE ORÇAMENTO / [en] THE MULTI-PERIOD PRIZE-COLLECTING STEINER TREE PROBLEM WITH BUDGET CONSTRAINTSLARISSA FIGUEIREDO TERRA DE FARIA 26 January 2021 (has links)
[pt] Esta tese generaliza a variante multi-período do clássico problema da
Árvore de Steiner com coleta de prêmios (PCST), que visa encontrar um
subgrafo conexo que maximize os prêmios recuperados de nós conectados
menos o custo de utilização das arestas conectadas. Este trabalho
adicionalmente: (a) permite que vértices sejam conectados à árvore em
diferentes períodos de tempo; (b) impõe um orçamento pré-definido em
arestas selecionadas em um horizonte específico de períodos de tempo; e (c)
limita o comprimento total de arestas que podem ser adicionadas em um
período de tempo. Um algoritmo branch-and-cut é fornecido para este
problema, avaliando satisfatoriamente instâncias benchmark da literatura,
adaptadas para uma configuração multi-período, de até aproximadamente
2000 vértices e 200 terminais em tempo razoável. / [en] This thesis generalizes the multi-period variant of the classical Prizecollecting
Steiner Tree Problem, which aims at finding a connected subgraph
that maximizes the revenues collected from connected nodes minus the costs
to utilize the connecting edges. This work additionally: (a) allows vertices
to be added to the tree at different time periods; (b) imposes a predefined
budget on edges selected over a specific horizon of time periods; and (c)
limits the total length of edges that can be added over a time period. A
branch-and-cut algorithm is provided for this problem, satisfactorily evaluating
benchmark instances from the literature, adapted to a multi-period setting, up
to approximately 2000 vertices and 200 terminals in reasonable time.
|
Page generated in 0.036 seconds