BrBRCEEn0101-74382002000100002

Uma heurística interativa para geração de caminhos em grafos com restrição de grau: aplicação ao projeto de sistemas metroviários

1. Introdução 1.1  O transporte metroviário O metrô tem se mostrado, em todo o mundo, como a melhor solução para o transporte de passageiros em grandes cidades, sendo comum a sua presença na maioria delas (Jane's, 1993), não só pela existência de corredores de alta demanda, mas também por oferecer um serviço potencialmente atrativo para usuários de outras modalidades, como ônibus e carro, retirando veículos das vias públicas. Nesse sentido, contribui para melhorar o desempenho do tráfego e minimizar suas externalidades, como os congestionamentos, acidentes de trânsito e degradação ambiental. Apenas as externalidades monetariamente quantificáveis e associadas aos congestionamentos derivados do excesso de veículos nas vias ultrapassam a casa de um bilhão de dólares/ano, segundo estudos realizados em diversas metrópoles americanas e européias (ICDT, 1995). Não contar com uma rede adequada deste serviço é condenar a cidade a conviver com sérios problemas no trânsito e com baixo nível de qualidade de vida, desordem e poluição, podendo chegar ao colapso. Esse colapso pode resultar, até, na fuga de empresas de grande porte para outros locais, na redução do fluxo de investimentos para a cidade, na retração do mercado de trabalho e na conseqüente perda da arrecadação de impostos pelo Poder Público (Metrô Rio, 2000). O sistema metroviário se caracteriza, exatamente, por ter uma grande capacidade de transporte, não ser poluente e utilizar energia renovável, sendo, em vista dessas características, indicado em corredores e áreas altamente adensadas e com elevadas demandas de viagens. Apesar da capacidade de um sistema metroviário depender de inúmeros fatores, tipicamente ela supera os 15.000 passageiros/hora/sentido, podendo este valor ultrapassar a casa dos 60.000 (Mello, 1978; TRB, 1995; Campos & Szasz, 1996; D'Agosto, 1999).

Em todo o mundo se contavam, em 1999, 108 sistemas de metrô, dos quais 11 na América do Sul, sendo 6 brasileiros (Belo Horizonte, Brasília, Porto Alegre, Recife, Rio de Janeiro e São Paulo). Neste trabalho se inclui um exemplo de aplicação da heurística aqui apresentada ao desenvolvimento de uma proposta de expansão do sistema metroviário do Rio de Janeiro.

No geral observa-se que o planejamento de redes de transportes, em particular metroviárias, tem como critério de análise potencializar o desenvolvimento do espaço sócio-econômico, atender a grandes contingentes de demanda e minimizar custos de implantação/operação e os impactos ambientais (Arruda, 1980; Ribeiro, 1980). O processo tradicional de modelagem usado é conhecido como "de quatro etapas" denominadas: geração de viagens, distribuição de viagens, escolha modal e alocação do tráfego. A sua aplicação envolve altos custos e uma quantidade extremamente elevada de dados, normalmente não disponíveis em países em desenvolvimento. Os programas computacionais existentes no mercado são habitualmente calibrados para outras realidades e têm uma concepção pouco interativa com os analistas e atores intervenientes.

Algumas pesquisas sobre este tema indicam uma preocupação maior com o desenho de redes alimentadas por ônibus e o emprego de técnicas de programação matemática de fluxo em redes, sistemas de informação geográfica e Inteligência Artificial (algoritmos genéticos), não tendo sido encontrada na literatura consultada abordagem similar à proposta deste artigo (Shih et al., 1998; Choi & Jang, 2000; Shrivastav & Dhingra, 2001; Bruno et al., 2002).

Os instrumentos e critérios adotados neste trabalho permitem uma visão preliminar da estrutura de rede, utilizando-se dados de obtenção mais simples e rápida. O projeto resultante poderá ser em seguida avaliado por técnicas mais elaboradas, etapa essa que, no entanto, não é contemplada aqui.

1.2  Características do problema Resolver um problema através de um modelo de grafo implica, com freqüência, em um esforço para suplantar dificuldades de caráter combinatório associadas às características do problema, especialmente quando se dispõe de um amplo universo de alternativas relacionadas entre si, em meio às quais se busca uma otimização ao menos aproximada.

O problema do projeto da rede metroviária tem outra natureza: essencialmente se trata de um problema de percursos, com uma restrição adicional (no entanto contornável) para o grau máximo dos vértices. Suas principais características são uma ordem em geral módica, envolvendo custos de projeto e de execução extremamente elevados e de execução seqüenciada no tempo. A construção de um sistema metroviário é uma atividade que ocorre ao longo de um período muito extenso, dirigida pelas necessidades da cidade e pelos seus planos de desenvolvimento. Freqüentemente se trabalha, em cada época, em uma linha apenas. O projeto é sujeito a diversos tipos de condicionantes relacionados à estrutura da rede, além dos fatores decisórios que levam à escolha de cada itinerário a ser efetivamente coberto, tais como dados de demanda, que figuram entre os elementos de mais fácil interação com o projetista. Destaca-se, entretanto, o cuidado com que se deve estudar o comportamento da demanda futura, particularmente no caso brasileiro, não só pelas significativas taxas de crescimento urbano das principais cidades, como por serem poucos, ou inexistentes em muitos casos, os instrumentos de controle de uso do solo, e conseqüentemente dos fluxos de viagens.

O grafo representativo de uma rede de metrô apresenta, em princípio, a restrição de grau máximo 4, associada à impossibilidade do cruzamento em nível de duas linhas. As opções para esse cruzamento são, habitualmente, a da construção de dois andares, ou então a da união das duas linhas por um corredor utilizado pelos passageiros para a transferência de uma linha para outra. Este último recurso é freqüentemente utilizado, em vista de permitir, na prática, que uma estação receba qualquer número de linhas. Mantém-se a discussão inicial baseada na restrição do grau em vista do menor custo que ela traz, habitualmente, para a construção das estações; no entanto, abre-se a possibilidade de deixá-la de lado na resolução interativa, caso isso se mostre conveniente. De fato, em cada estação é usual que não mais de duas linhas se cruzem, pois cada linha demanda um andar, restringindo o emprego de estações com mais de dois andares em vista do elevado custo. Cada andar, é claro, contribuirá com no máximo duas unidades de grau (correspondentes à chegada e à saída de uma linha), o que tende a limitar a 4 o grau de um vértice no grafo representativo das linhas.

Esta restrição torna o problema não polinomial. Por outro lado, um instrumento eficiente no sentido de apresentar propostas para uma malha metroviária não deverá ter elevada complexidade computacional, não fazendo sentido, portanto, a execução de testes de eficiência avaliados pelo tempo de execução. De qualquer forma, uma heurística será necessária em vista das diversas considerações a serem contempladas na análise da geração sucessiva das linhas, o que vem ainda resolver o problema da complexidade. O que importa, de fato, é a capacidade dessa heurística de lidar com as injunções a serem levadas em conta nesse processo. Neste ponto, exatamente, é preciso que o processo se torne interativo, permitindo ao projetista, seja a cada linha gerada ou ao final, introduzir na solução a sua visão do problema.

1.3  A heurística e sua construção O trabalho foi dedicado ao desenvolvimento de uma ferramenta computacional baseada em uma técnica heurística interativa, idealizada com o objetivo de auxiliar o projeto e a crítica de redes metroviárias e dar respaldo aos planejadores do sistema de que o projeto final atende aos interesses sociais e econômicos e também respeita as restrições inerentes ao problema. A heurística foi elaborada, então, para oferecer ao projetista propostas já selecionadas em acordo com as questões de estrutura, para que ele as aperfeiçoe pela introdução dos demais elementos de avaliação.

O trabalho, que envolveu fases alternadas de construção e de testes, usou recursos de grafos e procedimentos da geometria computacional, estes últimos na geração de grafos-suporte destinados aos testes que permitiram o aperfeiçoamento da heurística. Evidentemente, esse mesmo processo poderá levar a melhorias e aprimoramentos ulteriores.

Ao se construir um grafo-suporte para testes, partiu-se de um conjunto de vértices gerados aleatoriamente em uma área limitada do plano, para em seguida obter-se um grafo planar triangulado. Neste momento se trabalhou com cascas convexas sucessivas, partindo-se dos vértices mais distantes dois a dois, gerando com eles um ciclo e procedendo iterativamente da mesma forma com os vértices totalmente desconexos ainda existentes. Ao final, pode ocorrer que restem apenas dois vértices ao centro; neste caso, eles seriam simplesmente conectados por uma aresta.

Em seguida cada ciclo mais exterior é ligado ao imediatamente interior por arestas de comprimento mínimo, em número suficiente para que se obtenha uma triangulação local. Se a região central do conjunto contiver apenas um vértice, ele será unido a todos os vértices do ciclo interior (usando k arestas, se k for o número de vértices desse ciclo; já, se existirem dois vértices, a triangulação local exigirá k + 2 arestas e neste caso se utiliza ainda um critério de escolha da menor aresta). Os detalhes, bem como um exemplo, estão no Apêndice.

Esta técnica foi julgada preferível à triangulação de Delaunay (ver, por exemplo, Preparata & Shamos, 1985). Esta conhecida técnica de Geometria Computacional é de fácil uso e utiliza um critério de proximidade entre pontos, o que a apontaria como ideal para a aplicação aqui desenvolvida. No entanto, ela não garante uma estrutura de comprimento mínimo, a não ser quando se utilizam distâncias euclidianas: e, exatamente, no problema em estudo, as arestas do grafo-suporte possuem uma valoração em termos de custo que depende não apenas da distância mas ainda de diversas outras questões. Enfim, a técnica utilizada limita a busca de menores arestas às ligações entre os ciclos sucessivos, o que deve favorecer a geração de linhas mais diretas unindo vértices periféricos.

A definição do conjunto de vértices do grafo-suporte (estações que farão parte da rede), em uma aplicação real da heurística, não faz parte do escopo do trabalho. Os vértices devem ser estabelecidos a priori pela existência de uma demanda que justifique a criação de uma estação naquele ponto, ou pelo interesse em se desenvolver determinada área urbana pela oferta de um transporte público de maior capacidade. Para o caso do metrô, um método proposto para escolha de estações é apresentado por Junquilho (1981) e se baseia na maximização do benefício líquido, expresso como a economia de custo de viagem dos passageiros (medida pelo tempo de viagem) e os custos envolvidos na construção e operação do sistema.

2. Descrição da Heurística 2.1  Considerações iniciais A Heurística de Geração de Linhas (HGL) tem como propósito contribuir no processo de elaboração de um projeto de metrô que respeite a restrição de grau inerente ao problema e que permita a cada etapa a interação com a equipe responsável pelo projeto. Partindo de um grafo-suporte G, objetiva-se gerar linhas que minimizem o custo total de construção. Para isso, procuram-se os caminhos de menor custo entre os vértices periféricos.

Um ponto importante neste problema está no fato de que o modelo de grafo não é suficiente, estruturalmente, como uma base de dados representativa do sistema metroviário. É preciso, também, que se tenha informação sobre quais são as linhas consideradas, ou seja, por onde passam as composições.

O grafo final H,obtido pela aplicação da heurística de geração de linhas, será um grafo parcial de Gformado pela união de todas as linhas, respeitando as restrições de custo mínimo de construção e de grau, ou seja, que não tenham vértices com grau superior a 4, ou com grau nulo (que seriam estações não atingíveis pela rede).

A HGL é aplicada através de três etapas, sendo que a primeira executa um programa para gerar caminhos candidatos (ou seja, caminhos que apresentam, em princípio, condições de serem selecionados como linhas) e as duas últimas são etapas que analisam e se necessário modificam estes caminhos através de critérios pré-definidos, para que possam eventualmente ser selecionados. Estas etapas são executadas através da interface com o planejador do sistema, que assim intervém no processo, introduzindo no projeto as especificidades do contexto de aplicação do metrô.

2.2  Primeira etapa da HGL: Geração de caminhos candidatos A primeira etapa consiste na execução de um procedimento que tem como entrada a matriz de valores das arestas do grafo-suporte. O procedimento aplica o algoritmo de Floyd (Floyd, 1962) e busca, na matriz de distâncias que dele resulta, caminhos candidatos a participarem das linhas do sistema metroviário.

O processo de busca de caminhos candidatos é iterativo e consiste em se obter, da matriz de distâncias vigente a cada iteração, a maior distância entre pares de vértices, fazer o retraçamento do percurso correspondente e zerar a distância na matriz. Se houver neste itinerário pelo menos um vértice ainda não utilizado, considera-se este caminho como candidato a participar de uma linha do sistema. O processo iterativo de busca de caminhos candidatos termina quando todos os vértices do grafo pertencerem a pelo menos um caminho. Portanto, o algoritmo executará O(n) iterações polinomiais.

Os procedimentos executados estão indicados a seguir, mas não estão detalhados no texto uma vez que se trata de instrumental padrão da teoria dos grafos. Os detalhes, a nomenclatura e a notação estão em Boaventura Netto (2002).

' Procedimento inicialização: lê de um arquivo de entrada os dados das matrizes de distância e adjacência do grafo-suporte gerado.

' Procedimentofloyd: executa o algoritmo de Floyd, gerando como saída a matriz de distâncias que contém os valores do menor caminho (mij) entre cada par de vértices (i,j) e a matriz de roteamento final (Farbey et al., 1967; Land & Stairs, 1967).

' Procedimentoretraçamento(i,j) (i,j): faz o retraçamento do caminho mínimo entre o par de vértices (i,j) utilizando a matriz de roteamento final obtida após a aplicação do algoritmo de Floyd.

' Procedimentomaior_distância: busca na matriz de distâncias final obtida pela aplicação do algoritmo de Floyd a posição D[j,k] que possui o maior valor, armazenando as posições do par de vértices (j,k) nas variáveis jmd e kmd, posteriormente zera a posição d [jmd,kmd], para que na próxima execução deste procedimento se encontre a próxima maior distância.

Na descrição a seguir, as variáveis referenciadas têm o seguinte significado: ' nvi: variável inteira que armazena o número de vértices já pertencentes aos caminhos candidatos gerados; ' nca: número de caminhos gerados; ' mca[j,k]: matriz que armazena os caminhos candidatos; ' nvca: variável que armazena o número de vértices pertencentes ao caminho gerado a cada iteração; ' vnca: variável que armazena o número de vértices novos no caminho, ou seja, o número de vértices que estão participando pela primeira vez de um caminho.

2.3  Segunda etapa da HGL: Análise e modificação do conjunto de caminhos candidatos para eliminar trechos de caminhos com sobreposição de trechos Não é conveniente, em princípio, que duas linhas tenham trechos (arestas) em comum: isto implicaria na construção de um suporte de dimensão dobrada, seja em subterrâneo (túnel largo), seja externo (elevado, ou à superfície do solo). A segunda etapa da HGL consiste na aplicação de critérios de análise e modificação do conjunto dos caminhos candidatos, para que ele passe a ter o menor número possível de caminhos e de modo que não haja superposição de trechos de linhas.

Os critérios de análise e modificação dos caminhos candidatos são: ' a maior distância entre pares de vértices do grafo-suporte inicial é prioritária para escolha; ' dois caminhos que tiverem exatamente um vértice periférico em comum são considerados como uma única linha; ' se houver mais de dois caminhos candidatos com um mesmo vértice periférico em comum, procura-se fazer a união dos dois caminhos que juntos mapearem maior área radial ou transversal; ' se dois caminhos de tamanho k tiverem (k ' 1) vértices em comum, diferindo apenas por um dos vértices periféricos, estuda-se a viabilidade de uni-los através de um procedimento baseado em desigualdades triangulares, como exemplificado a seguir: Exemplo: Considerando os caminhos candidatos m1 = (x1, x6, x7, x9) e m2= (x1, x6, x7, x5), onde m1 é o caminho de maior comprimento, verifica-se se no grafo- suporte inicial existe a aresta (9,5). Caso exista, faz-se a união dos dois caminhos colocando-se no caminho resultante os (k ' 1) vértices comuns, seguidos dos vértices finais do menor e do maior caminho, resultando o caminho (x1, x6, x7, x5, x9). Se não existir a aresta (9,5), elimina-se o segundo caminho. Este procedimento pode ser usado com quaisquer pares de caminhos que difiram de apenas um vértice. Caso não seja possível a união, elimina-se o menor caminho (Figura_1).

Os critérios de análise e modificação dos caminhos candidatos devem ser aplicados não apenas quando os caminhos de tamanho k diferem pelo vértice periférico mas também quando diferem em apenas uma das k posições.

' Se duas linhas se cruzarem em mais de um vértice, estuda-se a possibilidade de deixar o menor número de cruzamentos possível.

' Os trechos não analisados que tiverem arestas em comum com as de caminhos já definidos como linhas devem ter estas arestas retiradas.

Se o trecho restante tiver pelo menos três arestas consecutivas pode ser considerado como um caminho candidato, devendo ser analisado através dos critérios anteriores.

Após aplicação destes critérios de análise e obtenção de um novo conjunto proposto para linhas do sistema, cujos caminhos não têm nenhuma aresta em comum, tem-se um grafo parcial H formado pela união das arestas pertencentes às linhas geradas.

2.4  Terceira etapa da HGL: Verificação dos graus dos vértices do grafo H e aplicação de operações corretivas, estudo de circuitos e eliminação de trechos paralelos Seja H o grafo parcial que resulta da segunda etapa da HGL. A terceira etapa consiste na verificação dos graus dos vértices de H, e resolver os problemas existentes, que podem ser de dois tipos: ' Vértices não contemplados com linhas, ou seja, que tenham grau zero; ' Vértices com grau superior a 4, ou seja, que pertençam a mais de duas linhas.

Nos dois casos, se procurará resolver o problema examinando o conjunto de vizinhos GG(x) do vértice xem análise.

No primeiro caso, algum vértice x não é atendido; procuram-se então as interseções de GG(x) com as linhas construídas em busca de algum vértice y terminal de linha, ou de dois vértices consecutivos de uma linha nesse conjunto; em ambos os casos, pode ser feita a inserção de x.

Se o problema não puder ser resolvido dessa forma, devem ser retiradas do grafo-suporte G as arestas que fazem parte das linhas obtidas até o momento e executado novamente o algoritmo de Floyd, reaplicando o processo à procura de uma linha que passe por x.

Pode ainda ser estudada a possibilidade da integração com outra modalidade de transporte, para satisfazer a demanda existente neste ponto: desta forma, x não seria considerado para construção de uma estação.

O segundo problema é mais complexo: é preciso que não se criem novos vértices de grau superior a 4 em H, ao se fazer trocas em linhas. Além disso, dentre as diversas possibilidades, deve-se escolher a de menor custo de construção. Para resolver esse problema, devem ser analisadas duas possibilidades: ' Se um vértice tiver grau entre 5 e 8 em H, criar um novo vértice representativo de uma instalação próxima, mantendo-se duas linhas passando pelo vértice de origem e desviando a(s) restantes(s) para o novo cruzamento. Deve-se considerar esta opção, se num raio da ordem de 300m (conveniente para trânsito a pé, conforme observado na prática para transferência de passageiros) houver possibilidade de construção dessa nova instalação.

' Não havendo a possibilidade de criação de um cruzamento próximo à estação com grau superior a quatro, será preciso avaliar as possibilidades de contornar x por um conjunto de trocas de arestas que foi chamado, em geral, operação contorno. Se uma operação contorno envolver um vértice de grau 4 pode-se cair em seguida na Possibilidade 1 e seresolver o problema de acordo com a técnica descrita.

Possibilidade de linhas circulares: observar, para os vértices terminais de cada linha mif, se no grafo-suporte inicial existe a aresta (xi, xf); caso ela exista, sugere-se o estudo da viabilidade da construção desta ligação, que transformaria a linha em circular.

Eliminação de trechos paralelos: pode ocorrer que dois trechos de linha estejam muito próximos no grafo H, uma vez que os vértices possuem posições definidas no plano cartesiano, é importante que se estude a eliminação de um dos trechos.

Ver o exemplo a seguir.

2.5  Exemplo de aplicação da HGL Para exemplificar a aplicação da heurística, gerou-se um grafo-suporte planar triangulado com 15 vértices (Figura_2).

Após a aplicação da heurística, foi feita uma análise das linhas que poderiam ser transformadas em circulares, como uma sugestão de realização futura caso haja na região demanda que justifique tal investimento.

A execução do procedimento caminhos_candidatos, tendo como entrada a matriz de valores das arestas do grafo da Figura_2, gerou como saída os seguintes dados: ' matriz de caminhos candidatos a participarem das linhas do sistema (MCA); ' vetor com os tamanhos de cada caminho candidato (TCA); e ' matriz de vértices periféricos (MVP) de cada caminho candidato.

O procedimento gerou 7 caminhos, correspondentes aos elementos não nulos em cada linha da matriz MCA.

Na segunda etapa da heurística, foram aplicados os critérios de análise e modificação dos caminhos candidatos da seguinte forma: ' O primeiro caminho recebeu uma linha do sistema, unindo os vértices periféricos 2 e 14; ' O quarto caminho tem, em comum com o primeiro, apenas um vértice (periférico); então se fez a união desses dois caminhos, obtendo-se {14, 13, 8, 3, 2, 7, 10, 11}, que passou a ser a primeira linha do sistema; ' Eliminaram-se as arestas dos outros caminhos candidatos coincidentes com as da primeira linha adotada: isto levou à retirada da aresta (7,10) do sexto caminho. Como ele passou a ter menos de três arestas consecutivas, deixou de configurar como caminho candidato. O conjunto vigente de caminhos candidatos passou a ser: 1º ' {7, 4, 3, 15}    2º ' {1, 3, 4, 7},     3º ' {5, 9, 13, 10}    4º ' {6, 3, 4, 7}; ' Adotou-se o caminho {7, 4, 3, 15} como a segunda linha do sistema; ' Eliminou-se a aresta (3, 4) do segundo e quarto caminhos candidatos, por coincidir com uma aresta da segunda linha adotada.

Como esses caminhos passaram a ter menos de três arestas consecutivas, eles deixam de pertencer ao conjunto de caminhos candidatos, que passou a ter apenas o caminho {5, 9, 13, 10}; ' Adotou-se então, o caminho {5, 9, 13, 10} como a terceira linha do sistema; ' Como o conjunto de caminhos candidatos deixou de existir, passa-se a fazer a verificação dos vértices do grafo H obtido através das linhas adotadas que foram: m1 = {14, 13, 8, 3, 2, 7, 10, 11},    m2 = {7, 4, 3, 15}   e   m3 = {5, 9, 13, 10}.

O grafo parcial H formado pelas linhas do metrô após a execução das duas primeiras etapas, pode ser visualizado através da Figura_3.

As linhas 1 e 3 têm dois cruzamentos (nos vértices 13 e 10), mas é possível eliminar-se o segundo cruzamento, já que o vértice 10 é terminal da linha 3.

Então se retira a aresta (13,10) e a terceira linha passa a ser {5, 9, 13}.

A verificação de graus indica que não há vértices com grau superior a 4, mas que há três vértices com grau nulo (vértices 1, 6 e 12). Os conjuntos de vizinhos desses vértices são: G G(1) = {2, 3, 15}; G G(6) = {3, 8, 12, 15}; G G(12) = {6, 8, 13, 14, 15}.

Observa-se que: ' o vértice 1 pode ser ligado ao vértice terminal da linha 2 através da aresta (1,15); ' o vértice 12 pode ser ligado ao vértice terminal da linha 3 através da aresta (12,13); ' o vértice 6 não possui vértices terminais na sua vizinhança, mas sim as extremidades de (8,3) (aresta da linha 1): então ele pode ser incluído na linha 1, através da substituição da aresta (8,3) pelas arestas (8,6) e (6,3).

Enfim, as arestas (4,7) e (2,7) são muito próximas: como 7 pertence à linha 1, (4,7) pode ser eliminada e a linha 2 fica com apenas 4 vértices.

As linhas passaram a ser: ' Linha 1: {14, 13, 8, 6, 3, 2, 7, 10, 11}; ' Linha 2: {1, 15, 3, 4}; ' Linha 3: {12, 13, 9, 5}.

A Figura_4 mostra as novas linhas: pode-se observar que todos os vértices pertencem a pelo menos uma linha e não existem vértices com grau superior a 4.

A análise da possibilidade de linhas circulares mostra que: ' A linha 1 pode ser transformada facilmente em uma linha circular, pois seus vértices periféricos, 14 e 11, são extremidades de uma aresta no grafo-suporte inicial; ' A linha 2 não oferece possibilidade de transformação em circular, pois os vértices periféricos estão muito distantes e para ligá-los seria necessário usar arestas que já pertencem a outra linha; ' A linha 3 possui seus vértices periféricos na vizinhança do vértice 8 e pode então ser transformada em circular por passagem através dele.

O resultado dessas modificações pode ser observado na Figura_5, que completa o exemplo.

3.  Uma Aplicação: Proposta de Sistema Metroviário para a Região Metropolitana do Rio de Janeiro 3.1  Considerações iniciais Neste item é apresentado um exemplo de aplicação da heurística de geração de linhas discutida no trabalho, através de uma simulação do planejamento de um sistema metroviário para a região metropolitana do Rio de Janeiro. A intenção deste exercício é mostrar a exeqüibilidade do procedimento proposto e fornecer um guia que possa ser útil para futuras aplicações.

Apesar de se ter um compromisso com a realidade, a precisão e confiança no resultado alcançado no planejamento de uma rede de metrô estão vinculadas à qualidade e à suficiência dos dados utilizados: ora, justamente as estatísticas existentes são com freqüência deficientes, em particular no setor de transportes, o que se reproduz no sistema metro-ferroviário da região metropolitana do Rio de Janeiro e empresas envolvidas. Nem todos os dados necessários estão disponíveis, tais como possíveis estações que fariam parte da rede, custos de construção das estações e de cada um dos possíveis trechos, matriz de demandas entre pares de estações e custo de operação dos trechos de linhas.

Por outro lado, a obtenção destes dados é por si só um grande projeto e, como tal, depende de decisões que transcendem a capacidade e o contexto de atuação associados ao presente trabalho.

Na construção do grafo-suporte utilizado, tomou-se como base um estudo da Companhia do Metropolitano do Rio de Janeiro (Metrô Rio, 2000), que traça um plano de expansão para o metrô do Rio até o ano 2020.

Deste plano foi desconsiderada a linha 3 (Rio ' Niterói), dada a ausência de sua interação com as demais linhas fora de um ponto único de conexão. Com relação à linha 4, foi considerada a versão do projeto que liga a Barra ao Centro indo até a estação Carioca, visto que a alternativa de final da linha no morro de São João deixa sem estação alguma bairros de elevada densidade de população, tais como Laranjeiras. Considerou-se, além das estações contempladas neste plano, algumas outras situadas em pontos associados a áreas adensadas (como Meier, Deodoro, Campo dos Afonsos, Cidade de Deus, Madureira etc.), ou a pólos atrativos para moradia, ou para investimentos (como Barra da Tijuca e Recreio dos Bandeirantes). Esta concepção ofereceu alternativas mais adequadas para a modelagem e o planejamento de linhas, contribuindo para melhorar o seu papel estruturador do espaço sócio-econômico e integrador das diferentes modalidades de transportes.

A HGL necessita, desde a modelagem do grafo-suporte até a aplicação de sua última etapa, ser desenvolvida por planejadores de sistemas metroviários com conhecimento das características geográficas, dados de demanda e de custos de construção e operação do futuro metrô, de modo a garantir uma aderência satisfatória à realidade, com um bom nível de otimização. Em vista disso, os resultados aqui apresentados podem envolver configurações bastante diferentes das que seriam obtidas numa situação real de projeto que contasse com mais recursos e um melhor sistema de informações.

3.2  Construção do grafo-suporte Na construção do grafo-suporte foram consideradas as linhas 1 e 2, já em operação, e as demais linhas do plano de expansão do metrô para os próximos 20 anos, à exceção da linha 3 conforme já citado (Metrô Rio, 2000), num total de 42 estações, além dos locais atrativos já referenciados não contemplados nesse plano, num total de 9 estações (representadas por círculo em tom mais claro na Figura_6).

A escolha destes pontos contou com a colaboração do Engenheiro de Transportes Luiz Antonio Werneck de Carvalho (da Companhia do Metropolitano do Rio de Janeiro). Por outro lado, muitas arestas de um possível grafo triangulado não foram incluídas, por considerações diversas (obstáculos naturais e regiões julgadas impróprias para construção de trechos).

Os vértices rotulados de 1 a 33 são estações que no grafo-suporte têm grau 1 ou maior que 2. Os vértices rotulados de 34 a 51 são de grau 2; eles correspondem a uma ou mais estações e deverão ser atendidos por alguma linha que conecte um par de vértices de grau maior que 2. O número de arestas do grafo, construído dessa forma, (Figura_6) é de 67. Os valores indicados correspondem a centímetros sobre o mapa utilizado.

Na Figura_6 não foram contempladas todas as estações do plano original: onde nele existiam vértices consecutivos de grau 2, em certos casos foram somados os valores das arestas consecutivas e os vértices entre elas desconsiderados: por exemplo Freguesia-Galeão, com 6 km, teria uma estação no Centro da Ilha, o que significa que estes 6 km seriam a soma dos trechos (Freguesia, Ilha) e (Ilha, Galeão).

Existem trechos pertencentes às linhas 1 e 2 que já estão em operação; nestes casos, as arestas correspondentes do grafo-suporte têm seu tamanho real.

Trechos novos tiveram seus valores aproximados, tendo sido consideradas distâncias euclidianas medidas entre pares de vértices, a menos de trechos com obstáculos evidentes, como mar e aeroporto. As medidas das arestas novas foram obtidas através de um mapa (SMU/PMRJ, 2000), com escala de 1:50.000.

Procurou-se não sobrepor o grafo-suporte à rede ferroviária existente, de modo a viabilizar um estudo futuro de integração entre os vários modais de transporte.

3.3  Aplicação da heurística de geração de linhas Na aplicação da HGL, após a geração de caminhos candidatos, foi obtida a seguinte saída de dados: ' Uma matriz com 14 caminhos candidatos a participarem das linhas do sistema metroviário a ser proposto (MCA[j,k], j = 1, , 14, k = 1, , 18); ' Um vetor com os tamanhos destes 14 caminhos candidatos (TCA[j], j = 1, , 14) cuja unidade dos dados é o km, seguindo a escala do mapa utilizado de 1:50.000; ' Uma matriz (MVP[j,k], j = 1, , 14, k = 1,2) com os vértices periféricos dos 14 caminhos candidatos.

Cada linha da matriz MCA representa um caminho candidato, cada posição do vetor TCA[j] o seu tamanho (aqui em km) e cada linha da matriz MVP contém os vértices periféricos dos respectivos caminhos candidatos. No que se segue, as estações são representadas por suas siglas.

Na segunda etapa da heurística, foram aplicados os critérios de análise e modificação dos caminhos candidatos além de tentar respeitar a infra-estrutura do metrô já existente.

A Tabela_1 mostra o resultado da análise dos caminhos candidatos no que tange as interseções de seus conjuntos de arestas, observada a prioridade da ordem numérica.

O conjunto de linhas que formam o grafo parcial H é, portanto, o seguinte: ' Linha 1:(LEB, GOS, BTF, CRC, LAR, SCL, JBT, GAV, JAO, ALV, ITA, REC); ' Linha 2:<formula/> (FRE, GAL, FUD, PEN, BRP, IRJ, VAC, LMC, MAD, TAQ, AUT, ITA); ' Linha 3:<formula/> (CRC, CTR, ESA, SCR, MRC, TRG, MDA, INH, TOC, LMC); ' Linha 4:<formula/> (MDA, MEI, SPN, URU); ' Linha 5:<formula/> (FUD, VIP, CAJ, ROD, SEV, PRM, CAS, CRC); ' Linha 6:<formula/>(TOC, VIC, IRJ, CNT, PVN, NIL).

O grafo H (obtido após a aplicação das duas primeiras etapas da HGL) pode ser visualizado na Figura_7.

Antes da aplicação da terceira fase da HGL, foi incluída uma sétima linha, de modo a contemplar um circuito previsto no plano de expansão do metrô. Esta modificação envolve a criação do vértice CVR (Estação da Cruz Vermelha) com as arestas (ESA, CVR) e (CVR, CRC) em H.

No modelo inicial não foram incluídas as arestas (URU, GAV) e (GAV, LEB), visto que o algoritmo de Floyd não contempla circuitos positivos; ao serem elas consideradas, pôde ser traçada a linha circular: m2 = (GAV, URU, SPN, AFP, ESA, CTR, CRC, BTF, GOS, LEB, GAV). A criação da sétima linha foi priorizada pelo fato de uma linha circular ser sempre desejável em uma região adensada e desenvolvida, com grande concentração de atividades comerciais, industriais e de prestação de serviços, além de possibilitar maior flexibilidade operacional caso algum trecho apresente problema de circulação. Com a criação da sétima linha, os trechos das outras linhas que passaram a coincidir com ela foram eliminados, a saber, o trecho (LEB, GOS, BTF, CRC) da linha 1, o trecho (CRC, CTR, ESA) da linha 3 e o trecho (URU, SPN) da linha 4. O vértice AFP que tinha grau zero passou a ter grau 2.

Com objetivo de proporcionar uma ligação direta da Baixada Fluminense ao Centro, inclui-se um trecho de 3 Km entre Estácio (ESA) e Carioca (CRC), através da estação Cruz Vermelha (CVE) a ser localizada na praça com o mesmo nome. A linha 3 passou a ter o vértice CRC como vértice terminal, o que soluciona o problema da sobrecarga imposta pelos passageiros da atual linha 2 que se vêem obrigados a realizar o transbordo na estação Estácio, que não foi projetada como terminal, na qual atualmente existe um grande fluxo de passageiros.

Com a inclusão da linha circular e do vértice CVE, o conjunto de linhas que formam o grafo parcial H passou a ter a seguinte configuração: ' Linha 1: <formula/>(CRC, LAR, SCL, JBT, GAV, JAO, ALV, ITA, REC); 'Linha 2:  <formula/> (FRE, GAL, FUD, PEN, BRP, IRJ, VAC, LMC, MAD, TAQ, AUT, ITA); ' Linha 3: <formula/>(CRC, CVE, ESA, SCR, MRC, TRG, MDA, INH, TOC, LMC); ' Linha 4: <formula/>(MDA, MEI, SPN ' Linha 5:  <formula/> (FUD, VIP, CAJ, ROD, SEV, PRM, CAS, CRC); ' Linha 6: <formula/>(TOC, VIC, IRJ, CNT, PVN, NIL); e 'Linha 7:<formula/> (GAV, URU, SPN, AFP, ESA, CTR, CRC, BTF, GOS, LEB, GAV).