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 nó 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).
Há 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 nó inicial s Î N e um conjunto alvo T Î N, busca-se entre todos os
caminhos que unem s a algum nó 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ó n o
conjunto de nós G(n) (sucessores de n) tais que nj Î G(n)se e só 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 nó, 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 nó 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 há um desperdício de memória, podendo-se
caracterizar hi por seu nó 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 nó 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 já 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 nó 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 nó [/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 nó 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 Î 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 nó representa o estado dos reservatórios, um nó
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
nó 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
nó. 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ó.
Nó.Um nó 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 nó 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 nó cuja segunda torre está no fim do
perfil topográfico é um nó 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 nó deste arco a torre que não tinha seu tipo conhecido no nó anterior
já 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 nó nj e da
primeira torre do nó 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 nó [/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 nó [/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 nó já 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 nó 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 nó 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 nó está
"mais perto" do objetivo do que outro nó. 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
nó resultante da expansão com custo cj (ou custo total estimado cj + hj no caso
do A*) maior que este nó. 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 nó 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 nó <formula/> é preferível ao nó ni) se:
A condição (1) significa que a abscissa da primeira torre do nó [/img/revistas/
pope/v23n1/a15img22.gif] (que já tem seu tipo conhecido) é maior ou igual que a
abscissa da primeira torre do nó ni (que também já 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 nó [/img/revistas/
pope/v23n1/a15img22.gif] (que ainda não tem seu tipo conhecido) é maior ou
igual que a abscissa da segunda torre do nó 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 nó [/img/revistas/pope/v23n1/
a15img22.gif] (que ainda não tem seu tipo conhecido) é menor ou igual que a
segunda torre do nó ni (que também ainda não tem seu tipo conhecido), ou seja,
a altura da segunda torre do nó ni não é menor que a altura da segunda torre do
nó <formula/>.
A condição (4) significa que a abscissa do eixo da catenária traçada a partir
da segunda torre do nó <formula/> é maior ou igual
que a abscissa do eixo da catenária traçada a partir da segunda torre do nó 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 nó <formula/> está mais avançado no perfil
que o nó 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 nó [/img/revistas/pope/v23n1/
a15img22.gif] não será mais cara que a do nó 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 nó 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 nó 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 nó ni é
maior ou igual que o custo da segunda torre do nó [/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 nó <formula/> é menor ou igual
que o custo da segunda torre do nó 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.
