Modeling distribution network of urban facilities through graphs theory = Rede de distribuição modelada de equipamentos urbanos através da teoria de grafos

Francisco Ortega Riejos

Resumo


As redes de transporte existentes podem ser modeladas geometricamente mediante esquemas compostos por nós e arestas. Um grafo G = (N, A) é a representação abstracta de um sistema de carácter especial ou temporal que se formaliza através de um conjunto finito de nós (N) e um conjunto de arcos (A) que indicam as ligações directas existentes entre pares de nós origem-destino.

Quando uma rede de transporte urbano é desenhada desde o início, a rede proposta deve apresentar uma estrutura topológica compatível com a organização urbana das ruas da cidade. No grafo resultante aparecem, de forma destacada, determinados nós que correspondem aos sítios que geram grande mobilidade na cidade. Uma vez que a questão das viagens é estimada e a infraestrutura da rede (nós e arcos) está estabelecida, passamos a definir as vias de trânsito do sistema, o seu número, rota, frequência e capacidade das unidades de transporte, dando assim resposta à questão. A concatenação dos arcos do grafo é a base para o desenho de corredores que canalizam a proposição das viagens, entre a origem e o destino. Os alinhamentos mais promissores (em termos de eficácia e eficiência) determinarão as vias de trânsito (metro ou autocarro) que serão utilizadas pelos sistemas das empresas de transporte.

A representação algébrica de grafos relacionados com as infraestruturas é dada pela sua matriz de adjacência. O resultado "um" na posição (i,j) da matriz indica que há um arco que liga directamente o nó i ao nó j. Se, pelo contrário, o resultado for "zero" para a posição (i,j), não se verifica a referida ligação directa. Uma maneira simplificada de abordar o problema do desenho da infraestrutura de transporte consiste em preencher inteligentemente as células de uma matriz de adjacência com "zeros" e "uns".

O objectivo desta contribuição é apresentar como a busca das melhores opções no planeamento dos transportes pode ser conduzida através da formulação de modelos matemáticos de optimização em espaços geométricos discretos, representados através de grafos.

 

The existing transport networks can be geometrically modeled as schemas composed of nodes and edges. A graph G = (N, A) is the abstract representation of a system of spatial or temporal character which is formalized by means of a finite set of nodes (N) and a set of arcs (A), that indicate the directional sense of a connection directly between pairs of source and destination nodes.

When an urban transportation network is designed from scratch, the proposed network must exhibit a topological structure compatible with the urban arrangement of city streets. In the resulting graph appear, in a highlight way, certain nodes that are sites which generate a great mobility in the city. Once travel demand has been estimated and the network infrastructure (arcs and stations) has been established, the transit lines of the system are determined in terms of their number, route, frequency and capacity of transport units in order to satisfy the demand. The concatenation of the edges in the graph is the basis for designing corridors that drive travel demand between origins and destinations. The most promising alignments (in terms of effectiveness and efficiency) will lead to the future transit lines (subway or bus) which will be operated by transport companies in the system.

The algebraic representation of graphs related to infrastructures is given by its adjacency matrix. A one at position (i, j) of the matrix indicates that there is an arc that directly connects node i to node j. If, in an opposite way, there is a zero at the position (i, j), then there would be no such connection. A simplified way of looking at the problem of designing transportation infrastructure consists of cleverly fill the cells of an adjacency matrix with zeros or ones.

The aim of this contribution is to present how the searching of the best options in transportation planning can be carried out by means of the formulation of mathematical optimization models in discrete geometric spaces described by graphs.


Apontamentos

  • Não há apontamentos.


Fundação Minerva - Cultura - Ensino e Investigação Científica / Universidades Lusíada, 2004-2014
Serviços de Informação, Documentação e Internet
Rua da Junqueira, 188-198 | 1349-001 Lisboa | Tel. +351 213 611 617 | Fax +351 213 622 955 | E-mail: revistas@lis.ulusiada.pt | skype | chat