Título
[en] ADJACENT QUADRATIC SHORTEST PATH PROBLEM: AN APPROACH FOR ELECTRIC TRANSMISSION LINE ROUTE OPTIMIZATION
Título
[pt] O PROBLEMA DE CAMINHO MAIS CURTO QUADRÁTICO ADJACENTE: UMA ABORDAGEM PARA OTIMIZAÇÃO DE ROTAS DE LINHAS DE TRANSMISSÃO
Autor
[pt] JOAO MARCOS DUSI VILELA
Vocabulário
[pt] SISTEMAS DE INFORMACAO GEOGRAFICA
Vocabulário
[pt] ROTEAMENTO DE LINHAS DE TRANSMISSAO
Vocabulário
[pt] CUSTO QUADRATICO
Vocabulário
[pt] PROBLEMA DE CAMINHO MAIS CURTO
Vocabulário
[pt] TEORIA DE GRAFOS
Vocabulário
[en] GEOGRAPHICAL INFORMATION SYSTEMS
Vocabulário
[en] TRANSMISSION LINE ROUTING
Vocabulário
[en] QUADRATIC COST
Vocabulário
[en] SHORTEST PATH PROBLEM
Vocabulário
[en] GRAPH THEORY
Resumo
[pt] Exploramos neste trabalho o problema de encontrar o caminho mais curto em um grafo, considerando custos quadráticos de arcos adjacentes, no contexto de otimização de rotas de linhas de transmissão. Nós fornecemos descrição teórica do problema de Caminho mais Curto Quadrático Adjacente e uma adaptação do algoritmo de Dijkstra (aqDijkstra) para solução do mesmo em grafos sem ciclo de melhoria. Além disso, estudamos o uso de regras de dominância como um recurso para melhorar a performance. Experimentos computacionais são feitos para estudar a performance dos algoritmos em comparação com outras abordagens da literatura. Por fim, fornecemos uma aplicação real de um projeto de linha de transmissão previsto para ser construído no Brasil.
Resumo
[en] We explore in this work the problem of finding the shortest path in a direct graph considering quadratic costs for adjacent edges (AQSPP) in the context of calculating optimal routes for transmission line projects. We provide theorical description for AQSPP and an adaptation of Dijkstra s algorithm (aqDijkstra) that handles adjacent quadratic weights, for graphs with no improving cycle, as an approach for solving AQSPP. Furthermore, we study the use of dominance rules as a resource for improving performance. Computational experiments are made to study algorithm s performance in comparison to other approaches. Finally, we provide a real case study for a transmission line project expected to be built in Brazil.
Orientador(es)
BRUNO FANZERES DOS SANTOS
Coorientador(es)
RAFAEL MARTINELLI PINTO
Catalogação
2021-05-20
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=52810@1
Referência [en]
https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=52810@2
Referência DOI
https://doi.org/10.17771/PUCRio.SeminarPPGEP.52810
Arquivos do conteúdo
NA ÍNTEGRA PDF