Título
[pt] O PROBLEMA MULTI-PERÍODO DA ÁRVORE DE STEINER COM COLETAS DE PRÊMIOS E RESTRIÇÕES DE ORÇAMENTO
Título
[en] THE MULTI-PERIOD PRIZE-COLLECTING STEINER TREE PROBLEM WITH BUDGET CONSTRAINTS
Autor
[pt] LARISSA FIGUEIREDO TERRA DE FARIA
Vocabulário
[pt] BRANCH-AND-CUT
Vocabulário
[pt] DESENHO DE REDE
Vocabulário
[pt] MULTI-PERIODO
Vocabulário
[pt] ARVORE DE STEINER COM COLETA DE PREMIOS
Vocabulário
[en] BRANCH-AND-CUT
Vocabulário
[en] NETWORK DESIGN
Vocabulário
[en] MULTI-PERIOD
Vocabulário
[en] PRIZE-COLLECTING STEINER TREE
Resumo
[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.
Resumo
[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.
Orientador(es)
HELIO CORTES VIEIRA LOPES
Coorientador(es)
DAVID SOTELO PINHEIRO DA SILVA
Banca
HELIO CORTES VIEIRA LOPES
Banca
MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO
Banca
EDUARDO UCHOA BARBOZA
Banca
RAFAEL MARTINELLI PINTO
Banca
DAVID SOTELO PINHEIRO DA SILVA
Banca
LUIZ CARLOS FERREIRA DE SOUSA
Catalogação
2021-01-26
Apresentação
2019-04-05
Tipo
[pt] TEXTO
Formato
application/pdf
Idioma(s)
INGLÊS
Referência [pt]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=51356@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=51356@2
Referência DOI
https://doi.org/10.17771/PUCRio.acad.51356
Arquivos do conteúdo
NA ÍNTEGRA PDF