$$\newcommand{\bra}[1]{\left<#1\right|}\newcommand{\ket}[1]{\left|#1\right>}\newcommand{\bk}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}$$
INFORMAÇÕES SOBRE DIREITOS AUTORAIS


As obras disponibilizadas nesta Biblioteca Digital foram publicadas sob expressa autorização dos respectivos autores, em conformidade com a Lei 9610/98.

A consulta aos textos, permitida por seus respectivos autores, é livre, bem como a impressão de trechos ou de um exemplar completo exclusivamente para uso próprio. Não são permitidas a impressão e a reprodução de obras completas com qualquer outra finalidade que não o uso próprio de quem imprime.

A reprodução de pequenos trechos, na forma de citações em trabalhos de terceiros que não o próprio autor do texto consultado,é permitida, na medida justificada para a compreeensão da citação e mediante a informação, junto à citação, do nome do autor do texto original, bem como da fonte da pesquisa.

A violação de direitos autorais é passível de sanções civis e penais.
Coleção Digital

Avançada


Estatísticas | Formato DC|



Título: AN EFFICIENT ALGORITHM FOR THE ADJACENT QUADRATIC SHORTEST PATH PROBLEM WITH APPLICATION TO SMOOTH TRANSMISSION LINE ROUTING
Instituição: PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO - PUC-RIO
Autor(es): JOAO MARCOS DUSI VILELA

Colaborador(es):  BRUNO FANZERES DOS SANTOS - Orientador
RAFAEL MARTINELLI PINTO - Coorientador
Número do Conteúdo: 57045
Catalogação:  13/01/2022 Idioma(s):  ENGLISH - UNITED STATES

Tipo:  TEXT Subtipo:  THESIS
Natureza:  SCHOLARLY PUBLICATION
Nota:  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.
Referência [pt]:  https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=57045@1
Referência [en]:  https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=57045@2
Referência DOI:  https://doi.org/10.17771/PUCRio.acad.57045

Resumo:
This dissertation explores the problem of transmission line (TL) routing through finding the shortest path on an undirected graph with no improving cycles, considering quadratic costs for adjacent arcs. This problem is known as the Adjacent Quadratic Shortest Path Problem (AQSPP). This work provides the theoretical background for the AQSPP, proposes an extension of Dijkstra s algorithm (aqDijkstra) for solving AQSPP in polynomial-time and discusses how AQSPP can be included in routing methodologies. Furthermore, it is presented an improvement to the algorithm: the adjacent quadratic A star (aq A star) with a backward search for cost-togo estimation, to speed up search. For computational experiments, aqDijkstra and aqA star are benchmarked with other algorithms from the technical literature. The search behavior of the algorithms is also studied within different tests, including: quadratic cost variation, randomly generated graph instances and increasingly larger instances. The numerical results suggests that: (i) aqA star outperformed all the other algorithms, being 40 times faster than aqDijsktra and 50 times faster than the fastest benchmark algorithm; (ii) the studied algorithms do not lose efficiency as quadratic costs increase; (iii) aqA star and aqDijkstra were faster benchmark algorithms under random graph instances, indicating their robustness. Two applications are provided, one for illustrative purposes, and another to study performance on a real application. The aqA star algorithm solved an AQSSP on a graph with almost a billion quadratic arcs and provided a route with three times lower additional costs.

Descrição Arquivo
COMPLETE  PDF
Logo maxwell Agora você pode usar seu login do SAU no Maxwell!!
Fechar Janela



* Esqueceu a senha:
Senha SAU, clique aqui
Senha Maxwell, clique aqui