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.
|