[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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:51356 |
| Date | 26 January 2021 |
| Creators | LARISSA FIGUEIREDO TERRA DE FARIA |
| Contributors | HELIO CORTES VIEIRA LOPES |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.002 seconds