Uma Arquitetura de Software Interativo para
Apoio à Decisão na Modelagem e Análise do Tráfego
Urbano
Walid A. R. Jradi
Hugo A. D. Nascimento
Humberto Longo
Instituto de Informática
UFG, GoiâniaGO, Brasil
{wallid,hadn,longo}@inf.ufg.br
Bryon Richard Hall
Instituto de Matemática e Estatística
UFG, GoiâniaGO, Brasil
[email protected]
Resumo
Web
Este trabalho apresenta uma ferramenta
que inclui uma arquitetura para modelagem,
simulação e visualização do tráfego urbano. A arquitectura inova ao apresentar uma modelagem do problema que pode ser distribuída e remotamente atualizada por vários usuários, e
para a utilização de um modelo matemático adequado para a realidade brasileira de tráfego.
Além disso, inclui o uso de ferramentas grácas interativas, a m de produzir resultados visuais
sobre mapas da região em análise. Um protótipo da arquitetura foi implementado e avaliações
realizadas por especialistas indicaram que pode ser útil para responder a perguntas relativas
a tráfego urbano e a urbanismo.
Palavras-Chave:
Transportes.
Trafégo Urbano, Sistema de Suporte à Decisão. Aplicações a Logística e
Abstract
This paper presents a web-based DSS Decision Support System architecture for modelling,
simulating and visualizing urban trac. The arquitecture innovates by presenting a modelling
of the problem that can be distributed and remotely updated by several users, and for using a
mathematical model suitable for the Brazilian trac reality. Moreover, it includes the usage
of interactive graphical tools in order to produce visual results over maps of the region in
analysis. A prototype of the architecture was implemented and evaluations carried out by
specialists indicated that it can be useful for answering questions concerning urban trac and
urbanism.
Keywords:
portation.
1
Urban Trac, Decision Support System. Applications to Logistics and Trans-
Introdução
Recentemente, jornais de diversas cidades brasileiras têm relatado que o trânsito, na
maioria dos centros urbanos, está em estado caótico (veja, por exemplo, Gallo e Galvão
(2008)).
Este fato vem ocorrendo, principalmente, devido ao mau dimensionamento da
XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento
Pág. 1324
malha viária em relação ao número de veículos que por ela trafega, agravado pela ausência
de ferramentas capazes de auxiliar na gestão do tráfego urbano.
O objetivo deste artigo é apresentar uma arquitetura desenvolvida para auxiliar na tomada de decisões em Engenharia de Tráfego e implementada na forma de uma ferramenta
Web.
Apresenta também um modelo matemático para simulação de tráfego urbano e o
SAD Sistema de Apoio à Decisão (DSS
Decision Support System )
desenvolvido usando
tecnologias RIA. Por m, apresenta um resumo dos principais resultados gerados. O algoritmo subjacente resolve uma inequação variacional, o PET-EU (Problema de Equilíbrio de
Tráfego Equilíbrio de Usuário), e uma minimização simples, o PET-OS (Otimização de
Sistema). Um simula o uxo rodoviário existente em determinado horário e dia da semana,
estocasticamente. O outro aponta o uxo ideal na minimização de emissão de poluentes e
consumo de combustível.
A simulação do tráfego é feita com base em algoritmos de comprovada ecácia existentes
na literatura, mas com adaptações propostas e implementadas pelos autores deste artigo. A
ferramenta
Web
implementada com base na arquitetura permite a visualização de informa-
ções geográcas sobre o tráfego, bem como oferece formas de investigar o efeito de possíveis
reestruturações da rede viária.
O restante deste artigo está organizado como segue: a Seção 2 descreve o modelo matemático desenvolvido para simulação do tráfego urbano, junto com algumas fundamentações
teóricas sobre o assunto; a Seção 3 descreve os requisitos e a arquitetura, além da transformação necessária no grafo representante da malha viária; a Seção 4 apresenta o sistema
PET-Gyn; Seção 5 as avaliações feitas por especialistas da área em relação à arquitetura implementada; por m, a Seção 6 apresenta as conclusões e as propostas de trabalhos futuros
desta pesquisa, seguida das referências bibliográcas.
2
Modelo Matemático de Alocação de Tráfego
Beckmann et al. (1956) foram os primeiros a apresentar uma modelagem matemática
para computar os estados EU e OS. Seu ponto central é a formulação de uma função de
latência para cada avenida do sistema viário de tal forma que, quanto mais motoristas
usarem-na, maior será a sua latência, tornando-a cada vez menos atrativa e obrigando os
usuários a escolherem rotas alternativas.
A modelagem matemática de Beckmann et al. (1956) considera o PET-OS e o PETEU como problemas de minimização, denidos da seguinte forma: seja dado um digrafo
D = (V, A),
de
n
nós e
de percorrer o arco
a,
m
arcos, e
ta (x, Γ)
é a função de
Rm
em função de suas características físicas
em
Γ
R
que expressa o tempo
e do vetor de uxo
x
(veja
Hensher e Button (2002)). Tal aplicação deve ser convexa, contínua, não-negativa e nãodecrescente em
xk
para todo
k.
O PET-EU procura uxo
x∗
tal que
t(x∗ )(x − x∗ ) ≥ 0
para
∗
todo uxo x viável, ou seja, que atenda à demanda. Em x ocorre minimização unilateral e
∗
individual de custo de viagem para os motoristas. O uxo x é encontrado mediante uma
sucessão de minimizações de funções em iterações de um ou mais passos, conforme She
xa ta (x, Γ) e a solução x∗ 0 é encontrado
0
∗
− x | mede a distância do uxo real do uxo ideal, ou seja, a
(1985). O PET-OS busca minimização da função
∗
por simples minimização. |x
P
ineciência intrínseca da rede viária. Supõe-se a demanda de uxo entre pares de nós OD
conhecida
Versões mais simples deste algoritmo foram implementadas com certo sucesso por Hall
(1999, 2002), mas sem uma série de modicações presentes na atual edição para a modelagem
de proibição de conversão (Seção 3.3) e o atendimento de aspectos práticos de uso e uso
múltiplo, inclusive à distância.
XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento
Pág. 1325
3
A Arquitetura do SAD
3.1
Web
Requisitos da Arquitetura
São apresentados a seguir os requisitos da arquitetura, especicados visando direcionar
a implementação da mesma:
1. Possuir Acesso
Web
Simplicado. Todas as funcionalidades do sistema devem ser aces-
síveis através de uma interface
Web,
de forma a poderem ser utilizadas remotamente
e independentemente de plataforma de hardware e software.
2. Permitir Trabalho Colaborativo.
Deve permitir que diversos usuários trabalhem de
forma simultânea, modelando e analisando um ou mais projetos de tráfego.
3. Possibilitar Preenchimento e Atualização Incremental da Base de Dados.
Deve ser
possível inserir e atualizar de forma incremental os dados referentes às modelagens
e às simulações. Assim, uma modelagem de tráfego de uma cidade inteira pode ser
construída a partir de acréscimos a uma pequena base inicial.
4. Utilizar Mapas Urbanos.
Devem ser utilizados mapas urbanos para representar e
visualizar os diversos elementos constituintes da rede viária de uma cidade, tais como:
ruas, avenidas, cruzamentos, praças, rotatórias, semáforos, entre outros.
5. Implementar uma modelagem adequada à realidade brasileira. A modelagem deve considerar aspectos especícos da rede viária brasileira, tais como rotatórias, proibições
de realizar conversões à esquerda, etc.
6. Permitir Otimização Interativa. A ferramenta de simulação de trânsito urbano deve
permitir que o engenheiro de tráfego realize modicações na estrutura da rede viária,
possibilitando o estudo e a avaliação do impacto de possíveis alterações antes que
sejam efetivamente implantadas. Entre elas, podem ser citadas a construção de uma
nova via, a duplicação de uma via existente, a construção de viadutos, a modicação
do tempo de semáforo, a inversão da mão de uma rua, a simulação de acidente que
bloqueie uma determina via e a inserção e retirada de semáforos.
Deve permitir
também a comparação dessas alterações com a rede original ou redes diferentes entre
si.
7. Possuir Visualizações Interativas e Intuitivas. O sistema deve possuir visualizações efetivas e expressivas que permitam inserir, apresentar e atualizar as informações relativas
ao tráfego urbano. Recursos como planilhas, mapas da região em foco, visualizações
de grafos, coloração, ícones e diagramas devem ser usados com o objetivo de facilitar
a atividade do usuário.
O atendimento a todos os requisitos é uma das características que diferencia a proposta
de SAD aqui descrita de outros sistemas existentes de simulação do tráfego, tais como o
Dracula, apresentado pelo Institute for Transport Studies (a), e Saturn, também do
Institute for Transport Studies (b).
Tais sistemas implementam um subconjunto menor
desses requisitos.
3.2
Módulos da Arquitetura
A arquitetura está organizada em quatro módulos, conforme ilustra a Figura 1.
XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento
Pág. 1326
Figura 1: Módulos da Arquitetura.
O
Módulo de Armazenamento e Recuperação de Dados
é responsável pelo for-
necimento dos mapas e das informações sobre a rede viária urbana em si, das políticas
de tráfego para cada local da rede e das demandas de veículos. Ele armazena também os
resultados de simulações anteriores, de modo que seja possível mensurar diferenças entre
propostas distintas para o tráfego. Este módulo atende ao requisito n
o 4 da arquitetura podendo tanto armazenar os mapas internamente quanto usar mapas disponíveis on-line e ao requisito n
o 3, pois é possível, partindo-se de uma proposta inicial para a rede viária,
expandir tal rede até que abranja a totalidade de uma cidade ou região metropolitana.
O
Módulo de Simulação
Módulo de Visualização
possibilita a modelagem e simulação de uma rede viária e o
cálculo para ns comparativos do uxo ideal, com minimização de consumo de combustível.
O
é responsável pela produção de visualizações interativas,
o
em atendimento ao requisito n 7, para permitir a modelagem do tráfego, ativar a simulação
XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento
Pág. 1327
e exibir os resultados dos uxos computados de veículos. Parte deste módulo é enviado ao
navegador cliente durante a carga da aplicação onde é executado, e passa a ser chamado
de Módulo de Apresentação e Interação, descrito em mais detalhes a seguir.
O
Módulo de Apresentação e Interação
é quem efetivamente apresenta a interface
com o usuário, os mapas e os resultados do cálculo do tráfego.
do navegador
Web
Ele é executado dentro
do usuário, enquanto os três módulos anteriores estão localizados em
servidores remotos. Conforme pode ser observado na Figura 1, várias instâncias deste módulo podem estar em execução simultânea, acessando concorrentemente uma mesma base
de dados, de forma a atender assim aos requisitos n
3.3
o 1 e no 2 da arquitetura.
Transformação do grafo da rede viária
O presente trabalho realizou uma adaptação no grafo representante da rede viária urbana
antes de utilizar algoritmos de cálculo de caminhos mínimos (veja Cormen et al. (2002)). O
grafo original representa ruas e avenidas como arcos, enquanto as interseções das mesmas
são representadas como nós. No entanto, nem todos os caminhos mínimos sobre esse grafo
são válidos, pois há certas conversões no tráfego real que não podem ser realizadas.
Desta forma, as conversões ou continuações permitidas foram representadas através de
Arcos Livres. Um arco livre
a2 = (j, k),
com
i, j
e
k
nós
` consiste em um par de arcos (a1 , a2 ) de G, tal que a1 = (i, j) e
de G. Por simplicidade, representaremos também um arco livre
pela seqüência formada pelos três nós que compõem o seu par de arcos, como, por exemplo,
(i, j, k).
Note que somente os pares de arcos de uma rede viária que são especicados como
arcos livres permitem uma conversão livre, inclusive simples deslocamento em linha reta ao
longo de uma via de trânsito.
Conseqüentemente, o algoritmo de caminhos mínimos deve ser executado não sobre o
G0 derivado de G, considerando um
0
0
0
conjunto L de arcos livres. O grafo resultante G = (V , E ) tem as seguintes dimensões:
0
|V'|=1+|L|. A seguir, é apresentada a construção do grafo G a partir de G e de L. Um
grafo original
G
da rede viária, mas sobre um grafo
exemplo da tranformação é ilustrada na Figura 3.
1. Seja o grafo
aresta de
E
G = (V, E), com A seu vértice inicial, uma função
L de arcos livres, conforme a Figura 2:
de custo
c
para cada
e uma lista
Figura 2: Grafo original representando ruas, cruzamentos e arcos livres.
2. Cada arco livre
(u, v, w)
de
G
torna-se um vértice
hu, v, wi
em
G0 .
Vide passo 1 na
Figura 3.
XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento
Pág. 1328
3. Cada par de arcos livres
G0 ,
cujo custo
c0
(u, v, w) e (v, w, z) gera uma aresta (hu, v, wi, hv, w, zi) em
c0 (hu, v, wi, hv, w, zi) = (c(w, z)), ilustrado no passo 2 da
é dado por:
Figura 3.
4. O vértice
A
de
5. Cada arco livre
G
também torna-se um vértice de
G0 .
Vide passo 3 na Figura 3.
(A, v, w) gera uma aresta (A, hA, v, wi) em G0 , com custo c0 dado
= c(A, v) + c(v, w), conforme ilustra o passo 4 da Figura 3.
por
c0 ((A, hA, v, wi))
Figura 3: Passos necessários à transformação.
G0
A e terminando em um vértice v ,
é possível construir o seu caminho correspondente em G. Esse processo exige escolher o
0
menor caminho de A até os vértices de G cujos índices possuam como suxo v (os índices
0
de dois ou mais vértices de G podem terminar com o mesmo suxo). Além disso, é preciso
considerar o custo das arestas diretas (A, v), caso elas existam em G. Esta transformação
pode ser realizada em tempo n log(n), onde n indica a quantidade de arcos livres da rede
Note-se que dado um caminho em
partindo de
viária.
4
O Sistema PET-Gyn
Foi implementada uma ferramenta, batizada de PET-Gyn, seguindo as especicações
da arquitetura descrita na Seção 3. Uma das premissas básicas em sua implementação foi
o uso exclusivo de tecnologias livres, de código-fonte aberto ou não. Portanto, as soluções
tecnológicas utilizadas em cada componente da arquitetura do sistema foram as seguintes:
•
O Módulo de Simulação foi implementado em Java e faz uso de algoritmos baseados
nas soluções propostas por Arezki e Van Vliet (1990), She (1985) e implementado por
Hall (1999, 2002). No entanto, este módulo utiliza um conjunto renado de funções de
latência, denidas pelos autores do presente trabalho, as quais modelam de forma mais
apurada as especicidades do trânsito brasileiro, além de fazer uso da transformação
do grafo descrita na Seção 3.3.
XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento
Pág. 1329
•
Para o Módulo de Armazenamento e Recuperação de Dados foram utilizados o SGBD
FireBird e o servidor de mapas do Google.
•
No Módulo de Apresentação e Interação foram utilizadas as tecnologias Java Server
Pages (JSP), Asynchronous JavaScript and XML (AJAX) e a API JavaScript fornecida
pelo GoogleMaps.
A ferramenta está disponível também à sociedade para utilização e melhoria, podendo
uma demonstração ser usada através do portal
http://www.inf.ufg.br/funcomp,
com da-
dos do tráfego urbano de uma região de Goiânia-GO.
5
Avaliações
A ferramenta implementada segundo as especicações da Seção 3.1 foi submetida à
avaliação por meio de entrevistas com prossionais direta ou indiretamente responsáveis
pelas políticas de trânsito da capital goiana.
Para cada avaliador, foi feita uma breve
apresentação sobre as motivações do trabalho e sobre a modelagem matemática, seguida de
uma explicação das telas e dos recursos da ferramenta. Um questionário foi aplicado, sendo
preenchido pelos entrevistadores à medida que a avaliação era realizada.
De um modo geral, as avaliações indicaram inequivocamente uma carência, no mercado,
de ferramentas de simulação adequadas à realidade brasileira do trânsito urbano. Todos os
avaliadores demonstraram, portanto, grande interesse no presente estudo e também o desejo
de que o mesmo tivesse continuidade com novas pesquisas.
Observamos ainda que a ferramenta PET-Gyn, implementada para
Web
usando tecno-
logias AJAX, foi capaz de lidar com um volume considerável de dados, mantendo um desempenho satisfatório. Tal desempenho, porém, talvez não possa ser alcançado se a mesma
for executada em máquinas muito antigas ou ligadas a redes não muito rápidas.
6
Conclusões
Os
software
em uso pelos órgãos de estudo e administração das condições do tráfego
urbano não reformulam o problema como PET-EU nem PET-OS. Fazem input de um valor
de uxo predeterminado e calculam o movimento deste em certa via, mas não exploram
as decisões tomadas por motoristas na realidade, de buscar caminhos que minimizem seu
tempo de deslocamento.
Os programas atuais utilizados não realizam uma simulação do
tráfego global em função da demanda global; programas existentes desta simulação como
DRACULA e SATURN não permitem modelar as especicidades do trânsito brasileiro,
como de interação múltipla entre correntes de tráfego em ruas distintas.
O presente trabalho propôs uma arquitetura de software para apoio à decisão na análise
e simulação de tráfego urbano. Ela dene uma modelagem matemática baseada no cômputo
dos modelos EU e OS, com funções de latência ajustadas para a realidade do trânsito brasileiro. A arquitetura também prevê a interação via
Web
e o uso de visualizações interativas
que facilitam as atividades de modelagem, simulação e análise de projetos de tráfego, além
de um conjunto de outros requisitos.
A modelagem matemática necessitou de adaptações para tratar as conversões permitidas no trânsito. Foi criado o conceito de
Arcos Livres
, e denida uma transformação
que converte o grafo de rede viária em outro, contendo apenas caminhos válidos, para o
cômputo dos caminhos mínimos. Esse processo é uma contribuição do trabalho que, por si
só, representa uma área de pesquisa que pode continuar a ser explorada.
XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento
Pág. 1330
A arquitetura prevê formas de armazenar informações necessárias para a simulação de
obras de engenharia do trânsito da cidade e mecanismos que permitem estimar o impacto de
situações temporárias (por exemplo, a interdição de uma avenida para obras ou por causa de
um acidente) ou permanentes (como mudanças do sentido de uma ou mais vias, retirada ou
colocação de semáforos, etc). Foi implementado um SAD baseado na arquitetura proposta,
chamado de PET-Gyn, inteiramente baseado em tecnologias livres.
Avaliações realizadas
sugerem que o mesmo pode ser útil aos prossionais da engenharia de tráfego. Propostas
de melhoria inclusive foram feitas pelos avaliadores.
Espera-se que as contribuições feitas com a arquitetura e com as soluções de modelagem
e de simulação do trânsito urbano, bem como com o sistema implementado, levem, a médio
prazo, a melhorias da malha viária atual.
Como trabalhos futuros dessa pesquisa, propõem-se, entre outros, a exploração de alternativas para as funções de latência, utilizando métodos numéricos que permitam encontrar
funções mais precisas de forma automática; a atribuição de pesos para as avenidas, de forma
a simular a preferência subjetiva dos motoristas em relação a certos caminhos, muitas vezes
não ótimos; a disponibilização da ferramenta documentada como
software
livre e o desen-
volvimento de novas funcionalidades para melhorar a interação, simulação e visualização
dos dados georeferenciados.
Referências
Arezki, Y. e Van Vliet, D. (1990). A Full Analytical Implementation of the PARTAN/FrankWolf Algorithm for Equilibrium Assignment.
Transportation Science,
Beckmann, M., Mcguire, C., e Winsten, C. (1956).
tation.
24(1):5862.
Studies in the Economics of Transpor-
Yale University Press, New Haven, Connecticut.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., e Stein, C. (2002).
Prática.
Algoritmos: Teoria e
Editora Campus, 2 edition.
Gallo, R. e Galvão, V. Q. (2008). Área central de SP perde moradores, e periferia incha.
Folha de São Paulo, 18/02/2008.
Hall, B. R. (1999).
Apresentação de Modelagem de Tráfego Rodoviário em Goiânia.
Anais do XXXI Simpósio brasileiro de Pesquisa Operacional,
Hall, B. R. (2002). Modelagem Matemática e Computacional do Tráfego Urbano. In
do XXXIV Simpósio brasileiro de Pesquisa Operacional,
Hensher, D. A. e Button, K. J. (2002).
In
Juiz de Fora, MG.
Anais
Rio de Janeiro, RJ.
Handbook of Transport Modelling.
Institute for Transport Studies, U. o. L.
Dynamic Route Assignment Combining User
Learning and microsimulAtion.
Institute for Transport Studies, U. o. L.
Simulation and Assignment of Trac to Urban
Road Networks.
She, Y. (1985). Urban Transportation Networks: Equilibrium Analysis with Mathematical
Programming.
Prentice-Hall.
XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento
Pág. 1331