[pt] Essa dissertação explora o problema roteamento de linhas de transmissão (LT) através da solução do caminho mais curto em um grafo sem ciclos de melhoria, considerando custos quadráticos para arcos adjacentes. Esse problema é conhecido como o Problema do Caminho Mínimo Quadrático
Adjacente (CMQA). Esse trabalho apresenta uma descrição teórica do CMQA, propõe uma extensão do algoritmo Dijkstra (aqDijkstra) para solução de CMQA em tempo polinomial e discute como o algoritimo pode ser utilizado em metodologias de roteamento de LT. Em seguida, apresentamos uma melhoria estendendo o algoritmo A estrela para sua forma adjacente quadrática (aqA estrela), incluindo uma etapa de busca reversa para estimação de custos de chegada. Foram feitos experimentos computacionais contemplando a variação de custos quadráticos, geração de instâncias aleatórias, testes de estresse e comparação com abordagens já utilizadas na literatura. Os resultados sugerem que: (i) aqA estrela teve o melhor desempenho, atingindo tempos de busca 40 vezes mais rápidos que aqDijkstra e 50 vezes mais rápido que a abordagem mais rápida apresentada pela literatura; (ii) a eficiência dos algoritmos não foi afetada pela variação dos custos quadráticos; (iii) os algoritmos propostos aqA estrela e aqDijkstra também foram mais eficientes nas instancias aleatórias, reafirmando a superioridade dos mesmos. Duas aplicações
são apresentadas, uma de objetivo ilustrativo e outra para um caso real. O algoritimo aqA estrela foi usado para solução de um CMQA em um grafo de quase um bilhão de arcos quadraticos, resultado em uma rota proposta com custos adicionais três vezes menor. / [en] 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.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:57045 |
| Date | 13 January 2022 |
| Creators | JOAO MARCOS DUSI VILELA |
| Contributors | BRUNO FANZERES DOS SANTOS, BRUNO FANZERES DOS SANTOS, BRUNO FANZERES DOS SANTOS, BRUNO FANZERES DOS SANTOS, BRUNO FANZERES DOS SANTOS |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | English |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0025 seconds