Home   |   Structure   |   Research   |   Resources   |   Members   |   Training   |   Activities   |   Contact

EN | PT

BrBRCEEn0101-74382003000100015

BrBRCEEn0101-74382003000100015

National varietyBr
Country of publicationBR
SchoolEx-Tech-Multi Sciences
Great areaEngineering
ISSN0101-7438
Year2003
Issue0001
Article number00015

Javascript seems to be turned off, or there was a communication error. Turn on Javascript for more display options.

Aplicação de métodos de busca em grafos com nós parcialmente ordenados à locação de torres de tranmissão

1. Introdução Este artigo apresenta algoritmos para otimização da locação de torres de transmissão e baseia-se numa modelagem inovadora do problema de locação de torres como um problema de decisões seqüenciais com a construção recorrente de um grafo através da aplicação repetida de um operador sucessor. O trabalho introduz um processo de eliminação de caminhos no grafo baseado em relações de preferência entre nós que não havia sido utilizado anteriormente para resolver este tipo de problema e que resulta em aumento de eficiência na determinação de uma linha de transmissão de custo mínimo. O objetivo do trabalho é apresentar uma modelagem original para o problema de locação de torres de transmissão que apresenta melhorias sobre algoritmos consagrados por incorporar a estes relações de preferência entre nós. Acreditamos que esta forma de modelagem tem amplas aplicações em outros tipos de problemas.

Nesta seção introdutória é feita uma descrição do problema bem como um levantamento da literatura de otimização da locação de torres de transmissão. A segunda seção apresenta resultados básicos sobre algoritmos de busca de caminhos de custo mínimo através de um grafo ordenado. A terceira seção apresenta a modelagem sugerida oferecendo definições do grafo e seus componentes ' os nós, os arcos, os custos, os caminhos e um operador sucessor.

A quarta seção apresenta o detalhamento da aplicação dos algoritmos apresentados anteriormente ao problema de locação.

Descrição do problema.O projeto de uma linha de transmissão compreende diversas etapas: especificação das características elétricas da linha, escolha do traçado, determinação de características mecânicas das torres, levantamento topográfico e, finalmente, a locação das torres de transmissão sobre o traçado escolhido. Da etapa de determinação de características mecânicas das torres resulta a definição dos tipos de torres que serão utilizadas na linha. Resulta também desta etapa a especificação detalhada de todos os limites mecânicos que cada tipo de torre pode suportar, as diversas alturas disponíveis para cada tipo de torre e o custo de cada par (tipo, altura) de torre. As restrições mecânicas são numerosas e incluem esforço transversal máximo, esforço vertical mínimo para os cabos de transmissão e para os cabos pára-raios, trações longitudinais e transversais para cadeias em torres de suspensão bem como outras restrições particulares a torres de ancoragem e de suspensão. Os custos de cada torre dependem apenas de seu tipo e altura.

A etapa seguinte é a especificação das restrições topográficas com o completo levantamento do perfil do terreno ao longo do traçado da linha. As restrições topográficas incluem a altura de segurança do cabo (altura mínima do cabo ao solo), a topografia do terreno, trechos de locação proibida (como, por exemplo, rios e estradas a serem cruzados pela linha) e pontos de locação obrigatória. O cabo suspenso entre duas torres toma o formato de uma catenária, que neste trabalho (e normalmente) é aproximada por uma parábola. Ela deve necessariamente superar uma distância mínima do solo em todos os pontos do perfil topográfico (a altura de segurança). A catenária de segurança é a catenária virtual que tangencia o perfil topográfico, partindo do ponto na torre que representa sua altura decrescida da altura de segurança naquele ponto do traçado. Neste trabalho, o termo catenária é utilizado para significar catenárias de segurança, as ilustrações mostram torres com catenárias de segurança e as torres têm suas alturas decrescidas da altura de segurança. Ao final desta etapa são conhecidas as restrições mecânicas e as restrições topográficas para o problema e têm-se todos os dados para iniciar o processo de otimização ' os tipos e alturas (e conseqüentemente custos) das torres de transmissão, bem como a descrição completa do perfil topográfico do terreno.

Os esforços mecânicos a que está submetida uma torre somente são determinados quando são conhecidas as localizações e alturas das duas torres adjacentes a ela, ou seja, o tipo e conseqüentemente o custo de uma torre depende de sua localização e também da localização e altura da torre que a precede e da torre que a segue no traçado. Conseqüentemente o procedimento de locação de torres passa pelo exame de trechos de perfil topográfico imediatamente à frente da última torre locada para identificar a melhor opção para a locação da próxima torre e determinar o tipo e o custo da torre anterior. Como será descrito abaixo, modelamos este problema através da utilização de um grafo que incorpora todas as opções possíveis de locação para a linha. Este grafo é criado recursivamente através de um operador sucessor aplicado de forma seqüencial às torres que compõem o extremo de linha de transmissão mais promissor a cada momento. Após um breve resumo da literatura será descrita a modelagem bem como os algoritmos para solução do problema.

Resumo da literatura.A referência mais antiga mencionando uma tentativa de elaboração de um algoritmo para otimização de torres de transmissão foi um modelo simples utilizando otimização local, com uma pesquisa exaustiva de opções de locação no trecho imediatamente à frente da última torre locada (enfoque sliding window). Este processo não fornecia um resultado ótimo pois em cada ponto o horizonte de pesquisa se limitava a examinar as opções para um grupo de três torres subseqüentes ' ver Bob, Dabekis & Fullerton (1963).

A primeira modelagem de otimização utilizando teoria de grafos considerava um horizonte maior à frente de cada torre ou a ser expandido, podendo este horizonte chegar a dez torres. Esta modelagem utilizou algoritmos de otimização em grafos, inclusive o algoritmo A*, com mecanismos de análise estatística dos pontos do perfil à frente da torre mais recentemente locada (função look ahead) para permitir o exame de um número diferente de torres em casos de perfil muito ou pouco acidentado ' ver Neiva de Figueiredo (1978) e Neiva de Figueiredo, Gonzaga & Maculan (1979).

Mais recentemente outras abordagens foram tentadas utilizando variações do enfoque sliding window com horizonte limitado ' ver, por exemplo, Çalis (1992).

pelo menos um exemplo de aplicação de programação dinâmica ao problema de otimização na locação de torres de transmissão ' ver Cherdsant (1997). Esta aplicação também padece das limitações do enfoque sliding window pois examina apenas três torres de cada vez identificando ótimos locais sem examinar o traçado inteiro e conseqüentemente não encontrando um ótimo global.

Além das referências citadas acima não foi encontrada nenhuma citação na literatura que utilizasse algoritmos de busca em grafos para a modelagem e otimização de locação de torres de transmissão. Ademais, não foi encontrada na literatura nenhuma referência além daquelas citadas acima que utilizasse algoritmos seqüenciais de otimização para modelagem e minimização do custo de locação de torres de transmissão examinando o perfil topográfico em sua totalidade.

2. Algoritmos de busca em grafos O problema de locação será formulado como um problema de busca de caminho de custo mínimo através de um grafo ordenado. Nesta seção apresentamos resultados básicos sobre grafos e algoritmos de busca. Para uma descrição mais detalhada, veja Gonzaga (1978), Hart, Nilsson & Raphael (1968) e Nilsson (1971).

Um grafo é caracterizado por um conjunto de nós N = {n1, n2,...} e um conjunto de arcos, que são pares ordenados (ni,nj) de nós. A cada arco é associado um custo c (ni,nj) > 0. Um caminho é uma seqüência de nós hi=(nl1,nl2, nl3,...) ligados dois a dois por arcos, e seu custo é a soma dos custos desses arcos.

Dado um inicial s Î N e um conjunto alvo T Î N, busca-se entre todos os caminhos que unem s a algum de T, um que tenha custo mínimo.

Nos algoritmos de que trataremos aqui, os conjuntos de nós e arcos não são conhecidos a priori: tem-se um operador sucessor G, que associa a cada n o conjunto de nós G(n) (sucessores de n) tais que nj Î G(n)se e se (n,nj) é um arco. A definição de G para nosso problema ficará clara na próxima seção. O grafo pode ser construído recursivamente a partir de s por aplicações sucessivas do operador G. Isto será feito por algoritmos de busca.

Um algoritmo de busca trivial é o seguinte: liste todos os caminhos possíveis a partir de s e escolha entre os que atingem T um de mínimo custo. Bons algoritmos constroem uma lista de caminhos a partir de s, mas somente guardam um caminho entre s e cada , o mais barato encontrado. Portanto, os algoritmos guardam listas de caminhos e cada iteração constrói novos caminhos através da expansão do terminal de algum caminho listado.

Elementos listados.Suponhamos que estão listados os caminhos hi=(nl1,nl2,..., nlk) e hi=(nl1,nl2,..., njk,njk+1), com ni1 = nj1,..., nik = njk isto é, hj é uma extensão de hi. Obviamente um desperdício de memória, podendo-se caracterizar hi por seu terminal e um apontador para hi, a parte inicial do caminho. Assim, os caminhos listados serão representados por triplas hi= (ni,ci,pi), onde hi é o terminal do caminho, ci é seu custo, e pi é um apontador para hpi. A construção completa do caminho hi, quando necessária, é feita por retroação (backtracking) na lista.

Cada iteração de um algoritmo escolhe um caminho listado e expande-o.

Guardaremos duas listas de caminhos: a lista de fechados, contendo os caminhos que foram expandidos e a lista de abertos, contendo os caminhos que ainda não geraram sucessores. Portanto, cada iteração escolhe um caminho aberto e expande-o. Cada critério diferente de escolha do caminho a ser expandido caracteriza um algoritmo de busca em grafos: busca horizontal (escolha do caminho mais antigo), busca em profundidade (escolha do caminho mais recente), algoritmo de Dijkstra (escolha do caminho mais barato) e algoritmo A* (escolha do caminho mais promissor). Estes dois últimos são discutidos adiante.

Vamos agora descrever um algoritmo típico.

Inicialização.Identifique elementos listados como triplas h = (n,c,p), como descrevemos acima. Crie uma lista abertose uma lista fechados, inicialmente vazias. Introduza em abertoso elemento h0 = (s,0,'), onde s é o inicial, o custo é nulo e o apontador é vazio.

Passo 1.Escolha um elemento em abertos, transfira <formula/> para fechados. Se Î T(alvo), termine.

Passo 2: expansão.Aplique o operador sucessor G ao [/img/revistas/pope/ v23n1/a15img03.gif], obtendo seus sucessores G ([/img/revistas/pope/v23n1/ a15img03.gif]) = {<formula/>1,...,[/img/revistas/ pope/v23n1/a15img03.gif]q}, e construa os caminhos sucessores [/img/revistas/ pope/v23n1/a15img04.gif], j = 1,...,q onde [/img/revistas/pope/v23n1/ a15img05.gif]1=...<formula/>q é um apontador para <formula/>.

Passo 3: eliminações.Compare cada sucessor [/img/revistas/pope/v23n1/ a15img02.gif]j com todos os elementos listados. Se existe algum elemento listado com o mesmo terminal <formula/> = ([/ img/revistas/pope/v23n1/a15img03.gif]j, [/img/revistas/pope/v23n1/ a15img07.gif], <formula/>), execute a seguinte eliminação: se <formula/> < [/img/revistas/pope/ v23n1/a15img09.gif]j, descarte <formula/>j; senão, se <formula/> está em abertos, descarte [/img/ revistas/pope/v23n1/a15img06.gif]. Observe que nunca se eliminam fechados.

Introduza em abertosos sucessores remanescentes e volte ao Passo 1.

Terminação.Um caminho ótimo foi determinado. Reconstrua-o percorrendo a lista fechadosutilizando os apontadores retroativamente.

Especificamos agora os algoritmos que serão usados neste trabalho.

Algoritmo de Dijkstra.escolhe-se no Passo 1 um elemento de custo mínimo entre os de abertos. Como resultado, mostra-se que os caminhos fechados [/img/ revistas/pope/v23n1/a15img02.gif] são sempre ótimos, isto é, de custo mínimo entre todos os caminhos de s a <formula/>. Quando um elemento do alvo é fechado, o problema está resolvido.

Algoritmo A*.em certos problemas, existem procedimentos que associam a cada n Î N uma subestimativa h(n) para o custo de um caminho ótimo entre n e o alvo T. Tipicamente, tais estimativas são obtidas pela resolução de um problema relaxado, obtido retirando restrições do problema original. O algoritmo A* escolhe no Passo 1 um elemento <formula/> com mínimo valor de cj + h (nj) entre todos os abertos hj. Assim sendo, a comparação de custos no passo 1 passa a ser de uma subestimativa do custo total de uma linha cujo trecho inicial é o associado a cada hj listado ou sucessor.

Também neste caso, mostra-se que os caminhos fechados são sempre ótimos, e que o problema é resolvido ao fechar-se um elemento do alvo.

Relações de preferência.Em certos problemas é possível comparar nós com respeito à proximidade em relação ao alvo. Isto é, mesmo não se conhecendo estimativas como acima, pode haver uma ordenação parcial [/img/revistas/pope/ v23n1/a15img10.gif] (uma relação de preferência) entre nós do grafo. As relações de preferência entre nós melhoram a eficiência dos algoritmos de otimização em grafos sem comprometer a otimalidade, conforme demonstrado em Gonzaga (1973). Essas relações tem significado descrito a seguir: Dados dois nós n1e n2, eles podem ou não ser comparáveis. Se forem comparáveis, deve-se ter: Se n1<formula/> n2, então um caminho de custo mínimo entre n1 e T tem custo menor ou igual que qualquer caminho entre n2 e T.

Isto é, n1 está mais "próximo" de T do que n2. É claro que sempre se tem n <formula/> n.

O critério de eliminações no Passo 3 passa a ser o seguinte: compare [/img/ revistas/pope/v23n1/a15img02.gif] com cada elemento listado [/img/revistas/ pope/v23n1/a15img06.gif] = (<formula/>, [/img/ revistas/pope/v23n1/a15img07.gif],<formula/>) e faça: Se <formula/> < [/img/revistas/pope/v23n1/ a15img09.gif]j e <formula/> [/img/revistas/pope/ v23n1/a15img10.gif] <formula/>j, descarte [/img/ revistas/pope/v23n1/a15img03.gif]j.

Senão, se <formula/> está em abertos, [/img/ revistas/pope/v23n1/a15img09.gif]j < <formula/> e <formula/>j [/img/revistas/pope/v23n1/ a15img10.gif] <formula/>, elimine [/img/revistas/ pope/v23n1/a15img11.gif] da lista (nunca se eliminam caminhos fechados).

É fácil mostrar que um caminho ótimo nunca é eliminado por um não ótimo: suponha que um caminho <formula/> elimina um caminho <formula/>. Para cada n Î T, seja [/img/ revistas/pope/v23n1/a15img12.gif](n,T) o custo de um caminho ótimo de n a T.

Sabe-se então que pela regra de eliminação, [/img/revistas/pope/v23n1/ a15img09.gif] < <formula/>, e devido a [/img/ revistas/pope/v23n1/a15img03.gif] <formula/> [/ img/revistas/pope/v23n1/a15img11.gif], <formula/>( <formula/>, T) < [/img/revistas/pope/v23n1/ a15img12.gif] (<formula/>,T). O custo de um caminho ótimo iniciando por <formula/> é menor ou igual a <formula/> + [/img/revistas/pope/v23n1/ a15img12.gif] (<formula/>,T) < [/img/revistas/ pope/v23n1/a15img07.gif] + <formula/> ([/img/ revistas/pope/v23n1/a15img11.gif],T), e portanto o caminho [/img/revistas/pope/ v23n1/a15img06.gif] pode ser ignorado.

Regras de preferência desse tipo são comuns em problemas de decisões seqüenciais. Por exemplo, no planejamento da operação de sistemas hidroelétricos em que um representa o estado dos reservatórios, um elimina outro quando o primeiro corresponde a reservatórios mais cheios e as demais variáveis associadas a cada um desses nós são equivalentes. No planejamento da expansão de redes com capacidades nos arcos, uma rede (que é um do problema de planejamento) elimina outra se tiver mais capacidade instalada em todos os arcos.

A arborescência ótima.É interessante notar que um algoritmo de grafos como os que descrevemos mantém na lista fechadosapenas um caminho (ótimo) de s até cada . Isto caracteriza uma arborescência ótima do grafo. Quando o algoritmo termina, encontrou-se não somente um caminho ótimo até o alvo, mas também caminhos ótimos até todos os nós terminais de caminhos em fechados. A este mecanismo chama-se imersão invariante.

3. Modelagem do problema Enunciado.O problema de otimização da locação de torres de transmissão consiste em determinar uma linha de transmissão de custo mínimo satisfazendo restrições eletro-mecânicas e topográficas de um traçado pré-escolhido para a linha. Dado este traçado, cada ponto do perfil topográfico é expresso por sua ordenada e abscissa e são definidos os obstáculos, os trechos de locação proibida, os pontos de locação obrigatória, e as alturas de segurança em cada ponto do perfil. É também dado do problema um conjunto de tipos de torres com características estruturais diferentes e alturas discretas predeterminadas. As diversas restrições mecânicas definem limites de utilização para uma torre de determinado tipo. As restrições mais importantes são a de esforço transversal máximo (expressa pelo vão médio máximo que um tipo de torre suporta) e esforço vertical máximo e mínimo (expressa pelo vão gravante máximo e mínimo este somente no caso de torres de suspensão que um tipo de torre suporta). Estas e todas as outras restrições eletromecânicas (tais como ângulo máximo, balanço de cadeias, etc.) são pré-definidas para cada tipo de torre. Dado um par (tipo, altura) de uma torre, é conhecido o custo desta torre.

O problema de otimização na locação de torres de transmissão é um problema de minimização de custos em uma infinidade de possibilidades de locações. Este problema é aqui modelado como um problema de busca de caminhos de custo mínimo em grafos. O que segue é o enunciado da modelagem do problema com a caracterização do grafo através da definição de seus nós, arcos, caminhos e custos. O primeiro passo é a definição de um .

Nó.Um ni do grafo é determinado por uma torre completamente conhecida seguida de outra torre com locação e altura conhecidos mas de tipo ainda indeterminado.

Um ni é caracterizado pela quíntupla:

onde xj é a abscissa onde está localizada a torre j, hj é a altura da torre j, Tj é o tipo da torre j(ver Figura_1). Um cuja segunda torre está no fim do perfil topográfico é um alvo.

Arco.Um arco é um par ordenado de nós com uma torre coincidente. Mais especificamente, um arco compreende dois nós, o primeiro dos quais tem uma torre de tipo conhecido e uma torre de tipo não conhecido (ver Figura_2). No segundo deste arco a torre que não tinha seu tipo conhecido no anterior tem seu tipo determinado. Estas três torres têm satisfeitas todas as restrições topográficas e mecânicas a que estão sujeitas.

Custo.O custo associado ao arco (ni,nj) é o custo da torre intermediária deste arco, cujo tipo é agora conhecido (o custo da segunda torre do nj e da primeira torre do nj).

Caminho.Um caminho é uma seqüência ordenada de nós ligados por arcos à qual se associa uma seqüência de torres que satisfazem a todas as restrições topográficas e mecânicas para o trecho (ver Figura_2). A última torre de um caminho não tem seu tipo conhecido a não ser que seja a torre final do trecho sendo otimizado. Dentre os caminhos que cobrem a totalidade do perfil topográfico, um caminho de custo mínimo é uma solução ótima para o problema de locação.

Operador sucessorG.Os sucessores de um [/img/revistas/pope/v23n1/ a15img14.gif]são nós <formula/>com [/img/revistas/ pope/v23n1/a15img16.gif]. Eles são obtidos por todas as possíveis adições de uma nova torre tal que qualquer aumento na abscissa desta nova torre violaria alguma restrição (ver Figura_3).

Obtém-se esta condição em dois passos. Primeiro lança-se a partir da torre cujo tipo não foi ainda definido (a segunda torre do [/img/revistas/pope/v23n1/ a15img03.gif], de abscissa <formula/> e altura [/ img/revistas/pope/v23n1/a15img18.gif]) a catenária que tangencia o perfil topográfico. A catenária tangente de uma torre é obtida minimizando o eixo da aproximação parabólica da catenária, dado por

para (x,y) no perfil do terreno, com x > xt.

Nesta equação (xt,yt) e ht são a abscissa, ordenada e altura da torre t, hs é a altura da catenária de segurança na torre t (altura de segurança), W é o peso por metro do cabo condutor e L é a tração longitudinal do cabo. O segundo passo consiste em locar nesta catenária as torres de alturas disponíveis tomando por base as informações do perfil topográfico. Com a determinação de cada possível locação para a torre seguinte estão determinados os possíveis tipos da torre anterior (que é a primeira torre dos nós sucessores) e conseqüentemente seus custos.

O operador sucessor gera locações para a próxima torre ajustando todas as alturas de torres disponíveis à catenária tangente. Existirão situações em que, por limites de esforço mecânico na torre anterior, é necessário explorar opções em que a torre seguinte esteja localizada na abscissa mais distante possível da torre anterior tal que esta ainda seja de um tipo mais leve, e conseqüentemente, de custo mais baixo. Nestes casos, que somente excepcionalmente farão parte do caminho de custo mínimo, a catenária não será tangente ao solo.

Grafo.A aplicação do operador sucessor acima descrito permite a criação de sucessores de qualquer criado. O grafo é construído iterativamente à medida que nós são expandidos por aplicações sucessivas do operador sucessor G, como descrito na seção anterior.

4. Algoritmos e relações de preferência entre nós Nesta seção, fazemos uma breve discussão dos algoritmos, descrevendo as subestimativas utilizadas pelo algoritmo A* e as relações de preferência entre nós.

O algoritmo de Dijkstra.O algoritmo de Dijkstra pode ser aplicado diretamente ao problema. Devido ao fato de o problema ser de natureza contínua, dificilmente dois caminhos terão o mesmo terminal. Conseqüentemente haverá poucas eliminações de caminhos, e as listas podem crescer explosivamente. Mesmo com a utilização de tolerâncias para comparações entre nós, o número de eliminações pode ser insuficiente. O melhor método para reduzir as listas consiste na utilização de uma relação de preferência entre nós, descrita abaixo.

O algoritmo A*.O algoritmo A*, que reduz o número de expansões feitas por Dijkstra, depende de uma subestimativa para o custo de uma linha de transmissão entre um dado e o fim do perfil topográfico. Esta subestimativa pode ser facilmente obtida através do cálculo do custo de uma linha remanescente que tenha mesmo comprimento em um "perfil topográfico perfeito" com ondulações acompanhando as catenárias entre as torres.

Relações de preferência entre nós.Aqui este trabalho introduz uma relação de preferência entre nós que permite detectar certas situações em que um está "mais perto" do objetivo do que outro . A relação de preferência permite a melhoria dos algoritmos de Dijkstra e A* no Passo 3, permitindo-se que sejam eliminados da lista de caminhos abertos todos os elementos cujos nós sejam iguais ou piores que (ou seja, não preferíveis ao definição a seguir) o resultante da expansão com custo cj (ou custo total estimado cj + hj no caso do A*) maior que este . Conforme descrito formalmente na Seção 2, hi = (ni,ci,pi) elimina hj = (nj,cj,pj) se ni for preferível a nj e se cj > ci, ou seja, se hi tem o mesmo terminal e é mais barato ou de mesmo custo. Esta alteração permite uma redução substancial na lista de nós abertos e conseqüentemente um aumento significativo na eficiência no processo.

Definição:Considere duas quíntuplas <formula/> e <formula/>, identificando respectivamente os nós ni e <formula/>. Considere ainda as abscissas ei e <formula/> dos eixos das catenárias lançadas a partir da segunda torre desses nós.

ni (o <formula/> é preferível ao ni) se:

A condição (1) significa que a abscissa da primeira torre do [/img/revistas/ pope/v23n1/a15img22.gif] (que tem seu tipo conhecido) é maior ou igual que a abscissa da primeira torre do ni (que também tem seu tipo conhecido), ou seja, esta torre não está mais perto do final do traçado do que aquela.

A condição (2) significa que a abscissa da segunda torre do [/img/revistas/ pope/v23n1/a15img22.gif] (que ainda não tem seu tipo conhecido) é maior ou igual que a abscissa da segunda torre do ni (que também ainda não tem seu tipo conhecido), ou seja, esta torre não está mais perto do final do traçado que aquela.

A condição (3) significa que a segunda torre do [/img/revistas/pope/v23n1/ a15img22.gif] (que ainda não tem seu tipo conhecido) é menor ou igual que a segunda torre do ni (que também ainda não tem seu tipo conhecido), ou seja, a altura da segunda torre do ni não é menor que a altura da segunda torre do <formula/>.

A condição (4) significa que a abscissa do eixo da catenária traçada a partir da segunda torre do <formula/> é maior ou igual que a abscissa do eixo da catenária traçada a partir da segunda torre do ni ou seja, o eixo da catenária desta torre não está mais perto do final do traçado que o eixo daquela (ver Figura_4).

Quando as condições (1), (2) e (4) acima são satisfeitas simultaneamente, segue que o <formula/> está mais avançado no perfil que o ni. A condição (3) garante que se as segundas torres de ambos os nós receberem a mesma atribuição de tipo, a torre do [/img/revistas/pope/v23n1/ a15img22.gif] não será mais cara que a do ni.

Justificativa da relação de preferência.A relação de preferência será utilizada para eliminar caminhos listados ou gerados: informalmente, um caminho elimina outro quando seu custo é inferior e seu terminal é melhor. A afirmação a seguir mostra que a relação de preferência proposta está bem definida.

Afirmação. Dados dois nós <formula/> e ni, se [/ img/revistas/pope/v23n1/a15img22.gif] <formula/> ni, então o custo de uma locação ótima de torres a partir de [/img/revistas/ pope/v23n1/a15img22.gif] é menor ou igual que o custo de qualquer locação de torres a partir de ni.

Demonstração:Considere dois nós <formula/> e [/ img/revistas/pope/v23n1/a15img25.gif] e suponha que [/img/revistas/pope/v23n1/ a15img22.gif] é preferível a ni.

Considere uma locação de torres a partir da segunda torre de ni até o alvo.

Demonstra-se aqui que esta mesma locação poderá ser feita a partir da segunda torre de <formula/> com custo igual ou menor.

Basta examinar a primeira torre após <formula/> na locação considerada e seja <formula/> sua abscissa. Como <formula/> > ei, a catenária com eixo <formula/> passa por baixo da catenária com eixo ei após o ponto de tangência desta com o solo. Isto implica diretamente que a primeira torre do perfil remanescente a partir de [/img/revistas/pope/ v23n1/a15img28.gif] pode ser locada no mesmo ponto [/img/revistas/pope/v23n1/ a15img27.gif], possivelmente com folga na catenária.

O custo da linha remanescente até o alvo é o mesmo nos dois casos por construção. Falta somente demonstrar que o custo da segunda torre do ni é maior ou igual que o custo da segunda torre do [/img/revistas/pope/v23n1/ a15img22.gif]. Das relações (1), (2), e (4) segue imediatamente que o vão médio e o vão gravante da segunda torre de <formula/> são menores ou iguais que os respectivos vãos da segunda torre de ni. Portanto o mesmo tipo de torre é aceitável nos dois casos. Como [/img/revistas/pope/ v23n1/a15img29.gif] < <formula/>, o custo da segunda torre do <formula/> é menor ou igual que o custo da segunda torre do ni, completando a demonstração.

Esta relação de preferência pode ser facilmente incorporada ao processo de eliminação de elementos da lista de caminhos abertos ou de elementos sucessores recém-gerados nos algoritmos de otimização descritos anteriormente. Em cada comparação de custo entre elementos de nós iguais ao gerado pelo operador sucessor na lista de caminhos abertos, basta comparar o custo para todos os elementos cujos nós sejam iguais ou melhores que nós de elementos da lista.

Este procedimento melhora os algoritmos de busca por reduzir o tamanho das listas de caminhos abertos sem perda de eficiência na determinação do caminho de custo mínimo.

5. Conclusão Este trabalho apresentou um algoritmo para otimização de locação de torres de transmissão que propõe a otimização global de todo o traçado e utiliza algoritmos eficientes de busca em grafos, com a incorporação de uma relação de preferência entre nós além de comparações de custo. Este procedimento resulta em um aumento de eficiência na determinação de uma linha de transmissão de custo mínimo. A modelagem em teoria de grafos utilizada foi detalhada, foram descritos os algoritmos que se beneficiam da incorporação de relações de preferências entre nós, e foi descrita a relação de preferência entre nós com demonstração de sua validade.


Download text