ETDs @PUC-Rio
| Título: | O PROBLEMA MULTI-PERÍODO DA ÁRVORE DE STEINER COM COLETAS DE PRÊMIOS E RESTRIÇÕES DE ORÇAMENTO | ||||||||||||
| Autor: |
LARISSA FIGUEIREDO TERRA DE FARIA |
||||||||||||
| Colaborador(es): |
HELIO CORTES VIEIRA LOPES - Orientador DAVID SOTELO PINHEIRO DA SILVA - Coorientador |
||||||||||||
| Catalogação: | 26/JAN/2021 | Língua(s): | INGLÊS - ESTADOS UNIDOS |
||||||||||
| Tipo: | TEXTO | Subtipo: | TESE | ||||||||||
| Notas: |
[pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio. [en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio. |
||||||||||||
| Referência(s): |
[pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=51356&idi=1 [en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=51356&idi=2 |
||||||||||||
| DOI: | https://doi.org/10.17771/PUCRio.acad.51356 | ||||||||||||
| Resumo: | |||||||||||||
|
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.
|
|||||||||||||
|
|||||||||||||