[pt] O PROBLEMA MULTI-PERÍODO DA ÁRVORE DE STEINER COM COLETAS DE PRÊMIOS E RESTRIÇÕES DE ORÇAMENTO

Detalhes bibliográficos
Ano de defesa: 2021
Autor(a) principal: LARISSA FIGUEIREDO TERRA DE FARIA
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: eng
Instituição de defesa: MAXWELL
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=51356&idi=1
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=51356&idi=2
http://doi.org/10.17771/PUCRio.acad.51356
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.