- Modelagem Matemática e Computacional / CEFET-MG

Transcrição

FERNANDO BERNARDES DE OLIVEIRA
GERAÇÃO DE TEMPOS SEMAFÓRICOS
UTILIZANDO INTELIGÊNCIA
COMPUTACIONAL EM SIG CONVENCIONAIS
Belo Horizonte – MG
Setembro de 2009
FERNANDO BERNARDES DE OLIVEIRA
GERAÇÃO DE TEMPOS SEMAFÓRICOS
UTILIZANDO INTELIGÊNCIA
COMPUTACIONAL EM SIG CONVENCIONAIS
Dissertação apresentada ao Curso de
Mestrado em Modelagem Matemática e
Computacional do Centro Federal de Educação Tecnológica de Minas Gerais, como
requisito parcial à obtenção do título de
Mestre em Modelagem Matemática e Computacional.
Área de pesquisa: Sistemas Inteligentes.
Orientador:
Prof. Dr. Paulo Eduardo Maciel de Almeida
Centro Federal de Educação Tecnológica de Minas Gerais
(CEFET-MG)
M ESTRADO EM M ODELAGEM M ATEMÁTICA E C OMPUTACIONAL
C ENTRO F EDERAL DE E DUCAÇÃO T ECNOLÓGICA DE M INAS G ERAIS
D IRETORIA DE P ESQUISA E P ÓS -G RADUAÇÃO
Belo Horizonte – MG
Setembro de 2009
Folha de aprovação do projeto. Esta folha será fornecida
pelo Programa de Pós-Graduação e deverá substituir esta.
Dedico este trabalho aos meus pais, José Martins e Jamile, pelo amor e empenho
incondicionais em minha educação e para a realização de meus sonhos.
Este trabalho também é dedicado à memória de minha mãe-avó, Maria Joaquina.
Agradecimentos
Agradeço sobretudo a Deus, por sempre ter me iluminado e pelas bênçãos e graças derramadas;
Aos meus pais, José Martins e Jamile, pelo exemplo de vida, atenção e conselhos;
Aos meus irmãos, Ricardo e Ana Marcele, por todo carinho, amparo, paciência e
alegrias;
À minha namorada Ana Flávia e seus familiares, por todo cuidado e compreensão;
Ao meu orientador, Prof. Dr. Paulo Eduardo Maciel de Almeida, pelo apoio, tranquilidade, paciência e pelo acolhimento fraternal;
Ao meu Tio Antônio, pelo incentivo e pelas "obras de engenharia civil" em alguns
sábados;
À minha Tia Constância, à Janete e ao Miguel, pela preocupação, orações e ensinamentos;
Ao Chrystian, à Denise, ao Igor, ao meu afilhado Artur e demais familiares, pelo
carinho, pela força e por serem presenças marcantes em minha vida;
Ao Marcelo, pelas lições e pelos momentos de descontração;
Ao Gabriel, por toda consideração e auxílio;
Ao Juvêncio, pelo companheirismo durante essa jornada;
Ao Tuffi, pela amizade e por toda disponibilidade e interesse em ajudar;
Ao pessoal do LSI, pela amizade e auxílio;
Aos colegas e professores do CEFET-MG, pelos ensinamentos;
Ao CEFET-MG pelo apoio financeiro individual recebido;
Aos amigos do UNIFOR-MG pelo incentivo e confiança;
Aos amigos da Zeus Informática pela torcida e contribuições;
À Prof. Dr. Ana Bazzan e à Prof. Denise Oliveira pela gentileza e atenção nas
informações sobre o cenário de estudo;
Ao DENATRAN pela cordialidade no envio do Manual de Semáforos, contribuindo
pontualmente para a pesquisa;
Enfim, a todos que direta ou indiretamente contribuíram para que mais esse sonho
se concretizasse!
"Tudo é do Pai!
Toda honra e toda a Glória,
É Dele a vitória
alcançada em minha vida."
(Pe. Fábio de Melo)
"Quem não vê bem uma palavra
não pode ver bem uma alma."
(Fernando Pessoa)
Resumo
A gerência do trânsito nas cidades é um problema cada vez mais grave, seja pelo
crescente número de veículos e pessoas ou pela falta de infraestrutura dos órgãos
responsáveis. Além de evitar congestionamentos e a consequente redução na emissão de poluentes, outro ponto relevante é a segurança de motoristas e pedestres. O
controle semafórico tem papel fundamental para a redução das paradas e garantir que
o trânsito possa fluir. Algumas das técnicas utilizadas para a programação dos semáforos são obsoletas ou não conseguem suprir totalmente as condições das cidades.
Além disso, essa programação é uma tarefa difícil, principalmente quando a região em
questão possui um fluxo elevado e muitos semáforos para serem controlados. Este trabalho, inserido no âmbito do projeto Geoprocessamento e Inteligência Computacional
(GEOPROC) do Grupo de Pesquisa em Sistemas Inteligentes (GPSI) do Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG), propõe a modelagem e
implementação de uma ferramenta para a geração de tempos de semáforos por meio
de técnicas de Inteligência Computacional (IC). O desenvolvimento desse gerador foi
agregado ao simulador GISSIM, o qual permite que uma malha viária seja recuperada
diretamente do SIG OpenJUMP, evitando retrabalho no desenho da rede para a simulação. Os tempos dos semáforos são gerados por meio de Algoritmos Genéticos (AG)
e um algoritmo inspirado em sistemas imunológicos artificiais, o CLONal selection ALGorithm (CLONALG). Os experimentos foram realizados a partir de uma área real da
cidade de Porto Alegre, RS, com resultados comparados com a literatura e com os
tempos definidos por meio do Método de Webster, que é tradicionalmente utilizado na
área de engenharia de tráfego para a definição de ciclos de semáforos isolados. Os
resultados obtidos comprovam a eficiência das técnicas empregadas, bem como as
restrições do método em questão, que são discutidas no decorrer do texto.
PALAVRAS-CHAVE: SIG, simulação, inteligência computacional, semáforos, algoritmos genéticos, CLONALG.
Abstract
Traffic flow management and control has become a serious problem, because of the
increasing amount of circulating vehicles and people and the lack of infrastructure of
responsible agencies. Besides avoiding traffic jam and consequential pollution emissions, other relevant point is the security of drivers and pedestrians. The semaphorical
control has an essential role in order to reduce jam and guarantee the traffic flow.
Some techniques used to program traffic lights are obsoletes or not able to supply the
cities conditions totally. Besides, this programming is a hard task, mainly if a specific region has high vehicle flow rates and a lot of semaphores to be simultaneously
regulated. This work, inserted to the Geoprocessing and Computational Intelligence
Project (GEOPROC), by the Intelligent Systems Research Group (GPSI) from the Federal Center for Technological Education of Minas Gerais State, Brazil (CEFET–MG),
proposes the modeling and implementation of a traffic light generation tool by using
Computational Intelligence (IC) techniques. This analysis development has been coined to GISSIM simulator, which allows of a transportation system directly from the SIG
OpenJUMP, avoiding rework on its drawing. Traffic light cycles are generated by Genetic Algorithms (GA) and an algorithm inspired in artificial immunological systems, the
CLOnal selection ALGorithm. Experiments were carried out from a real area of Porto
Alegre, RS, and the results compared with the literature and the times generated by the
Webster Method, which is commonly used in the traffic engineering to generate isolated traffic lights cycles. Obtained results prove the efficiency of the used techniques
and the limitations of the method, which are discussed along the text.
KEYWORDS: GIS, simulation, computational intelligence, traffic lights, genetic algorithms, CLONALG.
Lista de Figuras
1
Exemplos de semáforos . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 27
2
Exemplo de um diagrama de tempos com 2 fases e 2 estágios . . . .
p. 28
3
Esquema de uma interseção de duas vias de mão única . . . . . . . .
p. 28
4
Diagrama de estágios para a interseção representada na Figura 3 . .
p. 29
5
Estudo do movimento × estágios para a interseção representada na
Figura 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 29
6
Comportamento do Tráfego assumido por Webster . . . . . . . . . . .
p. 30
7
Modelo do Tráfego Simplificado por Webster . . . . . . . . . . . . . .
p. 31
8
Representação do modelo de tráfego por meio de autômatos celulares p. 39
9
Área de estudo − Hipercentro de Belo Horizonte . . . . . . . . . . . .
p. 43
10
Representação dos dados cartográficos . . . . . . . . . . . . . . . . .
p. 45
11
Representação dos dados alfanuméricos . . . . . . . . . . . . . . . .
p. 46
12
Arquitetura do sistema JUMP . . . . . . . . . . . . . . . . . . . . . . .
p. 49
13
Tela principal do OpenJUMP . . . . . . . . . . . . . . . . . . . . . . .
p. 50
14
Algoritmo Genético básico . . . . . . . . . . . . . . . . . . . . . . . . .
p. 63
15
Exemplo do método de seleção por roleta . . . . . . . . . . . . . . . .
p. 64
16
Exemplo de recombinação a partir de um ponto de corte
. . . . . . .
p. 64
17
Exemplo de mutação em um bit
. . . . . . . . . . . . . . . . . . . . .
p. 64
18
Diagrama de blocos para o algoritmo CLONALG para o problema de
otimização
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 65
19
Pseudocódigo para o algoritmo CLONALG . . . . . . . . . . . . . . .
p. 65
20
Diagrama de pacotes das extensões desenvolvidas para o OpenJUMP p. 67
21
Diagrama de pacotes da arquitetura . . . . . . . . . . . . . . . . . . .
p. 72
22
Interface de configuração de cruzamentos . . . . . . . . . . . . . . . .
p. 73
23
Interface de definição do ciclo . . . . . . . . . . . . . . . . . . . . . . .
p. 74
24
Interface de definição dos grupos focais . . . . . . . . . . . . . . . . .
p. 74
25
Interface de configuração de parâmetros para as técnicas de IC. . . .
p. 75
26
Interface de configuração de parâmetros para o algoritmo CLONALG
p. 75
27
Interface do gerador de tempos . . . . . . . . . . . . . . . . . . . . . .
p. 76
28
Processo de geração e avaliação dos tempos gerados . . . . . . . . .
p. 77
29
Diagrama de tempos simplificado - cálculo do tempo de vermelho . .
p. 78
30
Representação de uma solução com duas variáveis . . . . . . . . . .
p. 80
31
Seleção aleatória dos pais e dos pontos de corte por variável . . . . .
p. 81
32
Combinação das informações dos pais
p. 81
33
Sub-rede analisada por Oliveira et al. (2005), com a identificação dos
. . . . . . . . . . . . . . . . .
cruzamentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 83
34
Imagem de satélite inserida no SIG OpenJUMP
. . . . . . . . . . . .
p. 83
35
Desenho da sub-rede no SIG OpenJUMP . . . . . . . . . . . . . . . .
p. 84
36
Desenho da sub-rede pelo simulador GISSIM . . . . . . . . . . . . . .
p. 85
37
Exemplo do Cálculo da Demanda . . . . . . . . . . . . . . . . . . . . .
p. 87
38
Resultado das Avaliações - Função de Avaliação sem Ponderação . .
p. 92
39
Resultado das Avaliações - Função de Avaliação com Ponderação . .
p. 96
Lista de Tabelas
1
Exemplo de Termos Sinônimos para Sistemas de Informação Geográfica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 47
2
Descrição dos pacotes do gerador de tempos . . . . . . . . . . . . . .
p. 71
3
Parâmetros AG/GISSIM-TL . . . . . . . . . . . . . . . . . . . . . . . .
p. 90
4
Parâmetros CLONALG/GISSIM-TL . . . . . . . . . . . . . . . . . . . .
p. 91
5
Veículos que deixaram a Simulação - FASP . . . . . . . . . . . . . . .
p. 91
6
Resultados - Av. Independência - Função de Avaliação sem Ponderação p. 92
7
Resultados - Rua Garibaldi - Função de Avaliação sem Ponderação .
8
Resultados - Av. Goethe (N/S) - Função de Avaliação sem Ponderação p. 93
9
Resultados - Av. Goethe (S/N) - Função de Avaliação sem Ponderação p. 94
10
Veículos que deixaram a Simulação - FACP . . . . . . . . . . . . . . .
11
Resultados - Av. Independência - Função de Avaliação com Pondera-
p. 93
p. 95
ções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 96
12
Resultados - Rua Garibaldi - Função de Avaliação com Ponderações
p. 97
13
Resultados - Av. Goethe (N/S) - Função de Avaliação com Ponderações p. 97
14
Resultados - Av. Goethe (S/N) - Função de Avaliação com Ponderações p. 98
15
Parâmetros AG/GISSIM-TL . . . . . . . . . . . . . . . . . . . . . . . .
16
Parâmetros CLONALG/GISSIM-TL . . . . . . . . . . . . . . . . . . . . p. 100
17
Veículos que deixaram a Simulação - Execução Rápida . . . . . . . . p. 100
18
Resultados - Av. Independência - Execução Rápida . . . . . . . . . . p. 100
19
Resultados - Rua Garibaldi - Execução Rápida . . . . . . . . . . . . . p. 101
20
Resultados - Av. Goethe (N/S) - Execução Rápida . . . . . . . . . . . p. 101
p. 99
21
Resultados - Av. Goethe (S/N) - Execução Rápida . . . . . . . . . . . p. 102
22
Resultados - Av. Independência - Análise Geral . . . . . . . . . . . . . p. 104
23
Resultados - Rua Garibaldi - Análise Geral . . . . . . . . . . . . . . . p. 104
24
Resultados - Av. Goethe (N/S) - Análise Geral
. . . . . . . . . . . . . p. 105
25
Resultados - Av. Goethe (S/N) - Análise Geral
. . . . . . . . . . . . . p. 105
Lista de Abreviaturas e Siglas
AG – Algoritmo Genético
API – Application Program Interface
BHTRANS – Empresa de Transporte e Trânsito de Belo Horizonte S/A
CEFET-MG – Centro Federal de Educação Tecnológica de Minas Gerais
CLONALG – CLONal selection ALGorithm
CSV – Comma-separated values
DENATRAN – Departamento Nacional de Trânsito
DRACULA – Dynamic Route Assignment Combining User Learning and microsimulAtion
GEOPROC – Geoprocessamento e Inteligência Computacional
GEPLO – Gerência de Planejamento e Controle Operacional
GISSIM – GIS Traffic Simulation
GISSIM-TL – GISSIM - Traffic Lights
GPSI – Grupo de Pesquisa em Sistemas Inteligentes
HCM 2000 – Highway Capacity Manual 2000
IA – Inteligência Artificial
IC – Inteligência Computacional
INPE – Instituto Nacional de Pesquisas Espaciais
ITACA – Intelligent Traffic Adaptive Control Agent
ITT – Impedância de Transposição do Trecho
JTS – Jump Topology Suite
RTIGIS – Real Time Intelligent Geographic Information System
SCATS – Sydney Coordinated Adaptive Traffic System
SCOOT – Split, Cycle and Offset Optimization Technique
SI – Sistemas Inteligentes
SIG – Sistema de Informação Geográfica
SPRING – Sistema de Processamento de Informações Georreferenciadas
TRANSYT – Traffic Network Study Tool
TSIS-CORSIM – Traffic Software Integrated System - Corridor Simulation
UTM – Universal Transversa de Mercator
VPH – Veículos por Hora
XML – eXtensible Markup Language
Sumário
1 INTRODUÇÃO
p. 19
1.1 O problema de pesquisa . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 21
1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 22
1.3 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 22
1.4 Organização da Dissertação . . . . . . . . . . . . . . . . . . . . . . .
p. 24
2 PROGRAMAÇÃO SEMAFÓRICA: Conceituação e Revisão Bibliográfica
p. 25
2.1 Conceituação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 25
2.1.1 Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 25
2.1.2 Termos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 26
2.1.3 O Método de Webster . . . . . . . . . . . . . . . . . . . . . . .
p. 29
2.2 Controle Semafórico . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 35
2.3 Estado-da-Arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 37
2.3.1 Trabalhos do Projeto GEOPROC . . . . . . . . . . . . . . . . .
p. 41
2.4 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 42
3 Sistemas de Informação Geográfica, Ferramentas de Simulação e Inteligência Computacional
p. 44
3.1 Sistemas de Informação Geográfica . . . . . . . . . . . . . . . . . . .
p. 44
3.1.1 Geoprocessamento . . . . . . . . . . . . . . . . . . . . . . . .
p. 45
3.1.2 Definições e Fundamentos . . . . . . . . . . . . . . . . . . . .
p. 46
3.1.3 OpenJUMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 48
3.2 Simulação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 50
3.2.1 Simulação de Tráfego . . . . . . . . . . . . . . . . . . . . . . .
p. 51
3.2.1.1
TRANSYT . . . . . . . . . . . . . . . . . . . . . . . .
p. 52
3.2.1.2
SimTraffic . . . . . . . . . . . . . . . . . . . . . . . . .
p. 53
3.2.1.3
TSIS-CORSIM . . . . . . . . . . . . . . . . . . . . . .
p. 53
3.2.1.4
DRACULA . . . . . . . . . . . . . . . . . . . . . . . .
p. 54
3.3 Inteligência Computacional . . . . . . . . . . . . . . . . . . . . . . . .
p. 55
3.3.1 Conceitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 55
3.3.2 Algoritmos Genéticos . . . . . . . . . . . . . . . . . . . . . . .
p. 56
3.3.2.1
Representação . . . . . . . . . . . . . . . . . . . . . .
p. 57
3.3.2.2
Definição da População Inicial . . . . . . . . . . . . .
p. 57
3.3.2.3
Função de Avaliação . . . . . . . . . . . . . . . . . .
p. 57
3.3.2.4
Seleção . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 58
3.3.2.5
Operadores Genéticos . . . . . . . . . . . . . . . . .
p. 58
3.3.2.6
Composição da Nova População . . . . . . . . . . . .
p. 59
3.3.3 CLONALG . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 59
3.3.3.1
Definições . . . . . . . . . . . . . . . . . . . . . . . .
p. 60
p. 62
4 DESENVOLVIMENTO DO GERADOR DE TEMPOS
p. 66
4.1 Simulador GISSIM . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 66
4.1.1 Área de Simulação . . . . . . . . . . . . . . . . . . . . . . . . .
p. 67
4.1.2 Interface Gráfica . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 68
4.1.3 Máquina de Simulação . . . . . . . . . . . . . . . . . . . . . .
p. 68
4.1.4 Veículos Instrumentados . . . . . . . . . . . . . . . . . . . . .
p. 69
4.1.5 Estatísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 69
4.1.6 Considerações . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 69
4.2 Gerador de Tempos . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 69
4.2.1 Extensões do Simulador . . . . . . . . . . . . . . . . . . . . . .
p. 70
4.2.2 Arquitetura do Gerador de Tempos . . . . . . . . . . . . . . . .
p. 71
4.2.3 Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 72
4.2.4 Módulo de Geração de Tempos . . . . . . . . . . . . . . . . . .
p. 73
p. 78
5 EXPERIMENTOS
p. 79
5.1 Implementação das Técnicas de Inteligência Computacional . . . . .
p. 79
5.1.1 Representação de uma solução . . . . . . . . . . . . . . . . .
p. 79
5.1.2 Algoritmos Genéticos . . . . . . . . . . . . . . . . . . . . . . .
p. 80
5.1.3 CLONALG . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
p. 82
5.2 Cenário dos Experimentos . . . . . . . . . . . . . . . . . . . . . . . .
p. 82
5.2.1 Preparação do Ambiente . . . . . . . . . . . . . . . . . . . . .
p. 82
5.2.2 Função de Avaliação . . . . . . . . . . . . . . . . . . . . . . . .
p. 85
5.2.3 Definição dos Tempos pelo Método de Webster . . . . . . . . .
p. 86
5.3 Resultados Práticos e Análises . . . . . . . . . . . . . . . . . . . . . .
p. 88
5.3.1 Considerações Iniciais . . . . . . . . . . . . . . . . . . . . . . .
p. 88
5.3.2 Parâmetros para os experimentos com variação da ponderação da Função de Avaliação . . . . . . . . . . . . . . . . . . .
p. 90
5.3.3 Resultados com Função de Avaliação sem Ponderações . . .
p. 90
5.3.3.1
Resultados . . . . . . . . . . . . . . . . . . . . . . . .
p. 91
5.3.3.2
Considerações sobre os Resultados . . . . . . . . . .
p. 94
5.3.4 Resultados com Função de Avaliação com Ponderações . . .
p. 95
5.3.4.1
Resultados . . . . . . . . . . . . . . . . . . . . . . . .
p. 95
5.3.4.2
Considerações sobre os Resultados . . . . . . . . . .
p. 98
5.3.5 Resultados com tempo de execução rápida . . . . . . . . . . .
p. 99
5.3.5.1
Parâmetros . . . . . . . . . . . . . . . . . . . . . . . .
p. 99
5.3.5.2
Resultados . . . . . . . . . . . . . . . . . . . . . . . .
p. 99
5.3.5.3
Considerações sobre os Resultados . . . . . . . . . . p. 102
5.3.6 Análise Geral dos Resultados . . . . . . . . . . . . . . . . . . . p. 102
5.4 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 106
6 CONCLUSÃO
p. 107
6.1 Discussões Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 107
6.2 Contribuições do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . p. 108
6.3 Propostas para Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . p. 109
Referências
p. 111
19
1
INTRODUÇÃO
As cidades, atualmente, enfrentam grandes problemas com o controle do trânsito.
Esse problema agrava-se cada dia mais em virtude do crescente número de veículos e
pedestres. A explosão do número de pessoas e veículos é cada vez maior e, portanto,
mais crítica em capitais e regiões metropolitanas. Em Belo Horizonte, MG, conforme a
BHTRANS (2009), a frota de veículos registrada apresentou um crescimento de 35%
entre 2004 e 2008, resultando numa relação de um veículo para cada 2,2 habitantes.
É ressaltado ainda o avanço do número de motocicletas, que cresceu 75% no mesmo
período, mais que o dobro do crescimento do número total de veículos. Em 2008, o
número total de veículos nessa capital superou 1 milhão. Machado (2009) relata estudos que mostram que o transporte público na capital tem que melhorar para se evitar
o caos, segundo o autor. De janeiro até o fim de maio de 2009 foram emplacados na
cidade 34.535 automóveis, sem a substituição da frota antiga. No Brasil, no primeiro
semestre foram vendidos 1,45 milhão de carros. Segundo estudo da Fundação Dom
Cabral, se nada for feito, em 15 anos o trânsito na capital mineira estagnará. Outro
exemplo é o da capital do estado de São Paulo, que, segundo o DETRAN-SP (2009),
atingiu no mês de junho de 2009 uma frota de mais de 6,5 milhões de veículos.
A organização do trânsito pode acontecer devido a situações especiais, como
eventos culturais e esportivos, manifestações, obras, dentre outros. Uma demonstração disso é fato do Brasil sediar a Copa do Mundo de Futebol em 2014. Isso implicará em mudanças, conforme descrito por Martins (2009), no trânsito e no transporte
público das cidades envolvidas, como a reformulação do centro de Belo Horizonte.
Faixas exclusivas para coletivos e novas calçadas estão entre as mudanças planejadas. Trechos de ruas e avenidas sofrerão intervenções para privilegiar pedestres e
abrigar ônibus rápidos.
Um elemento importante na gerência do tráfego é o controle semafórico, que é
empregado em interseções nas quais exista conflito de fluxo de tráfego, garantindo a
1 INTRODUÇÃO
20
segurança e aplicado com o intuito de reduzir atrasos. Nesse ponto, a definição dos
tempos semafóricos deve ser feita de modo bem cuidadoso. Luna (2003) afirma que o
tempo de verde alocado deve passar por critérios rigorosos, uma vez que tempos mal
ajustados implicam em atrasos compulsórios, senão em congestionamentos evitáveis.
A principal dificuldade na programação semafórica está na variação do fluxo de tráfego
ao longo do tempo, requerendo que a alocação dos tempos de verde também varie
para se adequar a essa demanda variável.
Nesse contexto, uma engenharia de tráfego eficiente e capaz de amenizar o impacto desse crescimento torna-se imprescindível. Para isso, soluções práticas, rápidas e eficientes são necessárias para que a gerência e planejamento do tráfego sejam
realizadas de modo que se garanta a fluidez e a segurança.
Os Sistemas de Informações Geográficas (SIG) permitem a modelagem, processamento e análise de informações espaciais. Foote e Lynch (1998)1 , citados em Silva
(2006, p. 17), afirmam que os SIG fornecem ferramentas poderosas para tratar de
assuntos geográficos e ambientais. Esses sistemas permitem, por meio do uso do
computador, organizar a informação sobre uma determinada região como um conjunto de mapas, cada um deles exibindo informações a respeito de uma característica
da região em estudo.
O Grupo de Pesquisa em Sistemas Inteligentes (GPSI) do Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG) promove, em uma de suas linhas de
pesquisa, o desenvolvimento de projetos que utilizam técnicas de inteligência computacional aplicadas a SIG convencionais. Os trabalhos desenvolvidos por esse grupo
atualmente utilizam o OpenJUMP (OPENJUMP, 2009), que é um SIG livre e de código
aberto, escrito em Java (SUN MICROSYSTEMS, INC., 2008) e extensível, permitindo que
novas funcionalidades sejam adicionadas pelo acoplamento de novos módulos (plugins).
A capacidade de extensibilidade desse SIG permitiu que Silva (2006) realizasse
a modelagem e implementação de uma ferramenta inteligente, utilizando inferência
Fuzzy, que determina o melhor caminho de tráfego entre dois pontos de Belo Horizonte. Nesse trabalho, informações como o número de veículos por faixa e por horário
e o comprimento da via são sintetizadas em um atributo denominado Impedância de
1
FOOTE, Kenneth E.; LYNCH, Margaret (1998). Sistemas de Informação Geográfica como uma
Tecnologia Integradora: Contexto, Conceitos e Definições. In: Courseware em Ciências Cartográficas
- Unesp - Campus de Presidente Prudente. Disponível em: http://www.multimidia.prudente.unesp.br/
arlete/hp_arlete/courseware/intgeo.htm. Acessado em 13/04/2006.
1.1 O problema de pesquisa
21
Transposição do Trecho (ITT), o qual mede a dificuldade de se transpor determinado
trecho, como um quarteirão. Essa ferramenta realiza a aquisição de dados, a geração
do atributo fuzzy e a atualização da base de dados automaticamente, em tempo real,
e de modo integrado ao ambiente de SIG.
Com o apoio também do OpenJUMP, Saliba Neto (2009) desenvolveu uma ferramenta de simulação microscópica de tráfego urbano, denominada GIS Traffic Simulation (GISSIM), na qual é possível reproduzir situações reais de trânsito e os resultados
serem utilizados no auxílio à tomada de decisão por engenheiros de tráfego.
1.1
O problema de pesquisa
A administração do trânsito não é uma tarefa trivial e requer a utilização de várias
metodologias a fim de garantir o fluxo de veículos com segurança e sem atrasos. Os
órgãos responsáveis pela engenharia de tráfego, em geral, necessitam de recursos
tecnológicos práticos e eficientes que permitam a definição de planos semafóricos
consistentes. Os simuladores de tráfego disponíveis no mercado requerem que a
malha viária seja desenhada, ao passo que esta pode ser recuperada diretamente a
partir de um SIG. O redesenho no simulador pode implicar em erros e comprometer os
resultados, além do tempo gasto para essa operação. Outra questão relevante é que
esses simuladores são desenvolvidos no exterior, utilizando outras regras e conceitos
que não os definidos para o país. Além de tudo, o que se deve ponderar também é o
alto investimento financeiro, o que uma ferramenta baseada em software livre não tem
ou é bem menor.
Os projetos do Grupo de Pesquisa em Sistemas Inteligentes (GPSI) do Centro Federal de Educação Tecnológica de Minas Gerais (CEFET-MG) destinados a Geoprocessamento e Inteligência Computacional (GEOPROC) têm por objetivo o desenvolvimento de metodologias baseadas em sistemas inteligentes para tratamento, solução
de problemas e aperfeiçoamento da operação de SIG. Nesse contexto, Saliba Neto
(2009) desenvolveu uma ferramenta com recursos para simulação de microrregiões,
na qual a malha viária é recuperada diretamente do SIG OpenJUMP.
Como o controle semafórico tem papel importante na gerência de trânsito, o problema de pesquisa abordado neste trabalho consiste na geração de tempos de semáforos por meio de inteligência computacional. Algumas das técnicas utilizadas para
a definição desses tempos nos sistemas de operação atuais são antigas e/ou não
1.2 Objetivos
22
atendem as necessidades das cidades. Além disso, algumas das propostas encontradas na literatura para resolução desse problema não incorporam a utilização de um
SIG. A resolução exata do problema de geração de tempos é uma tarefa difícil e, até
então, desconhecida na literatura. A utilização de outras técnicas de inteligência computacional para geração dos tempos semafóricos pode ser realizada, não se limitando
somente ao que é implementado nas ferramentas existentes, como por exemplo, o
SimTraffic e o TRANSYT.
1.2
Objetivos
O presente trabalho propõe o desenvolvimento de recursos para que a definição
dos tempos de semáforos seja realizada em um SIG, incorporado ao simulador de
microrregiões desenvolvido por Saliba Neto (2009). Isso, além de evitar que as redes
viárias tenham que ser redesenhadas em outros simuladores, permitirá a abertura
para o desenvolvimento e implementação de diversas técnicas de inteligência computacional. Outro fator relevante é a possibilidade de aplicação de técnicas de análise e
avaliações espaciais presentes no SIG.
O objetivo geral deste trabalho é a modelagem e implementação de uma ferramenta que utilize técnicas de inteligência computacional, baseada em software livre,
para a geração dos tempos semafóricos em um SIG convencional. Este trabalho se
propõe então aos seguintes objetivos específicos:
∙ Modelar e implementar um plugin que permita a geração de tempos semafóricos,
utilizando técnicas de inteligência computacional;
∙ Integrar esse plugin ao OpenJUMP e ao simulador desenvolvido por Saliba Neto
(2009);
∙ Validar o plugin desenvolvido com a execução de experimentos práticos em alguma região de interesse.
1.3
Metodologia
O objeto de pesquisa deste trabalho pode ser classificado, conforme Silva e Menezes (2001), em relação à sua natureza como sendo do tipo aplicada, pois objetiva
1.3 Metodologia
23
gerar conhecimentos práticos para a solução de problemas específicos.
Em relação ao modo de abordagem do problema, a pesquisa é classificada como
qualitativa, considerando a avaliação que será realizada acerca da incorporação da
geração dos tempos ao SIG. É também uma pesquisa quantitativa, pois os resultados
dos tempos gerados serão classificados e analisados.
Os objetivos da pesquisa a classificam como exploratória, pois visa investigar o
problema com vistas a torná-lo explícito ou a construir hipóteses. (SILVA; MENEZES,
2001). Nesse contexto, a hipótese que a pesquisa pretende comprovar é a seguinte:
É possível e viável a geração de tempos semafóricos
em SIG convencionais utilizando técnicas de inteligência computacional.
Os passos, então, para consecução deste trabalho são assim definidos:
∙ Revisão da literatura: pesquisar e examinar a literatura sobre os seguintes tópicos: Geoprocessamento, Sistema de Informação Geográfica (SIG), Inteligência
Computacional, Semáforos, Programação Semafórica, Controle Semafórico e
Padrões de Projeto de software;
∙ Levantamento de frameworks: pesquisar, estudar, testar e avaliar a viabilidade
de utilização de alguns frameworks livres e de código aberto, escritos em Java,
que implementem técnicas de inteligência computacional;
∙ Desenvolvimento do gerador de tempos: desenvolver um componente de software que realize a geração de tempos semafóricos, que seja extensível e que
utilize técnicas de inteligência computacional;
∙ Integração com o SIG e o Simulador: modelar e implementar um componente
de software que realize a integração do gerador de tempos com o SIG, para definição das interseções semaforizadas e demais parâmetros, e com o Simulador,
desenvolvido por Saliba Neto (2009), para análise e avaliação dos resultados;
∙ Validação do gerador de tempos: realizar testes para validação dos tempos gerados e comparar os resultados obtidos com algum trabalho correlato na literatura;
∙ Análise e discussão: avaliar os resultados obtidos, com as devidas considerações e ponderações.
1.4 Organização da Dissertação
1.4
24
Organização da Dissertação
O restante deste trabalho é organizado como se segue. Os conceitos sobre semáforos e programação semafórica são descritos no capítulo 2, como também os
trabalho correlatos na literatura a partir do estado-da-arte são apresentados. Com o
intuito de contextualizar o leitor, no capítulo 3 os conceitos e recursos necessários
para a execução deste trabalho são elucidados, como Geoprocessamento e Sistemas
de Informação Geográfica, Simulação e Inteligência Computacional (IC). O desenvolvimento de gerador de tempos semafóricos é relatado no capítulo 4. No capítulo 5,
os experimentos e a avaliação prática do simulador é apresentada. A conclusão do
trabalho e propostas de trabalhos futuros são descritas no capítulo 6.
25
2
PROGRAMAÇÃO SEMAFÓRICA:
Conceituação e Revisão
Bibliográfica
Neste capítulo, serão apresentados os conceitos sobre semáforos e programação
semafórica, bem como as técnicas e os métodos utilizados no apoio à definição dos
tempos e alguns SIG. Este capítulo também abordará o controle semafórico e suas
classificações. O estado-da-arte apresentará os trabalhos correlatos na literatura, com
as devidas considerações.
2.1
Conceituação
Nesta seção é apresentada a definição dos termos empregados neste trabalho,
como também as referências para a programação semafórica.
2.1.1
Referências
Dentre as referências utilizadas na engenharia de tráfego e programação semafórica, de modo geral, tem-se o Manual de Semáforos do Departamento Nacional de
Trânsito do Brasil (DENATRAN, 1984) e o Highway Capacity Manual 2000 (HCM 2000)
(TRB, 2000).
O primeiro apresenta os conceitos básicos, critérios para implantação de semáforos e utiliza como método para regulagem de semáforos isolados o Método de Webster. Conforme cita o DENATRAN (1984), ele foi escolhido por se tratar de um método
completo e detalhado, que possibilita a determinação dos tempos verdes e do comprimento do ciclo, causando o menor atraso geral possível na interseção. Este manual,
apesar de antigo, ainda está em vigor e é referência para o cálculo semafórico no Bra-
2.1 Conceituação
26
sil. Segundo o DENATRAN, ele está sendo atualizado e uma nova versão está prevista
para o segundo semestre de 2009, consistindo no Volume V do Manual Brasileiro de
Sinalização de Trânsito.
O HCM 2000 já é mais abrangente e muito utilizado, pois várias aplicações de
simulação de trânsito e programação semafórica têm esse manual como referência
para os cálculos e definição dos parâmetros e utilizam também o Método de Webster,
com algumas modificações.
2.1.2
Termos
Na definição dos termos empregados neste trabalho será utilizada como referência, conforme abordado no tópico anterior, o Manual de Semáforos do Departamento
Nacional de Trânsito do Brasil (DENATRAN, 1984). Esses termos serão abordados concisamente, objetivando a contextualização do leitor. Para maiores informações e aprofundamento no assunto, sugere-se a leitura da referência em questão.
O semáforo é um dispositivo de controle de tráfego que, por meio de indicações
luminosas transmitidas para motoristas e pedestres, alterna o direito de passagem de
veículos e/ou veículos e pedestres em interseções de duas ou mais vias. Compõese de focos luminosos afixados em grupos ao lado da via ou suspensos sobre ela, a
partir de elementos de sustentação (postes). Exemplos desses semáforos podem ser
observados na Figura 1.
O termo movimento é usado para identificar a origem e o destino de veículos e/ou
pedestres. Graficamente, os movimentos são representados por traços e seta; o traço
indica a direção, e a seta o sentido; traço e barra indicam movimento interrompido.
Dois movimentos são conflitantes entre si quando se cruzam numa interseção.
Movimentos convergentes são aqueles que possuem origens diferentes e mesmo
destino; contrariamente, os movimentos divergentes têm mesma origem, porém destinos diferentes. Os trechos de via que convergem para a interseção são denominados
aproximações do cruzamento.
Geralmente, a sequência de indicação de cores de um semáforo é verde (direito de
passagem), amarelo, vermelho e novamente verde. Esta sequência, aplicada a uma
ou mais correntes de tráfego (movimento), é denominada fase. O tempo total, em segundos, para a completa sequência de sinalização em uma interseção, é denominado
ciclo. Um dos vários períodos de tempo dentro do ciclo é denominado estágio ou
2.1 Conceituação
27
Figura 1: Exemplos de semáforos
(a) Semáforo Veicular e (b) Semáforo de Pedestres
Adaptado de Wikipedia (2009)
intervalo, e durante esse período as indicações luminosas do cruzamento como um
todo não mudam de aspecto, e uma ou mais correntes de tráfego e/ou pedestres têm
direito de passagem. O tempo decorrido entre o fim do verde de uma fase, que está
perdendo o direito de passagem, e o início de outra que está ganhando é denominado
período entreverdes (intergreen). No Brasil, normalmente, o período entreverdes é
igual ao tempo de amarelo.
O diagrama de tempos associa os instantes de mudança dos estágios com a
sequência de cores e duração das fases. Além disso, é possível verificar a relação
entre fase, estágio e ciclo. A situação de entreverdes (tempo de amarelo), na maioria
das vezes, não é considerada efetivamente um estágio. A Figura 2 ilustra os conceitos
apresentados acima.
O número de fases de uma interseção depende, basicamente, do número de aproximações, dos volumes de conversão e dos conflitos entre os movimentos. Na maioria
dos cruzamentos, o número de fases é igual a 2. Em termos de duração, o tempo de
verde de uma fase geralmente não deve ser inferior a 15 segundos. A Figura 3 apresenta o esquema de uma interseção de duas vias de mão única, com os movimentos
permitidos.
O diagrama de estágios é uma representação esquemática da sequência de mo-
2.1 Conceituação
28
Figura 2: Exemplo de um diagrama de tempos com 2 fases e 2 estágios
Adaptado de DENATRAN (1984)
Figura 3: Esquema de uma interseção de duas vias de mão única
vimentos permitidos e proibidos para cada intervalo do ciclo. A Figura 4 apresenta
o diagrama de estágios para a interseção definida na figura 3, com os movimentos
simultâneos.
A tabela de movimentos × estágios relaciona para cada estágio do diagrama de
estágios quais os movimentos permitidos, e a partir disso identifica quantos grupos
focais (grupos de semáforos) são necessários para operar o cruzamento. Pelo conhecimento dos grupos focais, pode-se construir o diagrama de tempos (ver Figura 2),
pois a cada grupo focal está associada uma fase. O estudo do movimento referente à
interseção representada acima é apresentado na Figura 5.
A programação semafórica consiste na definição dos parâmetros de operação
de um semáforo ao longo do tempo. Esses parâmetros devem ser definidos cuidado-
2.1 Conceituação
29
Figura 4: Diagrama de estágios para a interseção representada na Figura 3
Figura 5: Estudo do movimento × estágios para a interseção representada na Figura
3
samente, pois podem implicar em geração de filas, atrasos, desrespeito por parte dos
condutores, aumento da poluição, redução da segurança, dentre outros.
Como medida de segurança a ser adotada com o objetivo de redução de acidentes, Monteiro (2008) afirma que a semaforização deve ser criteriosa e o dimensionamento dos ciclos o mais apropriado possível. Afirma também que uma programação
semafórica deve conter os seguintes dados, para cada interseção (MONTEIRO, 2008):
∙ número e sequência de estágios;
∙ tempo de ciclo;
∙ temporização de estágios e fases (tempos de verde, amarelo e vermelho);
∙ tempos de vermelho total;
∙ defasagens (sincronização com outras interseções) - offset
2.1.3
O Método de Webster
O método proposto por Webster na década de 1950, referenciado por diversos autores como Saka, Anandalingam e Garber (1986), O’Flaherty (1986), Villalobos (2001),
2.1 Conceituação
30
Niittymäki (2002), Luna (2003), Cervantes (2005), Lima (2005), Monteiro (2008), dentre outros; e ainda, amplamente descrito no Manual de Semáforos do Departamento
Nacional de Trânsito do Brasil (DENATRAN, 1984) e no HCM 2000 (TRB, 2000) é utilizado no cálculo de ciclos ótimos em semáforos isolados e de tempo fixo. Um ciclo
é ótimo na perspectiva de Webster quando esse minimiza o atraso total na interseção. Webster desenvolveu um modelo de tráfego e fez simulações em computador de
uma interseção controlada por semáforo de tempo fixo, operando sob condições de
tempos de verde, tempo de ciclo, fluxo de tráfego e fluxo de saturação que cobriam
praticamente todas as situações possíveis em interseções. Nesta seção serão abordadas apenas os conceitos e fórmulas necessários para a execução dos experimentos
deste trabalho, tendo como referência o DENATRAN (1984). Para um melhor aprofundamento desses conceitos, bem como as discussões sobre as fórmulas, sugere-se
a leitura das referências anteriormente descritas, especialmente a utilizada para as
descrições a seguir.
Luna (2003) alega que, mesmo o método sendo antigo, ele fornece a base de
todos os métodos de cálculo de tempos para semáforos, o que justifica ter sido adotado pelo DENATRAN na determinação dos tempos fixos de semáforos isolados. O
comportamento de desmanche de fila adotado na definição desse método pode ser
observado na figura 6.
Figura 6: Comportamento do Tráfego assumido por Webster
Adaptado de Luna (2003)
Webster considerou que quando o período de verde se inicia, os veículos levam
algum tempo para começar seu deslocamento e acelerar até sua velocidade normal
2.1 Conceituação
31
de viagem, mas depois de alguns segundos, a fila de veículos descarrega a uma taxa
mais ou menos constante chamada de fluxo de saturação. Ou seja, o tempo de verde
que é oferecido não é totalmente utilizado.
A curva real foi simplificada e transformada em um retângulo, que corresponde ao
número total de veículos que atravessam o sinal na fase com direito de passagem,
conforme pode ser observado na Figura 7.
Figura 7: Modelo do Tráfego Simplificado por Webster
Adaptado de Luna (2003)
O fluxo de saturação é definido por DENATRAN (1984) como sendo o fluxo que
seria obtido se houvesse uma fila de veículos na aproximação e a ela fossem dados
100% de tempo de verde do cruzamento (escoamento ininterrupto). Normalmente, o
fluxo de saturação é expresso em unidade de veículos/hora de tempo verde (veíc./htv).
Ele depende de diversos fatores, dentre os quais, os mais influentes são: geometria
da interseção (principalmente largura), número de veículos que fazem a conversão
à esquerda e à direita, declividade da via, estacionamento de veículos e presença de
veículos comerciais (ônibus e caminhão). Para aproximações padrões (sem veículos
estacionados, nem movimentos de conversão à esquerda e com até 10% de conversão à direita), o fluxo de saturação pode ser estimado a partir da Equação (2.1). Essa
fórmula é válida para larguras de vias compreendidas entre 5, 5 e 18 metros. Para valores inferiores, os fluxos são fixos e apresentados numa tabela em DENATRAN (1984,
p. 142).
𝑆 = 525 ⋅ 𝐿
(2.1)
2.1 Conceituação
32
sendo:
𝑆: fluxo de saturação em veículos equivalentes1 por hora de tempo verde (𝑉𝑒𝑞 /ℎ𝑡𝑣);
𝐿: largura da aproximação, em metros (m).
O DENATRAN (1984) apresenta a decomposição dos tempos em que o movimento é autorizado (verde + amarelo) em dois períodos: período de verde efetivo,
no qual ocorre o escoamento de veículos na taxa de saturação e tempo perdido
(tempo morto) devido às reações dos motoristas no início e no fim do tempo de verde
e durante o qual não há travessia de veículos, ou seja, o fluxo é zero. O tempo perdido
ou tempo morto, para uma dada fase do cruzamento, é definido como a diferença entre o verde efetivo e a soma dos tempos de verde e amarelo. O tempo perdido total no
cruzamento durante um ciclo é igual à soma dos tempos perdidos para cada uma de
suas fases. Caso haja vermelho geral, este tempo também é considerado como perdido. A expressão então é dada pela Equaçao 2.2. Quando não é possível determinar
o tempo perdido de cada fase, um valor aproximado para o tempo perdido total pode
ser adotado como numericamente igual à soma dos tempos amarelos das fases
envolvidas.
𝑇𝑝 =
𝑛
∑
𝑖=1
𝑙𝑖 +
𝑛
∑
(𝑙 − 𝑡𝑎𝑖 )
(2.2)
𝑖=1
sendo:
𝑇𝑝 : tempo perdido total do cruzamento, por ciclo (em segundos);
𝑙: período de entreverdes (em segundos);
𝑙𝑖 : tempo perdido da fase 𝑖 (em segundos);
𝑡𝑎𝑖 : tempo de amarelo da fase 𝑖 (em segundos);
𝑛: número de fases.
A taxa de ocupação (𝑦) de uma aproximação, definida por DENATRAN (1984), é a
relação entre a demanda de tráfego e o fluxo de saturação. Ela é uma medida absoluta
1
A cada tipo de veículo (ônibus, caminhão leve e/ou pesado, motocicleta, dentre outros) corresponde
um fator de equivalência, determinado em função da relação do espaço ocupado entre este e o veículopadrão (automóvel de passeio – fator = 1) (DENATRAN, 1984, p. 142).
2.1 Conceituação
33
da solicitação de tráfego numa aproximação, a partir da Equação (2.3). Essa taxa é a
medida absoluta da solicitação de tráfego num aproximação. A taxa de ocupação da
aproximação crítica é aquela que apresenta o maior valor de 𝑦 (𝑦𝑐𝑟𝑖𝑡 ) para a fase em
questão.
𝑦𝑖 =
𝑞𝑖
𝑆𝑖
(2.3)
sendo:
𝑦𝑖 : taxa de ocupação da aproximação 𝑖;
𝑞𝑖 : demanda (fluxo horário) da aproximação 𝑖 (𝑉𝑒𝑞 /ℎ);
𝑆𝑖 : fluxo de saturação da aproximação 𝑖 (𝑉𝑒𝑞 /ℎ𝑡𝑣).
O ciclo mínimo para operação de um cruzamento pode ser definido pela Equação
(2.4). No ciclo mínimo, o tempo total de verde efetivo é suficiente apenas para escoar
a fila formada pelos veículos que chegam, durante o ciclo, na aproximação crítica de
cada fase do cruzamento (DENATRAN, 1984).
𝐶𝑚𝑖𝑛 =
𝑇𝑝
1−𝑌
(2.4)
sendo:
𝐶𝑚𝑖𝑛 : tempo de ciclo mínimo (em segundos);
𝑇𝑝 : tempo perdido total (em segundos), dado pela Equação (2.2);
𝑌 : o somatório das taxas de ocupação críticas de cada fase do cruzamento,
definido pela Equação (2.5).
𝑌 =
𝑛
∑
𝑦𝑖𝑐𝑟𝑖𝑡
(2.5)
𝑖=1
Webster obteve uma fórmula para o tempo de ciclo que minimize o atraso total na
interseção, sendo esse tempo denominado tempo de ciclo ótimo, a é apresentada
pela Equação (2.6).
2.1 Conceituação
34
𝐶𝑂 =
1, 5 ⋅ 𝑇𝑝 + 5
1−𝑌
(2.6)
sendo:
𝐶𝑂 : tempo de ciclo ótimo2 (em segundos);
𝑇𝑝 : tempo perdido total (em segundos);
𝑌 : somatório das taxas de ocupação da aproximação crítica (𝑦𝑐𝑟𝑖𝑡 ) de cada fase
do cruzamento.
Após o cálculo do tempo de ciclo ótimo, é necessário determinar os tempos de
verde para cada fase do cruzamento, o qual pode ser obtido por meio da Equação
(2.7) (DENATRAN, 1984).
𝑔𝑒𝑓𝑖 =
𝑦𝑖𝑐𝑟𝑖𝑡
⋅ (𝐶𝑂 − 𝑇𝑝 )
𝑌
(2.7)
sendo:
𝑔𝑒𝑓𝑖 : tempo de verde efetivo da fase 𝑖 (em segundos);
𝑦𝑖𝑐𝑟𝑖𝑡 : taxa de ocupação crítica da fase 𝑖;
𝑌 : somatório das taxas de ocupação da crítica das fases do cruzamento;
𝐶𝑂 : tempo de ciclo ótimo (em segundos);
𝑇𝑝 : tempo perdido total no ciclo (em segundos).
Definidos, então, os tempos de verde efetivos, define-se os valores reais de verde,
os quais serão implantados no controlador de tráfego do cruzamento, a partir da Equação (2.8).
𝑔𝑖 = 𝑔𝑒𝑓𝑖 + 𝑙𝑖 − 𝑡𝑎𝑖
(2.8)
sendo:
A referência em questão utiliza 𝐶𝑂 e não 𝐶 ∗ , como abordado na literatura em geral nos problemas
de otimização para a definição de ótimo.
2
2.2 Controle Semafórico
35
𝑔𝑖 : verde real da fase 𝑖 (em segundos);
𝑔𝑒𝑓𝑖 : tempo de verde efetivo da fase 𝑖 (em segundos);
𝑙𝑖 : tempo perdido na fase 𝑖 (em segundos);
𝑡𝑎𝑖 : tempo de amarelo na fase 𝑖 (em segundos);
O método de cálculo de ciclo ótimo apresenta muitas restrições, dentre as quais o
próprio Webster (apud LUNA, 2003, p. 15) reconheceu:
Se o fluxo de saturação cai ao longo do verde (por exemplo, devido
ao forte movimento de conversão à esquerda), essa fórmula não é
apropriada e um método mais complexo é necessário para se obter
um tempo de ciclo adequado.
Luna (2003) afirma que, apesar das restrições, outras propostas de modelos não
vieram a contribuir significativamente com uma melhor estimativa do atraso em interseções. O método em questão foi apresentado superficialmente apenas para demonstrar
a dificuldade de se determinar os tempos de semáforos, o que justifica a aplicação de
técnicas de inteligência computacional.
2.2
Controle Semafórico
Segundo o DENATRAN (1984), três variáveis devem ser ajustadas ao longo do
tempo : percentual de verdes de cada fase, tempo de ciclo e defasagem. O modo
pelo qual essas variáveis são definidas ao longo do tempo permite a classificação do
controle semafórico em tempo fixo, atuado e adaptativo.
Cervantes (2005) define o controle semafórico de tempo fixo como aquele que
é baseado em dados históricos da média da demanda de fluxo para um período de
tempo em que este plano seja operacional. A elaboração destes planos é realizada
a partir de contagens de veículos. Diferentes planos podem ser gerados para diferentes períodos do dia ou dias da semana para refletir o comportamento estatístico
do fluxo de veículos. No entanto, os planos fixos não se adaptam às alterações de
demanda que ocorrem em tempo real no dia-a-dia do tráfego. Luna (2003) alerta que
essa técnica exige que se faça uma previsão de médio prazo do comportamento do
tráfego. Os ajustes dos tempos devem ser definidos para condições próximas das
piores situações esperadas dentro do período de cada plano.
2.2 Controle Semafórico
36
No sistema de controle atuado, os tempos dos semáforos são atualizados conforme o fluxo atual do tráfego, monitorado por meio de detectores veiculares. Luna
(2003) define esse sistema como uma evolução do tempo fixo, porém seus planos
continuam sendo pré-calculados e implementados em função do horário e do dia da
semana.
Já no sistema adaptativo, os tempos são calculados e atualizados em tempo real
conforme a dinâmica do trânsito, identificada por meio de detectores. Dentre esses
sistemas, pode-se citar o australiano SCATS (Sydney Coordinated Adaptive Traffic
System), o britânico SCOOT (Split, Cycle and Offset Optimization Technique) e o espanhol ITACA (Intelligent Traffic Adaptive Control Agent).
Luna (2003) descreve o SCATS como um exemplo de tecnologia híbrida, na qual
cada controlador funciona como um sistema adaptativo sensível ao fluxo de tráfego,
executando planos gerados por um computador central. A formação de microrregiões
de tráfego é dinâmica, visto que o próprio sistema pode fundi-las ou separá-las para
melhor operação do sistema.
O mesmo autor, citando Wood (1993)3 , define o SCOOT como um sistema que
mede o fluxo de tráfego passando pelos detectores a montante da retenção e faz uma
estimativa da formação de filas assumindo que os veículos trafegam a uma velocidade
constante do laço-detector até a faixa de retenção. Enquanto o sinal está vermelho, o
sistema modela o crescimento da fila e, ao ficar verde, o sistema simula os veículos
em fila sendo descarregados a uma taxa constante.
O ITACA foi desenvolvido pela empresa espanhola Telvent e trabalha de modo
similar ao SCOOT. Ele adapta os planos semafóricos ao estado corrente do tráfego
e os ajustes podem ser imediatamente implementados. Ele não precisa de planos
pré-calculados para trabalhar, visto que as variáveis são calculadas e implementadas
em tempo real, de acordo com a parâmetros medidos das condições atuais de tráfego
(TELVENT, 2008).
Segundo a Gerência de Planejamento e Controle Operacional (GEPLO), um departamento da Empresa de Transporte e Trânsito de Belo Horizonte S/A (BHTRANS),
no ano de 2008, o controle inteligente e adaptativo em tempo real do tráfego, na região
central da cidade de Belo Horizonte, estava sendo implantado pelo ITACA. A GEPLO
informou nessa ocasião que esse controle semafórico adaptativo em tempo real não
3
WOOD, K. (1993) Urban Traffic Control:
Crowthorne, Berkshire.
System Review.
Transport Research Laboratory.
2.3 Estado-da-Arte
37
está em funcionamento, pois está em fase de manutenção. A empresa utilizava os
dados captados pelos detectores veiculares e, por meio de pesquisas de tráfego realizadas offline, definia os planos semafóricos.
2.3
Estado-da-Arte
Diversos trabalhos envolvendo a definição de tempos semafóricos podem ser encontrados na literatura. Dentre esses, alguns podem ser destacados por sua relevância e modo com que o problema foi abordado.
López et al. (1999) aplicaram redes neurais artificiais4 como ferramenta para a
otimização apenas da defasagem de tempos (offset-time) em dois semáforos consecutivos. O treinamento da rede neural, bem como os resultados, são avaliados em
um simulador construído especificamente para a solução do problema. Em uma abordagem similar, Febbraro, Giglio e Sacco (2002) empregaram Redes de Petri5 com o
intuito de otimizar também os tempos de defasagem. Nesses trabalhos, nota-se que
a otimização é limitada apenas ao tempo de defasagem, a qual pode ser realizada de
maneira mais flexível e abrangente, melhorando também com demais tempos semafóricos. Para maiores referências sobre redes neurais, sugere-se a leitura de Braga,
Carvalho e Ludermir (2005), Negnevitsky (2005) e Haykin (2008).
Hong et al. (1999) propõem a definição do tempo ótimo de verde por meio de regras Fuzzy e redes neurais, para a redução do tempo médio de parada e melhoria
da velocidade média dos veículos. Com o auxílio de simulação, os autores demonstraram que esse método é mais eficiente que semáforos com tempo fixo. O trabalho
é bem restrito, sendo limitado a apenas 10 interseções, com veículos que trafegam
no máximo a 50 km/h. As regras de produção Fuzzy são baseadas no tamanho dos
veículos. Em trabalho correlato desses autores (HONG; JIN; PARK, 1999), é proposto
um eletrossensor, usando um sistema Neuro-Fuzzy, o qual modifica os semáforos
baseando-se no tamanho e peso dos veículos. Para uma profunda abordagem sobre
sistemas Fuzzy e Neuro-Fuzzy, sugere-se a leitura de Zadeh (1965), Almeida e Evsu4
As redes neurais artificiais são modelos matemáticos que se assemelham às estruturas neurais
biológicas e que têm capacidade computacional adquirida por meio de aprendizado e generalização
(BRAGA; CARVALHO; LUDERMIR, 2005; HAYKIN, 2008).
5
Uma rede de Petri é uma representação gráfica de um sistema distribuído a partir de grafos direcionados e com comentários. Os grafos são compostos por nós de posição, nós de transição e arcos
direcionados relacionando as posições com as transições (GIRAULT; VALK, 2001; BEST; DEVILLERS; KOUTNY,
2001).
2.3 Estado-da-Arte
38
koff (2005a), Almeida e Evsukoff (2005b), Negnevitsky (2005) e Celikyilmaz e Türksen
(2009).
Rouphail, Park e Sacks (2000) utilizaram como pesquisa uma pequena região
urbana de tráfego, com nove interseções sinalizadas na cidade de Chigago (EUA).
Nesse trabalho, os autores realizaram a otimização dos tempos por meio do software
TRANSYT-7F (T7F) e compararam os resultados com um Algoritmo Genético (AG)
desenvolvido, executado em apenas um computador. Os critérios para medição da
eficiência foram os atrasos no trecho da ligação (link ) e o total do tempo de fila da
rede. Para simulação de tráfego, juntamente com o algoritmo evolucionário, os autores usaram o CORSIM, que é um modelo de simulação microscópica aplicado a
corredores de tráfego. O AG gera os dados de entrada para esse modelo, que realiza a simulação e retorna o resultado ao AG para a avaliação a partir de uma função
objetivo. Segundo os autores, esse processo atrasa a convergência do algoritmo e
consequentemente provoca demora nos resultados.
Vogel, Goerick e Seelen (2000) realizaram a otimização dos tempos utilizando
também um AG. Entretanto, essa otimização tem como base dados locais apenas e
interseções isoladas. A justificativa dos autores é de que os dados locais serão base
para adaptação dos semáforos de modo reativo, ou seja, conforme o fluxo no local em
determinado horário.
Brockfeld et al. (2001) realizaram a otimização global dos semáforos, utilizando
um modelo de tráfego por meio de autômatos celulares6 para simulação e avaliação,
com o objetivo de maximizar o fluxo na rede de tráfego. Nesse trabalho, foram tratadas todas as ruas e interseções de modo igual, sem que houvesse nenhuma que
fosse dominante ou preferencial a outra. Segundo os autores, esse método de abordagem torna a otimização mais difícil, pois implica que as fases de verde e vermelho
para cada direção devem ter o mesmo tempo. Definiram que, para interseções em
estradas principais com estradas menores, o fluxo pode ser melhorado, de modo geral, otimizando-se o fluxo na estrada principal. Empregaram ainda a técnica de "onda
verde", com a qual notaram melhoria no fluxo em comparação à estratégia sincronizada. Nesse contexto, demonstram a forte influência dos ciclos de um semáforo no
fluxo de tráfego. Os autores aplicaram essa otimização em uma situação hipotética,
sendo considerada uma rede de tráfego com 16 interseções e as supostas avenidas
6
Autômatos celulares são uma idealização matemática simples de sistemas naturais. Eles consistem
de uma grade infinita e regular de células, cada uma podendo estar em um número finito de estados,
que variam de acordo com regras determinísticas (WOLFRAM, 1983).
2.3 Estado-da-Arte
39
foram dividas em 4 partes (ou células), sendo que cada célula possui um tamanho
7,5 metros. A representação desse modelo, com a definição das células, pode ser
observada na Figura 8. A distância para o próximo carro é definida por 𝑑𝑛 e para o
próximo semáforo, essa distância é dada por 𝑠𝑛 . As condições definidas nesse trabalho podem comprometer os resultados, pois afasta-se muito de situações reais de
tráfego de veículos.
Figura 8: Representação do modelo de tráfego por meio de autômatos celulares
Adaptado de Brockfeld et al. (2001)
Sanchez, Galan e Rubio (2008) aplicaram um técnica evolucionária, baseada em
algoritmos genéticos, para otimização de semáforos em um caso de teste real. Utilizaram também um modelo de simulação de tráfego baseado em autômatos celulares.
O processo foi executado paralelamente em um cluster 7 da classe Beowulf 8 , com
cinco nós9 (um nó master e quatro nós slave), o que julgaram tornar o sistema escalável. Segundo esses autores, após alguns testes, decidiram utilizar, como função de
aptidão (fitness), o número absoluto de veículos que deixam a rede de tráfego. Afirmaram ainda que os tempos podem ser melhorados com esse ambiente de simulação
definido, reduzindo assim o tempo de viagens. Nesse trabalho, a região de estudo
precisou ser discretizada para a utilização no modelo de simulação adotado, o que
resultou em 1.643 células, 42 semáforos, 26 pontos de entrada de veículos e 20 pontos de saída. Essa discretização, obviamente, demandou um tempo razoável, o que
inviabilizaria ou dificultaria muito a aplicação dessa técnica em outras regiões.
7
Cluster é o conjunto ou agrupamento de computadores interligados para a resolução de problemas
de propósito geral.
8
Beowulf é um tipo de construção de cluster, o qual pode ser observado em: http://www.beowulf.org/.
9
Cada computador presente num cluster é conhecido por "nó".
2.3 Estado-da-Arte
40
A abordagem definida por Lämmer e Helbing (2008) foi inspirada na observação
de oscilações da auto-organização do fluxo de pedestres em engarrafamentos. A partir dessa observação, definiram um modelo para o auto-controle semafórico. Esse
problema pode ser tratado como multi-agente, com interações entre veículos e semáforos. Os autores assumem o controle de prioridade dos semáforos pelo próprio fluxo
dos veículos, considerando a antecipação a curto prazo desse fluxo e de pelotões. De
modo análogo, utilizaram algumas leis da área de circuitos elétricos para a modelagem
do problema, como a Lei das Correntes e a Leis dos Nós de Kirchhoff, considerando a
conservação do fluxo (veículos) nos nós (interseções). Em seus resultados, consideraram não só a redução média dos tempos de viagem, como também suas variações.
Julgaram ainda que a abordagem definida pode ser aplicada em logística e processos
de produção. A simulação realizada é simples e conservadora, pois considera em uma
interseção que todos os fluxos são incompatíveis, atendendo apenas um sentido de
movimento por vez.
No âmbito de utilização de SIG existem os trabalhos de Loureiro, Gomes e Leandro (2005) e Meneses, Carvalho e Loureiro (2006). Ambos os trabalhos se referem a
aplicações realizadas na cidade de Fortaleza, na qual o sistema utilizado é o SCOOT,
sistema adaptativo em tempo real. Loureiro, Gomes e Leandro (2005) avaliam o desempenho do tráfego, comparando os planos semafóricos definidos por meio de operação em tempo real e em tempo fixo. Este autor cita o trabalho de Oliveira (1997),
o qual desenvolveu uma interface (SIGTRAF ) que obtém dados no banco de dados
geográfico do SIG TransCAD, processa esses dados no TRANSYT e retorna os resultados ao SIG para geração de mapas temáticos e avaliação da qualidade dos planos
elaborados. Meneses, Carvalho e Loureiro (2006) desenvolveram um interface lógica,
denominada TRANSCOOT, desenvolvida para viabilizar a importação, a modelagem,
o referenciamento espacial e a utilização de dados dinâmicos da base de dados do
trânsito de Fortaleza (CTAFOR) e o SIG TransCAD. Segundo os autores, esta interface combina uma arquitetura modular e um modelo espaço-temporal de versões para
importar dados dinâmicos de tráfego para o ambiente SIG estático, de modo flexível
e eficiente. Afirmaram ainda que, no ambiente de SIG, esta interface agrega caráter
espacial aos dados importados, o que permite realizar análises espaciais sobre o tráfego urbano na área do CTAFOR. O trabalho então expressa a necessidade de utilizar
ou flexibilizar um SIG para a análise e avaliação de levantamento do trânsito.
Além desses, vários outros trabalhos abordam o problema de definição de tempo
de semáforo. O que é importante salientar nos trabalhos encontrados na literatura
2.3 Estado-da-Arte
41
é que não foi abordada pelos autores a questão de se empregar um SIG, no qual
a rede pudesse ser recuperada diretamente, evitando retrabalho para desenho da
mesma em um simulador. Isso, além de agilizar e flexibilizar a avaliação, reduz quase
que totalmente as possibilidades de erro nesse redesenho. Esta é uma importante
contribuição da proposta presente.
2.3.1
Trabalhos do Projeto GEOPROC
No âmbito do GPSI do CEFET-MG, Viana Jr. (2004), Viana Jr., Almeida e Moura
(2004) definiram um atributo, chamado de Impedância de Transposição do Trecho
(ITT), que sintetiza o comprimento e quantidade de veículos das vias para a escolha de trajetos de automóveis. A ITT foi assim denominada por medir a dificuldade
de se transpor determinado trecho. Esse atributo é gerado utilizando Lógica Fuzzy,
por meio do Fuzzy Logic Toolbox do software MATLAB 10 . Após isso, a ITT foi utilizada
no SIG SPRING
11
(Sistema de Processamento de Informações Georreferenciadas)
incorporando, assim, inteligência computacional ao mesmo. Porém, a geração da ITT
e a incorporação desse atributo não eram realizadas dinamicamente. Os especialistas
escolhidos para a validação desse trabalho foram os motoristas de táxi, porque, segundo aquele autor, conhecem as vias e as condições de tráfego do Hipercentro. Além
disso, eles estão habituados a escolher trajetos entre origens e destinos quaisquer
nesta área. De toda maneira, esse trabalho foi bastante relevante, sendo o primeiro
passo para as demais pesquisas do projeto GEOPROC.
Silva (2006), Silva e Almeida (2007), Silva, Jr e Almeida (2005), então, já cientes das restrições do SPRING, utilizaram um SIG que permitisse que funcionalidades
pudessem lhe ser acrescidas. Utilizaram em seu trabalho o OpenJUMP (ver seção
3.1.3), que, além de ser extensível, é um SIG livre e de código aberto. A utilização
do OpenJUMP permitiu aos autores também a automatização da geração do atributo
ITT, que nesse trabalho consistiu da sintetização com o emprego de Lógica Fuzzy do
comprimento do trecho, número de faixas de trânsito disponíveis e fluxo de veículos.
Com esse atributo foi possível definir o "melhor" caminho do trajeto a ser seguido. A
ferramenta desenvolvida, denominada Real Time Intelligent Geographic Information
System (RTIGIS), segundo Silva (2006), realiza a aquisição de dados, a geração do
atributo fuzzy e a atualização da base de dados automaticamente, em tempo real, e de
10
11
http://www.mathworks.com
http://www.dpi.inpe.br/spring/
2.4 Considerações Finais
42
modo integrado ao ambiente de SIG. O trajeto ainda pode ser sugerido considerando
que o percurso será realizado por um automóvel ou por um pedestre.
Saliba Neto (2009), utilizando também o OpenJUMP, desenvolveu um simulador
microscópico de tráfego urbano, escrito em Java, de código fonte aberto e incorporado ao SIG OpenJUMP. O trabalho daquele autor permitiu a avaliação dos trajetos
gerados por Silva (2006), que não a dos especialistas em locomoção de automóveis
(taxistas), utilizados no trabalho de Viana Jr. (2004). Conforme Saliba Neto (2009),
esse simulador foi desenvolvido para realizar um comparativo entre os resultados gerados pelos cálculos de menor e melhor trajeto. O menor trajeto é a menor distância
entre os pontos de origem e destino. O melhor trajeto usa como referência para cálculo
a ITT. Essa ferramenta, incorporada ao SIG, permite a avaliação de várias situações
reais de trânsito e, além disso, auxiliar engenheiros de tráfego na tomada de decisões.
Os trabalhos em questão do projeto GEOPROC utilizaram como área de estudo
o hipercentro de Belo Horizonte, porque, além de ser uma região de grande tráfego
de veículos, possui uma quantidade relevante de dados, captados pela BHTRANS
por meio de laços de detecção veicular, câmeras de TV, dentre outros. Essa área é
apresentada em destaque na Figura 9, e é composto por cerca de 15 avenidas, 120
ruas e mais de 300 cruzamentos.
2.4
Considerações Finais
Neste capítulo foram apresentadas algumas referências relevantes utilizadas para
programação semafórica, bem como para apoio e operação na área de engenharia
de tráfego. Vários termos e conceitos referentes aos semáforos e às ferramentas para
análise das interseções foram definidos e elucidados. O Método de Webster para a
definição do tempo ciclo ótimo para semáforos isolados foi abordado sucintamente,
identificando suas restrições e implicações. O controle semafórico foi conceituado,
conforme o modo de operação em relação à gerência do tráfego e seus resultados.
Os trabalhos correlatos na literatura, por meio do estado-da-arte, foram descritos
e considerados de acordo com sua aplicação e o modo com que o problema foi abordado. Os trabalhos do projeto GEOPROC foram relatados, apresentando a relevância
de cada um, bem como suas contribuições.
Figura 9: Área de estudo − Hipercentro de Belo Horizonte
Adaptado de Viana Jr. (2004)
43
44
3
Sistemas de Informação
Geográfica, Ferramentas de
Simulação e Inteligência
Computacional
O objetivo deste capítulo é abordar os conceitos e fundamentos das três principais
ferramentas presentes neste trabalho. O Sistema de Informação Geográfica (SIG)
agrega funcionalidades de dados georreferenciados, bem como suas técnicas de análise e avaliação desses dados. A Simulação permite que situações do mundo real
sejam representadas e estudas por meio de experimentos. As técnicas de Inteligência Computacional (IC) incorporam recursos aos computadores para a resolução de
problemas por meio do conhecimento.
3.1
Sistemas de Informação Geográfica
Esta seção apresenta as definições, aplicações e fundamentos sobre Geoprocessamento e Sistemas de Informação Geográfica (SIG). Os conceitos apresentados
aqui serão realizados de modo sucinto e apenas para a contextualização do leitor.
Para maiores informações, sugere-se a leitura de Câmara e Davis Jr. (2001), DeMers
(2005), Heywood, Cornelius e Carver (2006), Silva (2006) e Saliba Neto (2009).
Na literatura, é possível encontrar diversas terminologias e traduções para o assunto. Neste trabalho será utilizada a terminologia Sistema de Informação Geográfica
(SIG), conforme apresentado em Câmara (2001), Viana Jr. (2004), Silva (2006), Saliba
Neto (2009), ESRI (2009), Buckey (2009), dentre outros.
3.1 Sistemas de Informação Geográfica
3.1.1
45
Geoprocessamento
O termo Geoprocessamento denota a disciplina do conhecimento que utiliza técnicas matemáticas e computacionais para o tratamento da informação geográfica e que
vem influenciando de maneira crescente as áreas de Cartografia, Análise de Recursos
Naturais, Transportes, Comunicações, Energia e Planejamento Urbano e Regional. As
ferramentas computacionais para Geoprocessamento, chamadas de Sistemas de Informação Geográfica (SIG), permitem realizar análises complexas, ao integrar dados
de diversas fontes e ao criar bancos de dados georreferenciados (CÂMARA; DAVIS JR.,
2001).
Saliba Neto (2009) define que o Geoprocessamento está relacionado ao processamento de dados referentes a um espaço geográfico. Para este processamento, são
utilizados dados de natureza espacial, como as coordenadas geográficas, e também
aqueles que de algum modo possam ser georreferenciados, ou seja, vinculados a outros dados que possam ser localizados na superfície terrestre. Os dados de natureza
espacial podem ser chamados de dados cartográficos, que são a representação gráfica da localização e da geometria das entidades estudadas. Na Figura 10 é mostrada
uma representação para os dados cartográficos.
Figura 10: Representação dos dados cartográficos
Os dados alfanuméricos geralmente são armazenados em tabelas e contêm as
informações descritivas da entidade. Um exemplo de representação desses dados é
apresentado na Figura 11.
46
Figura 11: Representação dos dados alfanuméricos
3.1.2
Definições e Fundamentos
Neste tópico, serão apresentadas definições e fundamentos sobre SIG. Algumas
definições encontradas na literatura serão abordadas, bem como suas aplicações e
funcionalidades.
DeMers (2005) define que os SIG são ferramentas que permitem o processamento
de dados espaciais com informações, geralmente agregadas explicitamente, e usadas
para tomar decisões sobre algum lugar da terra. Segundo aquele autor, essa definição
não é nem abrangente e nem particularmente precisa. Afirma ainda que, como um
campo próprio da geografia, o termo é difícil de ser definido e representa a integração
de muitas áreas.
Os SIG possuem um valor particular quando se necessita responder questões sobre localização, padrões, tendências, condições e implicações como algumas a seguir:
(HEYWOOD; CORNELIUS; CARVER, 2006)
∙ Localização: Onde é a livraria mais próxima? Onde estão as minas de minério
de ferro no Brasil?
∙ Padrões: Qual é o fluxo de tráfego ao longo desta rodovia? Qual é a distribuição
de incidências de crimes em Belo Horizonte?
∙ Tendências: Onde a mudança na população de ursos polares ocorreu?
∙ Condições: Onde pode-se encontrar acomodações de férias a 1 km da praia
e com acesso ao transporte público? Onde existem mais de 100.000 clientes
potenciais num raio de 5 km da estação do metrô?
47
∙ Implicações: Se um novo parque temático for construído neste local, quais são
os efeitos sobre o trânsito? Quanto tempo pode-se economizar se a entrega do
produto for realizada por esta rota, ao invés da rota tradicional?
Alguns termos comuns encontrados na literatura para SIG são apresentados na
Tabela 1, com a origem e/ou motivação de sua derivação.
Tabela 1: Exemplo de Termos Sinônimos para Sistemas de Informação Geográfica
Terminologia
Geographic information system
Geographical information system
Geomatique
Georelational information system
Natural resources information system
Geoscience or geological
resources information system
Spatial information system
Spatial data analysis system
Origem/Motivação
Terminologia utilizada nos Estados Unidos
Terminologia utilizada na Europa
Terminologia utilizada no Canadá
Terminologia baseada na tecnologia
Terminologia baseada na área de estudo
Terminologia baseada na área de estudo
Derivação não baseada na área de geografia
Terminologia baseada no que o sistema faz
Adaptado de DeMers (2005, p. 6)
Conforme Heywood, Cornelius e Carver (2006), em linhas gerais, um SIG pode
ser usado para adicionar e/ou agregar valores a dados espaciais. Aqueles autores
apresentam ainda algumas funcionalidades que um SIG deve prover:
1. Acesso rápido e fácil a um grande volume de dados.
2. Ser capaz de:
∙ selecionar detalhes por área ou tema;
∙ conectar ou mesclar um conjunto de dados com outros;
∙ permitir a análise de características espaciais dos dados;
∙ procurar por características particulares ou feições em alguma área;
∙ atualizar dados rapidamente;
∙ modelar dados e avaliar alternativas.
3. Produzir resultados (mapas, gráficos, lista de endereços e resumo de estatísticas) sob medida, conforme necessidades.
48
Um ponto relevante para a utilização de um SIG é a capacidade desse sistema
integrar todo tipo de informação e aplicações com um componente geográfico em
um sistema de controle. Além disso, existe a possibilidade de suporte à tomada de
decisão por alguns SIG (SHAMSI, 2005).
Em suma, o SIG é uma aplicação de software com recursos para gerenciamento,
análise e armazenamento de informações georreferenciadas e/ou geo-processados,
assim como dados alfanuméricos. Assim, sua utilização torna-se fundamental para
conhecimento e análise de regiões e situações que envolvem localização geográfica
ou espacial.
3.1.3 OpenJUMP
O OpenJUMP (OPENJUMP, 2009) é um SIG livre e de código aberto, escrito em
Java (SUN MICROSYSTEMS, INC., 2008). Uma vantagem desse SIG é a de ser desenvolvido e mantido por um grupo de voluntários distribuídos pelo mundo. Além das
funcionalidades de um SIG, como a visualização de dados espaciais, ele é extensível, o que permite que novos módulos e funcionalidades sejam criadas e adicionadas
à sua arquitetura por meio de plugins. Couto, Brito e Rocha (2006) descrevem que
OpenJUMP é uma implementação da Jump Topology Suite (JTS)1 , que implementa
grande parte das interações espaciais necessárias para um bom funcionamento de
uma ferramenta SIG.
Segundo Saliba Neto (2009), o OpenJUMP é baseado no projeto JUMP GIS 2 , desenvolvido pela empresa Vivid Solutions Inc. Este projeto disponibiliza um conjunto de
aplicativos que provêem uma API (Application Program Interface) extensível e uma interface gráfica de usuário para visualização e manipulação de dados espaciais. Após
o lançamento da versão inicial, o desenvolvimento regular do JUMP foi interrompido
pela Vivid Solutions. No entanto, uma grande comunidade de usuários e desenvolvedores se formou, contribuindo para disseminação, evolução e correção de falhas
do programa. Em seguida, um novo projeto surgiu e foi chamado de OpenJUMP. O
grande número de plugins existentes no site do projeto comprova a popularidade da
ferramenta assim como sua extensibilidade.
A arquitetura JUMP API é organizada em dois pacotes principais: o JUMP API,
com recursos para suporte para operações de entrada/saída, manipulação de feições
1
2
http://www.vividsolutions.com/jts/jtshome.htm
http://www.jump-project.org/
49
e tratamento de informações espaciais; e a JUMP Workbench, que provê a parte de
interface com o usuário (DAVIS, 2003). A representação dessa arquitetura pode ser
observada na Figura 12.
Figura 12: Arquitetura do sistema JUMP
Fonte: http://www.jump-project.org
Alguns dos conceitos encontrados no OpenJUMP serão descritos a seguir. A Figura 13 ilustra esses conceitos.
∙ Extensões: Uma extensão é um conjunto de classes e recursos suportados
que fornecem funcionalidades adicionais ao OpenJUMP. Elas podem adicionar
plugins (itens de menu) e cursortools (botões de ação) na área de trabalho do
SIG (SILVA, 2006).
∙ Feição ou Feature: ou característica, é composta por atributos espaciais e não
espaciais. O atributo espacial, conhecido como geometria, representa um objeto
no espaço, utilizando pontos, linhas e polígonos. Já os atributos não-espaciais
caracterizam este objeto com informações alfanuméricas (SALIBA NETO, 2009).
∙ Camada ou Layer: é um conjunto de features afins e georreferenciadas que
quando sobrepostas formam um mapa. Conceitualmente, em uma mesma camada não devem existir elementos que se sobreponham espacialmente. Uma
camada pode ser do tipo vetorial ou raster (imagem) (SALIBA NETO, 2009).
∙ Tarefa: a tarefa armazena em um arquivo XML (com a extensão jmp) todas
3.2 Simulação
50
as informações que identificam a fonte de dados das camadas assim como a
formatação das mesmas (SALIBA NETO, 2009).
Figura 13: Tela principal do OpenJUMP
Assim, esse SIG tem sido utilizado como base para os trabalhos do projeto GEOPROC do CEFET-MG, adicionando recursos de inteligência computacional no contexto
de avaliação e análise dos dados. Para uma ampla discussão e abordagem desse
SIG, sugere-se a leitura também de Davis (2003), Couto, Brito e Rocha (2006), Silva
(2006) e Saliba Neto (2009) e OpenJUMP (2009).
3.2
Simulação
A simulação é o processo de desenvolvimento de um modelo de sistemas reais
ou imaginários e a realização de experimentos com esse modelo. O propósito da
simulação de experimentos é entender o ambiente do sistema ou avaliar estratégias
para operação do sistema. Suposições são realizadas sobre esse sistema e equações
matemáticas e relações são produzidas para descrever tais suposições - isso constitui
o "modelo" e define como o sistema trabalha. Se o sistema é simples, o modelo pode
ser representado e resolvido analiticamente (SMITH, 1998).
3.2 Simulação
51
Ela é uma ferramenta eficiente para analisar uma grande variedade de problemas
dinâmicos difíceis de serem resolvidos por outros meios. Esses problemas são caracterizados como complexos devido ao grande número de interações simultâneas
entre os vários componentes e entidades do sistema. Essas interações não podem,
geralmente, ser adequadamente descritas de modo lógico ou matemático. No entanto, o comportamento de cada entidade ou as interações de um número limitado
de elementos podem ser bem compreendidos, de modo a ser representado lógica e
matematicamente com uma confiança aceitável (LIEBERMAN; RATHI, 1997).
Neste aspecto, a simulação empregada à engenharia de tráfego torna-se uma
poderosa ferramenta na administração e planejamento do tráfego, pois permite que
situações do cotidiano nas cidades sejam reproduzidas e avaliadas. Além disso, com
o número crescente de veículos e pedestres, o controle do tráfego deve ser eficiente e
seguro, sendo que os recursos tecnológicos são imprescindíveis nessa organização.
3.2.1
Simulação de Tráfego
A importância da simulação no auxílio à gerência de tráfego é considerável, pois
incorpora recursos para o controle e planejamento do trânsito nas cidades. Entretanto,
Saliba Neto (2009) afirma que os simuladores mais conhecidos são desenvolvidos em
outros países e nem sempre consideram as características encontradas no trânsito
das cidades brasileiras. Além disso, são ferramentas que muitas vezes não se encaixam na realidade financeira da maioria dos órgãos reguladores do tráfego do nosso
país.
Os modelos de simulação de tráfego, descritos por aquele autor, são divididos e
classificados conforme o nível de detalhamento, sendo:
∙ Macroscópica: o tráfego é tratado com baixo nível de detalhamento. Ele é representado como uma entidade única, desprezando a individualidade dos veículos.
Os modelos são menos flexíveis e pouco detalhados, sendo apropriados para
modelagem de grandes redes.
∙ Microscópica: são caracterizados pelo alto nível de detalhamento. Tanto os
veículos quanto as demais entidades do sistema podem ser representados de
modo individualizado. A movimentação dos veículos se dá tanto longitudinalmente quanto transversalmente ao longo dos trechos. Devido ao alto nível de
3.2 Simulação
52
detalhamento e o grande número de interações entre as entidades, é uma abordagem que exige muito esforço computacional e requer um processo de calibração complexo, difícil e demorado.
∙ Mesoscópica: possuem um nível intermediário de detalhamento. É uma abordagem mista que representa algumas entidades de maneira agregada e outras
com certo nível de detalhamento. São geralmente utilizados em redes semafóricas.
∙ Submicroscópica: ou nanoscópica, considera os veículos individualmente como
a classificação microscópica. Entretanto, possui um nível de detalhes maior, considerando, por exemplo, a rotação do motor do veículo. Isso permite a apuração
mais detalhada como, por exemplo, das emissões de poluentes produzidas pelos
veículos, por exemplo.
Saliba Neto (2009) declara ainda que os simuladores de tráfego, especialmente
os microscópicos, são caracterizados por exigir uma grande quantidade de dados de
entrada como, por exemplo, a malha viária da região a ser estudada. Partindo da
premissa de que é cada vez mais comum a utilização de Sistemas de Informação Geográfica pelas administrações municipais como ferramenta de planejamento urbano,
é plausível o uso de tais ferramentas como fonte de dados para os simuladores, possibilitando a reutilização de informações espaciais da malha viária, tais como vias e
localização dos semáforos, dentre outras.
A seguir, serão apresentadas ferramentas de simulação mais utilizadas no controle
de tráfego, otimização de tempos semafóricos e simulação de tráfego.
3.2.1.1
TRANSYT
O TRANSYT (Traffic Network Study Tool) é um software britânico para coordenação dos tempos semafóricos, otimizando as defasagens (offsets) na rede semafórica.
É utilizado para elaboração dos planos de temporização semafórica e avaliação de indicadores, obtidos a partir de simulações, das melhorias previstas para o desempenho
do tráfego.
Luna (2003) cita que uma das vantagens é o tempo em que o software está no
mercado, sendo que a primeira versão foi disponibilizada em 1967. Desde então,
diversas versões já foram lançadas. Atualmente, ele está na versão 13.1 (TRL SOFT-
3.2 Simulação
WARE,
53
2009). Luna (2003) ainda relata que seu código foi comercializado com os
Estados Unidos, gerando uma segunda linhagem chamada TRANSYT/7F.
Na otimização dos tempos semafóricos, o TRANSYT requer que os semáforos
de uma mesma rede semafórica operem sob o mesmo tempo de ciclo. Porém, Luna
(2003) afirma que não existe um método formalizado para escolha do ciclo ótimo de
uma sub-área, ou mesmo para a definição do perímetro dessa sub-área. Isso requer
então que o engenheiro de tráfego faça testes e experimentações, combinando subáreas, tempos de ciclo e outros fatores até encontrar uma melhor estratégia a ser
utilizada.
Segundo Cervantes (2005), o algoritmo de otimização utiliza uma heurística de refinamento de busca local que introduz pequenas alterações nas variáveis de decisão,
requisita novo cálculo das variáveis a partir de um modelo e mantém esse procedimento até encontrar um ótimo.
3.2.1.2 SimTraffic
O SimTraffic, produto de software da Trafficware Ltd. (2008), é um simulador microscópico de tráfego que analisa interseções semaforizadas e não semaforizadas.
Utiliza o padrão do HCM 2000 para cálculos e resultados. Atualmente, ele está na
versão 7. Ele permite que sejam definidos tipos distintos para carros, ônibus, motocicletas, assim como o perfil dos motoristas.
O desenho da malha viária, ou seja, as geometrias de trecho de via, cruzamentos, dentre outros, são realizadas no aplicativo Synchro e a simulação realizada no
SimTraffic. Não é possível a importação ou exportação dos arquivos para padrões
utilizados em SIG. Isso limita a avaliação das informações, gerando retrabalho para
desenho das geometrias, seja no SIG ou no Synchro.
Segundo informações da GEPLO em 2008, esse software é utilizado pela BHTRANS para simulação do tráfego, assim como para a definição de tempos semafóricos em locais sem detectores veiculares.
3.2.1.3
TSIS-CORSIM
O Traffic Software Integrated System - Corridor Simulation (TSIS-CORSIM) (MCTRANS,
2008) é um modelo de simulação microscópica de tráfego de sistemas sema-
3.2 Simulação
54
forizados, corredores e a combinação destes. Simula também faixas exclusivas para
ônibus, com ou sem ponto de embarque/desembarque. Segundo Saliba Neto (2009),
esse simulador considera o comportamento do motorista com relação ao avanço no
amarelo do semáforo, bloqueio parcial da via, operações de carga/descarga, estacionamento irregular e a interferência dos pedestres nos giros das interseções.
3.2.1.4
DRACULA
O simulador DRACULA (Dynamic Route Assignment Combining User Learning
and microsimulAtion) está sendo desenvolvido desde 1993 pelo Institute for Transport
Studies3 , University of Leeds4 .
Liu (1994) apresenta que o DRACULA é um simulador de tráfego microscópico
no qual os veículos são individualmente representados. Os movimentos dos veículos
na rede são representados continuamente e atualizados todo segundo. A rede é modelada como um conjunto de nós e arestas, os quais representam as interseções e
ruas respectivamente. Os veículos são gerados em suas origens por uma distribuição
randômica e é atribuído ao conjunto motorista/veículo características (de acordo com
as probabilidades especificados pelo usuário) e uma rota fixa. O movimento dos veículos na rede é controlado pelo modelo car-following (veículo-seguidor), regras para
o intervalo de aceitação (gap acceptance) e regras de tráfego nas interseções. Eles
podem formar filas, mudar de pistas, convergir para outras ruas ou sair do sistema. O
regulamento do tráfego nas interseções é realizado por semáforos ou regras de direito
de passagem.
Segundo Saliba Neto (2009), car-following é o modelo que rege a movimentação
dos veículos ao longo da rede. A velocidade e a aceleração são determinadas em função da distância em relação ao veículo da frente. Os veículos obedecem a parâmetros
de aceleração e buscam atingir uma velocidade pré-definida.
Para maiores informações e referências sobre esse simulador, sugere-se a leitura
de Liu (1994), Liu, Vilet e Watling (1995), Rossetti et al. (2000) e Araújo (2003).
3
4
http://www.its.leeds.ac.uk/index.html
http://www.leeds.ac.uk/
3.3 Inteligência Computacional
3.3
55
Inteligência Computacional
Nesta seção serão apresentados alguns conceitos de Inteligência Computacional,
assim como serão feitas considerações sobre Computação Evolutiva ou Evolucionária. Essa elucidação é necessária devido às técnicas utilizadas neste trabalho para a
geração dos tempos.
3.3.1
Conceitos
A inteligência, segundo Negnevitsky (2005), é definida como a habilidade para
aprender e entender, para resolver problemas e tomar decisões. Fogel (2006) afirma
que a inteligência é parte natural da vida. É também, no entanto, um processo mecânico que pode ser simulado e imitado. A inteligência, segundo aquele autor, não é
propriedade que pode ser limitada de maneira filosófica somente a estruturas biológicas. Ela deve ser igualmente aplicada às máquinas.
O objetivo das pesquisas em Inteligência Artificial (IA) é capacitar o computador
a executar funções que são desempenhadas pelo ser humano usando conhecimento
e raciocínio (REZENDE, 2005). Silva (2006) define IA como o ramo da ciência que
estuda o conjunto de paradigmas que pretendem justificar como um comportamento
inteligente pode emergir de implementações artificiais, em computadores. Um sistema
é considerado inteligente, então, se esse for capaz de simular ou emular o processo
de decisão do ser humano. (REZENDE, 2005). Aquela autora caracteriza os Sistemas
Inteligentes (SI) por apresentarem:
∙ habilidade para usar conhecimento para desempenhar tarefas ou resolver problemas;
∙ capacidade para aproveitar associações e inferência para trabalhar com problemas complexos que assemelham-se a problemas reais.
A IC, conforme expressa Silva (2006), é a área da ciência que estuda a teoria e
a aplicação de técnicas inspiradas na natureza. Algumas técnicas relevantes dessa
área são a Lógica Fuzzy, as Redes Neurais e a Computação Evolucionária.
A abordagem evolucionária, segundo Negnevitsky (2005), é baseada em modelos
computacionais da seleção natural e genética. Computação evolucionária trabalha si-
56
mulando populações de indivíduos, avaliando sua performance, gerando novas populações, e repetindo esse processo por um determinado número de vezes. Algoritmos
genéticos, estratégias de evolução e programação genética são exemplos de algumas
das diversas técnicas que compõem a computação evolucionária.
3.3.2
Algoritmos Genéticos
Algoritmos genéticos, segundo Negnevitsky (2005), são uma classe de algoritmos
de busca estocástica baseados em evolução biológica. Similarmente, Michalewicz
(1996) os define como procedimentos computacionais estocásticos cujos métodos de
busca modelam os fenômenos biológicos de herança genética e seleção natural.
Carvalho, Braga e Ludermir (2005) caracterizam os AG como algoritmos de otimização global, baseados nos mecanismos de seleção natural e da genética. Afirmam
que eles empregam uma estratégia de busca paralela e estruturada, embora aleatória,
direcionada à busca de pontos de "alta aptidão", ou seja, pontos nos quais a função
a ser minimizada ou maximizada tem valores relativamente baixos ou altos, respectivamente. Souza (2009) declara que o objetivo de um AG é o de tentar melhorar
as qualidades genéticas de uma população por meio de um processo de renovação
iterativa das populações.
Os algoritmos genéticos simples, de acordo com De Castro (2001), constituem
modelos abstratos da evolução natural e operam com populações de tamanho fixo e
indivíduos representados por "cadeias genéticas" de comprimento fixo. Novas populações evoluem por meio da seleção probabilística proporcional ao fitness dos indivíduos, produzindo, via operações de cruzamento e mutação, descendentes semelhantes aos pais.
Segundo Fogel (2006), esta técnica, basicamente (1) incorpora uma população de
indivíduos codificados como "cromossomos", principalmente pela representação binária (zeros e uns), (2) reproduz cópias desses indivíduos baseadas em um critério de
aptidão externo, e (3) novos indivíduos são gerados para cada nova geração por meio
de mutação dos bits e recombinando elementos de diferentes membros da população.
A resolução de um dado problema, por meio de um AG básico, pode ser representada
como na Figura 14.
3.3.2.1
57
Representação
A representação dos indivíduos ou cromossomos de uma população pode ser realizada por meio de uma cadeia de valores ou vetores de valores binários (0 ou 1).
Cada indivíduo da população é uma possível solução para o problema em questão.
A codificação desses valores binários representa analogamente o genótipo de um indivíduo. Quando o valor binário é traduzido em números reais, tem-se o fenótipo do
indivíduo. O conjunto de todas as configurações que o cromossomo pode assumir
formam o seu espaço de busca (CARVALHO; BRAGA; LUDERMIR, 2005).
Existem outros modos para representação dos indivíduos, como por meio de números reais. Essa representação é mais naturalmente compreendida pelo ser humano
e requer menos memória do computador que aquela usando uma cadeia de bits (CARVALHO; BRAGA; LUDERMIR,
2005). Entretanto, essa representação requer operações
e tratamentos diferentes e que não serão abordados neste contexto. A escolha da
representação depende, dentre outros, do escopo abordado, do tipo de número que
constitui uma solução para o problema (inteiro, real) e das operações genéticas.
3.3.2.2
Definição da População Inicial
Von Zuben (2009a) expressa que o método mais comum utilizado na criação da
população é a inicialização aleatória dos indivíduos. Se algum conhecimento inicial a
respeito do problema estiver disponível, pode ser utilizado na inicialização da população. Por exemplo, no caso de codificação binária, se é sabido que a solução final vai
apresentar mais 0’s do que 1’s, então esta informação pode ser utilizada, mesmo que
não se saiba exatamente a proporção. Já em problemas com restrição, deve-se tomar
cuidado para não gerar indivíduos inválidos na etapa de inicialização.
3.3.2.3
Função de Avaliação
A função de avaliação (ou função-objetivo ou função de custo) pode ser definida
por uma expressão matemática que determina se uma solução está próxima ou distante da solução esperada (CARVALHO; BRAGA; LUDERMIR, 2005). Conforme o problema
em questão, ela pode ser maximizada, quando soluções com o maior valor possível
são desejáveis; ou minimizada, quando se deseja encontrar os menores valores para
a função. Para medir o quão boa é uma solução, utiliza-se a função de aptidão, que
58
pode ser vista como uma nota para essa solução, e é baseada no valor da função
de avaliação (CARVALHO; BRAGA; LUDERMIR, 2005). Em um problema de maximização
essa função pode ser a própria função objetivo e em um problema de minimização ela
pode ser o inverso da função objetivo (SOUZA, 2009).
3.3.2.4
Seleção
Os indivíduos numa população podem ser selecionados de acordo com sua aptidão para a reprodução a partir dos operadores genéticos. Dentre as técnicas de
seleção, uma das mais difundidas é o método da roleta (Roulette Wheel Selection),
no qual os indivíduos são selecionados proporcionalmente à sua função de aptidão.
Numa roleta, similar às utilizadas em jogos de azar, esse procedimento aloca espaços
para cada indivíduo de modo que a probabilidade do indivíduo ser selecionado varia
conforme sua aptidão (GOLDBERG, 1989). Outra técnica é o método de seleção por
torneio (Tournament Selection), na qual 𝑡 indivíduos são selecionados aleatoriamente,
com a mesma probabilidade e competem entre si de acordo com seus valores de aptidão. De Castro (2001) apresenta o método de seleção elitista, no qual os 𝑛 melhores
indivíduos da população são selecionados.
A Figura 15 exemplifica o método de seleção da roleta, no qual os indivíduos são
dispostos proporcionalmente à sua função de avaliação. No exemplo, o indivíduo 2
possui maior probabilidade de ser selecionado.
3.3.2.5
Operadores Genéticos
Um conjunto de operadores é necessário para que, dada uma população, seja
possível gerar populações sucessivas que (espera-se) melhorem sua aptidão com o
tempo. Os operadores mais comuns são o cruzamento ou recombinação (crossover )
e mutação. Eles são utilizados para assegurar que a nova geração seja diversificada,
mas possua, de alguma maneira, características de seus pais; e são necessários para
que a população se diversifique e mantenha características de adaptação adquiridas
pela gerações anteriores. O princípio básico então é transformar a população por meio
de sucessivas gerações, estendendo a busca até chegar a um resultado satisfatório
(CARVALHO; BRAGA; LUDERMIR, 2005).
A recombinação troca características entre os pais, gerando novos filhos. Dentre
as maneiras mais usuais, existe a recombinação a partir de um ponto de corte, no
59
qual, em um ponto qualquer dos indivíduos, as informações dos pais são combinadas,
como apresentado na Figura 16. A recombinação em multipontos acontece quando
ocorre a troca de informações em vários pontos dos pais.
A mutação consiste na modificação do valor de um ou vários bits de um indivíduo
(de 0 para 1 ou 1 para 0). Conforme Carvalho, Braga e Ludermir (2005), geralmente se
utiliza uma taxa de mutação pequena, pois esse é um operador genético secundário.
A Figura 17 apresenta o exemplo de mutação em um bit (flip mutation).
3.3.2.6
Composição da Nova População
Os indivíduos que vão compor a nova população, ou a população para a geração
seguinte, podem ser os novos filhos gerados pelos operadores somente ou a combinação desses com alguns pais, selecionados por meio de técnicas como as descritas na
seção 3.3.2.4. Assim, a população pode ser totalmente substituída ou ainda preservar
características da população anterior, empregando então a técnica de elitismo.
Sugere-se a leitura de Goldberg (1989), Michalewicz (1996), De Castro (2001),
Rezende (2005), Negnevitsky (2005), Fogel (2006), dentre outros, para uma abordagem mais aprofundada sobre algoritmos genéticos, bem como demais ferramentas e
operadores genéticos.
3.3.3
CLONALG
De Castro (2001) desenvolveu ferramentas computacionais para a solução de problemas complexos de engenharia, inspiradas em sistemas imunológicos artificiais.
Uma dessas ferramentas é o CLONal selection ALGorithm (CLONALG), uma implementação computacional simplificada do princípio da seleção clonal dos linfócitos B
(ou células B5 ) durante uma resposta imune adaptativa. Uma resposta imune específica, como a produção de anticorpos a um determinado agente infeccioso, é conhecida
como uma resposta imune adaptativa. Os anticorpos são produzidos pelos linfócitos
B em resposta a infecções, e sua presença em um indivíduo reflete as infecções às
quais o mesmo já foi exposto. O princípio (ou teoria) da seleção (ou expansão) clonal, conforme descreve aquele autor, está associado às características básicas de
5
Pequenas células brancas cruciais para as defesas imunes. Também conhecidas por linfócitos
B, são produzidas na medula óssea e diferenciam-se em plasmócitos, geradoras dos anticorpos, ou
células de memória, capazes de responder rápida e efetivamente contra re-infecções. (DE CASTRO,
2001)
60
uma resposta imune adaptativa a um estímulo antigênico6 . Ele estabelece que apenas aquela célula capaz de reconhecer um determinado estímulo antigênico irá se
proliferar, sendo, portanto, selecionada em detrimento das outras.
Foram propostas duas versões para o algoritmo: a primeira para resolver problemas de aprendizado de máquina e reconhecimento de padrões e a segunda para
resolver problemas de otimização. Neste trabalho, apenas o segundo algoritmo será
abordado, pois é o que se enquadra aos objetivos e propostas aqui definidos. Os demais conceitos biológicos utilizados por aquele autor também não serão descritos e/ou
aprofundados. Sugere-se então a leitura, além da referência acima do autor, de De
Castro e Von Zuben (2000), De Castro e Von Zuben (2002), De Castro e Von Zuben
(2005), Von Zuben (2009b), para contextualização das ferramentas propostas, bem
como revisões sobre o sistema imunológico. As referências e considerações descritas
no contexto deste trabalho baseiam-se em De Castro (2001).
3.3.3.1
Definições
Neste tópico serão apresentadas sucintamente as definições para o algoritmo
CLONALG, como também o seu pseudocódigo, com os devidos parâmetros de entrada e saída, e o diagrama de blocos para a execução do mesmo.
A Figura 18 apresenta o diagrama de blocos para a execução do algoritmo CLONALG. O repertório de anticorpos disponíveis é representado por 𝐴𝑏. A implementação computacional do CLONALG para otimização de funções pode ser feita utilizando
o pseudocódigo descrito na Figura 19, dados os parâmetros de entrada e saída:
∙ Entrada:
– Comprimento 𝐿 dos anticorpos;
– População 𝐴𝑏 composta por 𝑁 anticorpos;
– Quantidade 𝑔𝑒𝑛 de gerações a serem executadas (critério de parada);
– Número 𝑛 de anticorpos a serem selecionados para clonagem;
– Fator multiplicativo 𝛽 usado na definição da quantidade de clones;
– Quantidade 𝑑 de anticorpos com baixa afinidade que serão substituídos.
6
Qualquer substância que, quando introduzida no organismo, é reconhecida pelo sistema imune
adaptativo. Seu nome deriva de sua propriedade de gerar anticorpos (DE CASTRO, 2001)
61
∙ Saída:
– Matriz 𝐴𝑏, correspondente aos anticorpos de memória;
– Afinidade (fitness) 𝑓 de cada anticorpo da matriz 𝐴𝑏.
As funções utilizadas no pseudocódigo e as respectivas descrições são apresentadas a seguir:
−→ 𝒇 := 𝒅𝒆𝒄𝒐𝒅𝒊𝒇 𝒊𝒄𝒂(𝑨𝒃) : decodifica e calcula a afinidade 𝑓 da população 𝐴𝑏
(cada elemento do vetor 𝑓 representa a afinidade de um único indivíduo da população 𝐴𝑏) em relação a uma função objetivo 𝑔(⋅) a ser otimizada.
−→ 𝑨𝒃{𝒏} := 𝒔𝒆𝒍𝒆𝒄𝒕(𝑨𝒃, 𝒇, 𝒏) : seleciona 𝑛 anticorpos da população 𝐴𝑏 proporcionalmente à afinidade 𝑓 , gerando uma subpopulação 𝐴𝑏{𝑛} .
−→ 𝑪 := 𝒄𝒍𝒐𝒏𝒂(𝑨𝒃{𝒏} , 𝜷, 𝒇 ) : clona (reproduz) os elementos da população 𝐴𝑏{𝑛}
proporcionalmente à afinidade 𝑓 e a um fator multiplicativo 𝛽, gerando uma população 𝐶. A quantidade 𝑁𝑐 de clones gerada pode ser definida a partir da
equação (3.1).
𝑁𝑐 =
𝑛
∑
𝑟𝑜𝑢𝑛𝑑(𝛽.𝑁/𝑖)
(3.1)
𝑖=1
sendo 𝛽 é um fator multiplicativo, 𝑁 é a quantidade total de anticorpos do repertório 𝐴𝑏 e 𝑟𝑜𝑢𝑛𝑑() é o operador que arredonda o valor entre parênteses para o
inteiro mais próximo. Neste caso, os anticorpos estão ordenados da maior para a
menor afinidade, portanto quanto maior 𝑖 na Equação (3.1), menor a afinidade e
consequentemente a quantidade de clones gerada para 𝐴𝑏𝑖 (DE CASTRO, 2001).
−→ 𝑪 ∗ := 𝒉𝒚𝒑𝒆𝒓𝒎𝒖𝒕(𝑪, 𝒇 ) : muta os elementos da população 𝐶 proporcionalmente à afinidade 𝑓 , gerando uma população 𝐶 ∗ . A hipermutação é inspirada
na hipermutação somática, que é utilizada pelo sistema imunológico para inserir
e manter a diversidade do repertório linfocitário e também para melhorar a afinidade (capacidade de reconhecimento) dos anticorpos em relação aos estímulos
aplicados. Esse é o operador primário do CLONALG e, ao contrário do AG, deve
possuir uma taxa de mutação mais elevada.
−→ 𝑨𝒃{𝒎} := 𝒊𝒏𝒔𝒆𝒓𝒆(𝑨𝒃{𝒎} , 𝑨𝒃{𝒅} ) : insere a matriz 𝐴𝑏{𝑑} na população 𝐴𝑏{𝑚} ou,
dito de outra maneira, concatena a matriz 𝐴𝑏{𝑚} com a matriz 𝐴𝑏{𝑑} .
62
−→ 𝑨𝒃 := 𝒈𝒆𝒓𝒂(𝑵, 𝑳) : gera uma população 𝐴𝑏 contendo 𝑁 anticorpos de comprimento 𝐿 cada um.
−→ 𝑨𝒃{𝒓} := 𝒓𝒆𝒑𝒍𝒂𝒄𝒆(𝑨𝒃{𝒓} , 𝑨𝒃{𝒅} , 𝒇 ) : substitui 𝑑 anticorpos de 𝐴𝑏{𝑟} pelos 𝑑 elementos da população 𝐴𝑏{𝑑} proporcionalmente à afinidade 𝑓 .
A implementação deste algoritmo, bem como as demais ferramentas desenvolvidas pelo autor em questão, estão disponíveis em Von Zuben (2009b).
3.4
Neste capítulo foi apresentado um arcabouço teórico-conceitual necessário para
a compreensão das tecnologias e técnicas integradas nesse trabalho. O Geoprocessamento engloba o tratamento e avaliação de informações geográficas. O SIG é
o recurso de software para apoio a esse tratamento, bem como para a análise das
informações. O OpenJUMP é um SIG livre e de código aberto, escrito em Java e extensível, o que pode justificar a sua utilização nos trabalhos do projeto GEOPROC do
CEFET-MG.
A simulação permite que sistemas dinâmicos e complexos sejam estudados por
meio da elaboração de modelos. Esse recurso empregado à engenharia de tráfego
torna-se uma ferramenta importante na administração e planejamento do tráfego, pois
permite que situações do cotidiano das cidades sejam reproduzidas e avaliadas.
Os recursos de IC agregam a capacidade de aprendizado e entendimento para a
resolução de problemas e tomada de decisão. Os AG são procedimentos computacionais de busca estocástica inspirados em genética e seleção natural. O algoritmo
CLONALG é inspirado no princípio de seleção clonal e em sistemas imunológicos artificiais. Todos estes conceitos serão usados em conjunto para a proposição de uma
solução viável para o problema de geração de tempos semafóricos.
63
Figura 14: Algoritmo Genético básico
Adaptado de Negnevitsky (2005)
Figura 15: Exemplo do método de seleção por roleta
Adaptado de Fogel (2006)
Figura 16: Exemplo de recombinação a partir de um ponto de corte
Adaptado de Carvalho, Braga e Ludermir (2005)
Figura 17: Exemplo de mutação em um bit
Adaptado de Carvalho, Braga e Ludermir (2005)
64
65
Figura 18: Diagrama de blocos para o algoritmo CLONALG para o problema de otimização
Adaptado de De Castro (2001)
Figura 19: Pseudocódigo para o algoritmo CLONALG
Adaptado de De Castro (2001)
66
4
DESENVOLVIMENTO DO
GERADOR DE TEMPOS
Este capítulo descreve as etapas de modelagem e implementação do gerador de
tempos semafóricos, bem como a incorporação do mesmo ao SIG OpenJUMP e ao
simulador desenvolvido por Saliba Neto (2009). Esta ferramenta é uma evolução do
projeto GEOPROC e tem como base a mesma arquitetura utilizada nos trabalhos de
Silva (2006) e Saliba Neto (2009).
Inicialmente, os pontos relevantes deste trabalho ao simulador GISSIM desenvolvido por Saliba Neto (2009) são apresentados. Após isso, são descritos as bibliotecas,
os conceitos e recursos utilizados na construção do gerador de tempos. Para maiores
referências sobre o desenvolvimento desse simulador, sugere-se a leitura do autor em
questão.
4.1
Simulador GISSIM
A ferramenta GISSIM desenvolvida por Saliba Neto (2009), conforme abordado em
2.3.1, é um simulador microscópico de tráfego urbano, escrito em Java, de código fonte
aberto e incorporado ao SIG OpenJUMP. Esse simulador considera uma microrregião
como área de simulação. A principal fonte de informações para o simulador são as
bases cartográficas municipais, que comumente possuem dados relativos às vias de
circulação. É natural que essas informações abranjam toda a extensão do município.
No entanto, em função de seu caráter microscópico, a área de simulação deve ser
restrita a uma pequena região de estudo (SALIBA NETO, 2009). A arquitetura do GISSIM
pode ser observada na Figura 20.
4.1 Simulador GISSIM
67
Figura 20: Diagrama de pacotes das extensões desenvolvidas para o OpenJUMP
Adaptado de Saliba Neto (2009)
4.1.1
Área de Simulação
Para que a simulação de uma determinada microrregião seja realizada é necessária a criação da área de simulação. A partir da seleção da área pela ferramenta
"Quadro" ou "Fence" do SIG OpenJUMP, o processo identifica na malha viária selecionada quais são os pontos de entrada/saída de veículos (SourceSinkJunction) e
os cruzamentos. Os cruzamentos podem ser definidos como Control, quando apenas conectam dois segmentos de reta e Cross quando existe a interseção de mais de
dois segmentos. Com a área de simulação delimitada, são criadas as novas camadas contendo as informações cartográficas que servirão de dados de entrada para a
simulação, as quais podem ser definidas a seguir:
∙ Entrada/Saída de veículos: representa os nós de entrada/saída de veículos na
rede. Todos os nós que estão conectados com apenas uma aresta são classificados como do tipo entrada/saída;
∙ Pontos de Controle: a camada de controle contém os nós que apenas ligam
dois trechos. Esta situação ocorre quando a base cartográfica possui trechos
que foram seccionados fora de um cruzamento, como por exemplo, na divisa entre bairros. Todos os nós que estão conectados com duas arestas são inseridos
nesta camada;
∙ Cruzamentos: são caracterizados por nós que estão conectados com mais de
duas arestas. Representam os cruzamentos em uma malha viária.
4.1 Simulador GISSIM
68
Saliba Neto (2009) dividiu o desenvolvimento do simulador em duas partes: construção da interface para representação gráfica dos componentes de simulação e a
máquina de simulação, responsável por gerir todas as interações que ocorrem no sistema.
4.1.2
Interface Gráfica
A interface gráfica do simulador é responsável por exibir a evolução dinâmica da simulação como, por exemplo, a movimentação dos veículos. Uma boa interface gráfica
enriquece a análise dos fenômenos que ocorrem no tráfego e facilita o entendimento
dos estados do sistema por parte dos usuários durante uma simulação (SALIBA NETO,
2009). As geometrias apresentadas em tela são em escala real e possuem como
unidade de medida o metro. Uma característica importante no desenvolvimento da
interface gráfica é de que o objeto responsável por desenhar os componentes do sistema é totalmente desacoplado da máquina de simulação. Aquele autor aplicou uma
variante mais simples do padrão de projeto Observer, que garante a consistência entre
objetos relacionados sem a utilização de classes fortemente acopladas.
4.1.3
Máquina de Simulação
Conforme Saliba Neto (2009), a máquina de simulação é o módulo responsável
pelo gerenciamento do ambiente de simulação, controlando a interação entre todos os
componentes do sistema. As classes relativas à máquina de simulação estão localizadas no pacote br.cefetmg.lsi.gissim.simulation. A geração de veículos tem como base
um parâmetro denominado Veículos por Hora (VPH). Esse valor é definido na junção
de entrada de veículos e define o fluxo de veículos por hora que entram na rede, a partir de uma distribuição uniforme de probabilidade. Assim como a geração de veículos,
a saída de veículos da rede também é feita por intermédio da classe SourceSinkJunction. Toda vez que um veículo entra em um nó deste tipo, ele automaticamente é
recolhido da rede e deixa de existir (SALIBA NETO, 2009).
A movimentação dos veículos é realizada por meio do modelo de tráfego carfollowing. A cada passo de simulação, todos os veículos são notificados a atualizar
sua velocidade e posição. O modelo de movimentação é aplicado no cálculo da nova
velocidade do veículo. Este cálculo é feito, basicamente, em função da distância atual
do veículo para um obstáculo imediatamente à sua frente. Um obstáculo, neste traba-
4.2 Gerador de Tempos
69
lho, pode ser um veículo ou uma junção, do tipo prioritária, desde que o veículo não
esteja trafegando em uma via prioritária (SALIBA NETO, 2009).
4.1.4
Veículos Instrumentados
O veículo instrumentado possui todas as características de um veículo comum,
exceto pela capacidade de seguir um trajeto fixo pré-definido pelo usuário. Além da
rota, o veículo instrumentado também sabe em qual passo de simulação ele deve
entrar na rede. A função deste tipo de veículo é colher informações sobre viagens
fixas (SALIBA NETO, 2009).
4.1.5
Estatísticas
As estatísticas geradas pelo simulador são imprescindíveis para a avaliação dos
resultados. Os indicadores gerados pelo simulador são classificados em dois grupos: em tempo real, visualizados na interface do simulador durante a simulação e
em arquivo, armazenados durante a simulação e gravados em disco ao final do processo. Os indicadores dos veículos, do tipo arquivo, só são gerados quando o veículo
completa a viagem inteira. Uma viagem é considerada completa quando o veículo é
coletado por um nó de saída (SALIBA NETO, 2009).
4.1.6
Considerações
Uma restrição do GISSIM é a de permitir a simulação de apenas uma via de tráfego por sentido. Não é possível determinar múltiplas faixas para simulação, limitando
então as avaliações. Entretanto, é importante salientar a enorme contribuição ao projeto GEOPROC com o desenvolvimento desse simulador. Outro fator relevante é que
a modelagem realizada por Saliba Neto (2009) permite que o GISSIM seja estendido,
com a incorporação de novas funcionalidades.
4.2
Gerador de Tempos
Nesta seção serão descritas as etapas para construção do gerador de tempos,
denominado GISSIM - Traffic Lights (GISSIM-TL), em virtude de ser o módulo responsável também pelo gerenciamento dos semáforos no simulador GISSIM. Inicialmente,
70
algumas extensões realizadas no GISSIM que permitem a definição de multipistas
de tráfego, o processo de recuperação de veículos instrumentados e as respectivas
restrições serão abordadas.
4.2.1
Extensões do Simulador
A restrição apresentada anteriormente para o GISSIM foi parcialmente resolvida
neste trabalho, com o intuito da ampliação das funcionalidades dessa ferramenta,
como também para apoio aos experimentos. O código-fonte do simulador foi modificado, tanto na parte da interface quanto na máquina de simulação, permitindo que
sejam definidas até três vias de tráfego por trecho. Entretanto, esse número de pistas deve ser respeitado em toda área de simulação, não sendo permitindo, que num
cruzamento existam, por exemplo, três vias de tráfego chegando e duas saindo desse
cruzamento.
O veículo quando entrava na simulação, conforme a definição do VPH, era inserido
na primeira pista daquele ponto de entrada. Essa situação foi modificada e a pista passou a ser selecionada aleatoriamente, conforme o total de pistas para o trecho. Outra
modificação é que a pista que o veículo será inserido após sair de um cruzamento é a
de mesmo número que ele chega. Por exemplo, o veículo trafega na pista de número
dois e chega a um cruzamento. A pista que ele será inserido no próximo trecho na qual
ele trafegará também é a de número dois. Isso pode acontecer, conforme abordado
anteriormente, porque todos os trechos devem possuir o mesmo número de pistas.
Outra questão não abordada nesta extensão é a implementação de mudança de
faixa de tráfego pelos veículos. A princípio, ela não foi necessária devido a mesmo
número de pistas para todos os trechos. Posteriormente, essa questão deve ser observada pois limita, como a restrição de faixas, a aplicação desse simulador em algumas situações. Contudo, é importante salientar que o processo de extensão desse
simulador, até o nível de um software existente no mercado, demanda enorme tempo,
como também inúmeras pesquisas, principalmente sobre situações do cotidiano.
Uma funcionalidade agregada ao simulador é a capacidade de salvar em arquivo
e carregar os veículos instrumentados adicionados a uma simulação. Inicialmente, a
cada simulação, era necessário que esses veículos fossem adicionados novamente.
Essa questão agiliza a simulação, quando realizada inúmeras vezes, pois o veículos
podem ser inseridos, salvos e recuperados a qualquer instante. O arquivo possui o
71
formato XML1 e é persistido nesse formato por meio da biblioteca XStream2 . Essa biblioteca permite que objetos Java sejam facilmente persistidos e recuperados. Ainda
para essa classe de veículos, criou-se a funcionalidade que permite que eles sejam
cíclicos, ou seja, ao deixarem a simulação num determinado instante 𝑡, são inseridos
novamente na simulação no instante 𝑡 + 1. Isso permite que avaliações mais detalhadas sobre determinada rota ou trecho sejam realizadas, como o congestionamento da
via por meio do tempo médio gasto para conclusão do trajeto.
4.2.2
Arquitetura do Gerador de Tempos
Como o GISSIM-TL é um módulo incorporado ao GISSIM, responsável pelo gerenciamento dos semáforos nos cruzamentos e pela geração de tempos, foi necessário
o estabelecimento de uma relação de dependência entre os objetos dessas ferramentas. Essa relação pode ser observada na Figura 21, na qual são representados os
pacotes do gerador de tempos e do simulador. Uma breve descrição dos pacotes
apresentados acima pode ser observada na Tabela 2.
Tabela 2: Descrição dos pacotes do gerador de tempos
1
2
eXtensible Markup Language
http://xstream.codehaus.org/
72
Figura 21: Diagrama de pacotes da arquitetura
Pacotes do gerador de tempos (em verde) e do simulador (em azul)
As ferramentas de inteligência computacional responsáveis pela geração dos tempos dos semáforos foram implementadas em subpacote do br.cefetmg.lsi.gissimtl.ci,
como o br.cefetmg.lsi.gissimtl.ci.clonalg e o br.cefetmg.lsi.gissimtl.ci.ga. Outro ponto
relevante desse pacote é que ele é responsável pela integração da geração de tempos
com o simulador GISSIM. As informações referentes aos semáforos, como fase, estágio, grupos semafóricos, dentre outros (ver seção 2.1.2) foram definidas no pacote
br.cefetmg.lsi.gissimtl.trafficlights.
A classe responsável por gerenciar o cruzamento semaforizado na simulação é a
TrafficLightsJunction, presente no pacote do GISSIM br.cefetmg.lsi.gissim.simulation.
Essa classe implementa a interface Junction e define um novo tipo para os cruzamentos, além de Control e Cross, o TrafficLights. Da mesma maneira que esse cruzamento
foi criado, outros tipos podem ser facilmente implementados.
4.2.3
Interfaces
Algumas interfaces foram definidas para a definição dos parâmetros e configuração dos cruzamentos para agilizar o processo de geração de tempos e simulação. A
73
primeira delas, apresentada na Figura 22, é responsável pela configuração dos cruzamentos, na qual se define o seu tipo em simples (similar a um cruzamento prioritário
e com apenas placas de "Pare") e semaforizado (gerenciado por semáforos). Essa
interface é invocada por um plugin, responsável pela integração ao SIG OpenJUMP.
Figura 22: Interface de configuração de cruzamentos
No primeiro quadro dessa interface são exibidas as informações sobre o cruzamentos, como os trechos que chegam e saem da interseção. Caso ele seja do tipo
semaforizado, é apresentada no segundo quadro a definição do ciclo para o cruzamento, que é realizada na interface apresentada na Figura 23. Nessa interface, são
definidas as fases, os estágios, o estado do semáforo (cor) para o estágio e, opcionalmente, o tempo de entreverdes (amarelo). Assim como na interface de configuração
do cruzamento, informações sobre a definição do ciclo são exibidas.
Numa fase é necessário definir quais semáforos integram o grupo focal ou semáforo. Pode ser apenas um semáforo ou podem haver mais no cruzamento que
tenham a mesma configuração definida, ou seja, podem estar em verde ou vermelho ao mesmo tempo em pistas diferentes. A Figura 24 apresenta a definição desses
grupos para uma determinada fase.
4.2.4
Módulo de Geração de Tempos
O módulo de geração de tempos foi modelado de modo a permitir a incorporação
de outras técnicas de inteligência computacional. Cada técnica definida, por sua vez,
74
Figura 23: Interface de definição do ciclo
Figura 24: Interface de definição dos grupos focais
possui um conjunto de parâmetros a ser informado. Desse modo, a interface com o
usuário deve ser implementada também pelo responsável por agregar novas técnicas
de geração de tempos. A Figura 25 apresenta a interface principal para a definição
dos parâmetros. Nessa interface é possível que diversas configurações sejam salvas,
o que permite que dados históricos dessas parametrizações estejam armazenados,
facilitando a geração de tempos. Esses dados são salvos num layer denominado
"Parâmetros", o qual possui uma feição apenas (um ponto). Os dados alfanuméricos
para essa feição são as configurações, salvas no formato XML por meio da biblioteca
XStream. Essa opção de gravação foi utilizada para que esses dados sejam salvos
juntamente com a tarefa do OpenJUMP.
Uma implementação, na qual é apresentada a definição de parâmetros para uma
técnica específica, é representada na Figura 26. A parte referente aos parâmetros
é carregada dinamicamente, conforme a técnica selecionada e é ela que deve ser
75
Figura 25: Interface de configuração de parâmetros para as técnicas de IC.
implementada caso outras técnicas sejam incorporadas.
Figura 26: Interface de configuração de parâmetros para o algoritmo CLONALG
O acesso à interface de geração de tempos é realizada por meio de uma opção
na interface de simulação. Isso é necessário porque o gerador de tempos utiliza o
objeto de simulação (máquina de simulação) para a avaliação dos tempos gerados.
O ambiente de simulação deve ser previamente definido, como o carregamento do
arquivo de volume e dos veículos instrumentos, para que os tempos sejam gerados
de acordo com a configuração do ambiente em questão.
Para a geração de tempos é necessário que seja selecionada a técnica a ser
76
Figura 27: Interface do gerador de tempos
utilizada. Após selecionada, os parâmetros cadastrados para a técnica em questão
são carregados e um deles deve ser indicado para a geração. Além disso, é essencial
que seja definido o intervalo de tempos para cada semáforo. Esses valores definem
o limite inferior e superior de tempos de verde, em segundos, para cada semáforo
definido para geração. A cada conjunto de tempos definido pela técnica de IC, esses
tempos devem ser avaliados pelo simulador, objetivando-se a evolução da geração.
O número de passos de simulação define o tempo, em segundos, de cada simulação
executada para a avaliação dos tempos gerados. É importante salientar que apenas
a máquina de simulação é executada, conforme a divisão definida por Saliba Neto
(2009). A modelagem desse modo agilizou o processo de geração de tempos, na qual
os tempos são avaliados sem que seja necessário a exibição da simulação em tela.
O tempo de amarelo definido é usado para todos os cruzamentos, caso o tempo de
entreverdes não tenha sido configurado na definição do ciclo (Figura 23). Os campos
de início e fim exibem a hora inicial e final de processamento e o tempo gasto em
milissegundos é apresentado no último campo. O processamento da avaliação dos
tempos gerados pela técnicas de IC por meio do simulador é ilustrado pela Figura 28.
É imprescindível expressar que os tempos gerados pelas técnicas de IC são apenas os tempos de verde. A quantidade de tempos que devem ser gerados consiste
então na quantidade de estágios em "verde", definidos na configuração do semáforo.
O tempo de vermelho para o mesmo estágio nas outras fases consiste na soma do
tempo de verde e do tempo de amarelo, ambos das outras fases. O tempo de amarelo
é fixo e pode ser definido na configuração do ciclo do cruzamento, a partir da opção
Entreverdes. (Figura 23). Se esse valor não for definido nessa opção, será utilizado o
tempo de amarelo padrão determinado no instante da geração de tempos (Figura 27.
O diagrama de tempos simplificado, apresentado na Figura 29, exemplifica o processo
77
Figura 28: Processo de geração e avaliação dos tempos gerados
de cálculo do tempo de vermelho.
Após a geração dos tempos é possível que os resultados, com os conjuntos dos
tempos, sejam salvos em disco por meio da biblioteca XStream. O progresso da geração com o melhor resultado para cada etapa é também salvo no formato CSV3 , por
meio da biblioteca SuperCSV4 . Esse formato foi escolhido para facilitar a confecção
de gráficos mostrando a evolução das gerações nos algoritmos executados.
O GISSIM foi modificado também para permitir que os resultados da geração de
tempos sejam carregados para simulação. Como a geração de tempos é um processo
estocástico, essa funcionalidade é imprescindível para que os tempos possam ser
avaliados por meio de funções estatísticas.
3
4
Comma-separated values
http://supercsv.sourceforge.net/
78
Figura 29: Diagrama de tempos simplificado - cálculo do tempo de vermelho
Tempos em segundos. (V) − verde e (A) − amarelo
4.3
Nesse capítulo foram apresentados os passos para construção do gerador de tempos. O princípio de desenvolvimento foi baseado no trabalho de Saliba Neto (2009),
utilizando a arquitetura do SIG OpenJUMP. O trabalho daquele autor foi inicialmente
exposto, nos aspectos de sua modelagem e funcionalidades.
Após isso, as extensões realizadas no GISSIM foram relatadas, como a capacidade para a definição de múltiplas pistas para simulação e a gravação e recuperação
de veículos instrumentados. As limitações e restrições das extensões foram abordadas, como o processo de mudança de faixa de tráfego pelos veículos.
Por fim, o gerador de tempos foi descrito, com sua arquitetura e recursos. Foram
apresentadas as considerações para gerenciamento dos cruzamentos e semáforos.
As interfaces e os processos internos foram relatados, com suas aplicações e funcionalidades.
79
5
EXPERIMENTOS
Este capítulo tem por objetivo apresentar os experimentos realizados para avaliar
o gerador de tempos desenvolvido. Inicialmente, serão apresentadas as implementações para as técnicas de inteligência computacional utilizadas neste trabalho. Em
seguida, o cenário dos experimentos será abordado, com as devidas considerações
e adaptações. Os cálculos referentes ao Método de Webster serão apresentados,
com as devidas restrições e inferências. Os experimentos serão descritos, divididos
conforme o tipo de abordagem, com as respectivas análises e considerações.
5.1
Implementação das Técnicas de Inteligência Computacional
Esta seção apresenta a implementação das técnicas abordadas em 3.3, especificamente para a execução dos experimentos. Neste trabalho, tanto os indivíduos
(AG) quanto os anticorpos (CLONALG) foram codificados por meio de representação
binária, com resolução de 10 bits por variável, correspondendo a uma precisão de,
aproximadamente, 0, 02 segundos nos tempos calculados. Como o único tempo que é
gerado pelas técnicas é o tempo de verde, pois o tempo de vermelho do estágio em
questão corresponde ao somatório desses tempos nos demais estágios, o número de
variáveis depende do número de estágios em verde dos cruzamentos. O tempo de
amarelo pode ser definido por cruzamento ou a partir do tempo padrão no momento
da geração dos tempos.
5.1.1
Representação de uma solução
A representação de uma solução para o problema foi realizada a partir de uma cadeia de valores binários (vetor), conforme o número de variáveis em questão. A Figura
30 ilustra um solução para o problema com duas variáveis. Os índices acima dos valo-
5.1 Implementação das Técnicas de Inteligência Computacional
80
res representam a precisão e as variáveis foram distintas pelas cores branca e cinza.
A cada 10 números binários no vetor tem-se então 1 variável. Esse vetor simboliza
assim as características genéticas ou o genótipo. A combinação dos elementos desse
vetor forma as características reais ou o fenótipo. No exemplo da Figura 30, considerando a precisão de 10 bits por variável e o intervalo para geração de tempos entre 15
e 40 segundos, o resultado da combinação desses bits do vetor é de 18 segundos de
verde para a variável 01 e 34 segundos de verde para a variável 02.
Figura 30: Representação de uma solução com duas variáveis
5.1.2
Algoritmos Genéticos
Para a realização da reprodução da população nos experimentos realizados, os indivíduos (pais) foram selecionados por meio do método da roleta (ver seção 3.3.2.4),
no qual esses foram dispostos pelo valor da função de avaliação correspondente. Assim, os indivíduos mais aptos têm mais chances de serem selecionados para a geração de uma nova população.
A recombinação dos indivíduos (Crossover ) empregado neste trabalho foi realizado por variável. Para essa operação, dois pais são selecionados aleatoriamente e
em cada uma das variáveis é selecionado um ponto também aleatório para o corte
e combinação das informações. Esse processo é similar à recombinação a partir de
um ponto (ver seção 3.3.2.5), entretanto ele realizado para cada uma das variáveis. A
Figura 31 ilustra a parte inicial do processo, indicando o ponto de corte aleatório e por
variável (variável 01 e variável 02).
Em seguida, as informações dos pais são combinadas. A primeira parte da variável 1 é combinada com a segunda parte da variável 2 e primeira parte da variável 2 é
combinada com a segunda parte da variável 1. Esse processo acontece para todas
as variáveis. Consequentemente, ao final do processo de recombinação em todas
as variáveis, dois novos filhos são gerados. A Figura 32 mostra a combinação das
informações entre as variáveis.
5.1 Implementação das Técnicas de Inteligência Computacional
81
Figura 31: Seleção aleatória dos pais e dos pontos de corte por variável
Figura 32: Combinação das informações dos pais
Essa recombinação acontece a um percentual fixo durante todo o processo do
algoritmo. Nos novos filhos, com um percentual menor, acontece o processo de mutação. Neste trabalho, essa operação acontece em múltiplos bits, selecionados aleatoriamente, do indivíduo. O bit em questão é modificado de 0 para 1 ou de 1 para
0. A mutação acontece a um percentual bem inferior porque esse é um operador
secundário e responsável por realizar busca locais.
Na composição da nova população para a geração seguinte, a qual possui tamanho fixo, seleciona-se aleatoriamente um determinado número de pais da geração
corrente. O indivíduo mais apto na geração corrente também será inserido na nova
população, promovendo então o elitismo. A população é completada com os filhos
gerados, os quais também são selecionados aleatoriamente.
Os parâmetros de entrada definidos para o AG nesta implementação consistiram
do tamanho da população, número de gerações, taxa de crossover e taxa de mutação.
O critério de parada adotado foi o número de gerações. O melhor indivíduo em todas
as gerações é inserido na população resultante ao final da execução.
5.2 Cenário dos Experimentos
5.1.3
82
CLONALG
Na implementação do algoritmo CLONALG para a resolução do problema de geração de tempos, o número de clones por anticorpo, 𝑁𝑐 , foi determinado a partir da
Equação (3.1). Esse número é proporcional à afinidade do anticorpo e a um fator multiplicativo 𝛽. Os anticorpos são então clonados conforme o número 𝑁𝑐 determinado,
resultando em subconjuntos 𝐶𝑛 , sendo 𝑛 = [1..𝑁𝑐 ]. Cada clone foi modificado a partir
do operador de mutação e em seguida foi avaliado. Após a realização do processo de
avaliação, o anticorpo com maior afinidade de cada subconjunto foi selecionado para
a composição da nova população 𝐴𝑏. Dentre esses, 𝑑 anticorpos com baixa afinidade
foram substituídos por novos gerados aleatoriamente. O critério de parada adotado foi
o número de gerações.
5.2
Cenário dos Experimentos
Como prova de conceito do trabalho, desejou-se realizar os experimentos em uma
região mais próxima do real, a qual pudesse ser representada no SIG OpenJUMP e
recuperada pelo simulador. Outro ponto relevante é a possibilidade de comparação
objetiva com algum resultado prático e numérico da literatura. Assim, os experimentos
foram inspirados em Oliveira et al. (2005), que mesmo possuindo um foco diferente
do abordado neste trabalho, possui resultados consistentes e relevantes, os quais
satisfazem os critérios aqui definidos para escolha. O cenário representa uma área
real da cidade de Porto Alegre, RS. A Figura 33 representa a região abordada por
aqueles autores, com os cruzamentos e os semáforos considerados.
Conforme aqueles autores, a via principal (no mapa real, Av. Independência seguida da Av. Mostardeiro) tem oito semáforos controlados por agentes (cruzamentos
0 − 7), além de duas vias transversais: a Rua Garibaldi (composta pelos cruzamentos
8, 1, 9 e 10) e Av. Goethe (cruzamentos 5, 11 − 13). O fluxo de entrada na rede consiste
de 36 veículos inseridos por minuto nas três faixas da Av. Independência e na Avenida
Goethe e Rua Garibaldi inseridos a uma taxa de 24 veículos por minuto.
5.2.1
Preparação do Ambiente
Neste trabalho, a região em questão foi desenhada no SIG OpenJUMP, tendo
como base uma imagem de satélite obtida por meio do software Google Earth, versão
83
Figura 33: Sub-rede analisada por Oliveira et al. (2005), com a identificação dos cruzamentos
Adaptado de Oliveira et al. (2005)
5.0 (GOOGLE, 2009). A imagem foi inserida no SIG por meio do sistema de coordenadas Universal Transversa de Mercator (UTM)1 obtidas a partir do software em
questão. O simulador GISSIM utiliza essas coordenadas para cálculo da distância
percorrida pelos veículos. A Figura 34 demonstra a imagem de satélite inserida no
OpenJUMP.
Figura 34: Imagem de satélite inserida no SIG OpenJUMP
1
Esse sistema representa uma projeção cilíndrica da superfície terrestre, cuja unidade de medida é
o metro (SALIBA NETO, 2009).
84
Após a inserção da imagem no SIG foi necessário o desenho da sub-rede estudada, a qual está em escala real. Como o fluxo de veículos apresentado por Oliveira
et al. (2005) foi apenas para os trechos citados acima, esse desenho foi simplificado,
englobando apenas a região desses trechos. Os dados alfanuméricos desses trechos,
bem como os sentidos de movimento foram obtidos a partir do Google Maps2 por meio
de observação. A Figura 35 apresenta o desenho simplificado no OpenJUMP das características da sub-rede correspondente.
Figura 35: Desenho da sub-rede no SIG OpenJUMP
Os pontos de entrada de veículos na rede, no simulador GISSIM denominados
Source, foram considerados na Av. Independência (IND), com 36 veículos/minuto
(2.160 veículos/hora) e na Rua Garibaldi (GAR) com 24 veículos/minuto (1.440 veículos/hora). A Av. Goethe possui duas pistas, aqui tratadas como norte-sul (GNS) e
sul-norte (GSN), com a entrada também de 24 veículos/minuto em cada uma dessas
pistas. Por motivo de compatibilidade, cada uma das vias da rede possui três faixas
de circulação e apenas um sentido de circulação (mão única). Assim como Oliveira et
al. (2005), considerou-se que a probabilidade de um veículo convergir num determinado cruzamento é de 1/10. Essa probabilidade é definida no simulador pela inserção
de parâmetros de fluxo e conversão para cada cruzamento existente. A Figura 36
apresenta o desenho do cenário no simulador a partir da recuperação da rede que foi
2
http://maps.google.com.br/
85
representada no OpenJUMP.
Figura 36: Desenho da sub-rede pelo simulador GISSIM
5.2.2
Função de Avaliação
Em virtude da integração do gerador de tempos ao simulador, cada conjunto de
configurações gerado deveria ser simulado para avaliação dos resultados. Assim,
levou-se em consideração um período de 3.600 passos (1 hora) de simulação. Definiuse então Equação (5.1), na qual são atribuídas ponderações para os veículos que
deixaram a simulação pela via em questão. A maximização desta função define a
aptidão do indivíduo ou a afinidade do anticorpo.
𝑓 (⋅) = (𝑊𝐼𝑛𝑑 × 𝑁𝐼𝑛𝑑 ) + (𝑊𝐺𝑎𝑟 × 𝑁𝐺𝑎𝑟 ) + (𝑊𝐺𝑛𝑠 × 𝑁𝐺𝑛𝑠 ) + (𝑊𝐺𝑠𝑛 × 𝑁𝐺𝑠𝑛 )
sendo:
𝑾𝑰𝒏𝒅 : ponderação para a Av. Independência;
𝑵𝑰𝒏𝒅 : número de veículos que deixaram a simulação pela Av. Independência;
𝑾𝑮𝒂𝒓 : ponderação para a Rua Garibaldi;
(5.1)
86
𝑵𝑮𝒂𝒓 : número de veículos que deixaram a simulação pela Rua Garibaldi;
𝑾𝑮𝒏𝒔 : ponderação para a Av. Goethe (N/S);
𝑵𝑮𝒏𝒔 : número de veículos que deixaram a simulação pela Av. Goethe (N/S);
𝑾𝑮𝒔𝒏 : ponderação para a Av. Goethe (S/N);
𝑵𝑮𝒔𝒏 : número de veículos que deixaram a simulação pela Av. Goethe (S/N).
5.2.3
Definição dos Tempos pelo Método de Webster
Para que a viabilidade do gerador de tempos pudesse ser verificada em relação
às técnicas convencionais, calculou-se os tempos de verde e ciclo para cada um dos
cruzamentos definidos por meio do Método de Webster, abordado na seção 2.1.3.
Entretanto, como os dados em cada cruzamento necessários para os cálculos não
foram abordados pela literatura ou são resultantes dos fluxos de entrada para as vias,
algumas inferências foram feitas para que essa definição pudesse ser realizada.
O fluxo de saturação 𝑆 foi estimado, a partir da Equação (2.1) e expresso em
veículos equivalentes/hora de tempo verde (𝑉𝑒𝑞 /ℎ𝑡𝑣). Considerando que cada trecho
recuperado é desenhado pelo simulador com uma largura de 5 metros, conforme atribuída por Saliba Neto (2009), e que foram utilizadas 3 vias para cada trecho do cenário,
a largura 𝐿 então é igual a 15 metros. Desse modo, 𝑆 é definido a seguir:
𝑆 = 525 ⋅ 𝐿
𝑆 = 525 ⋅ 15
(5.2)
𝑆 = 7875 𝑉𝑒𝑞 /ℎ𝑡𝑣
Para a definição do tempo perdido total 𝑇𝑝 , convencionou-se que esse seria realizado pelo somatório dos tempos de amarelo por cruzamento. Como o tempo de
amarelo definido para cada estágio do cruzamento é igual a 5 segundos e cada cruzamento possui dois estágios, o tempo perdido total por cruzamento então é igual a 10
segundos.
A demanda 𝑞𝑖 para cada cruzamento foi definida a partir do fluxo de entrada em
cada via. Considerando que a probabilidade de um veículo convergir num determinado
cruzamento é de 1/10, conforme definido por Oliveira et al. (2005), a cada cruzamento
87
calculou-se o número de veículos que seguem em frente e os que convergem para
outra via. Os veículos que saem de um cruzamento são utilizados como entrada para
o cruzamento seguinte. Quando o valor de entrada para uma das vias do cruzamento
não podia ser definido, convencionou-se utilizar como referência o valor da outra via.
A Figura 37 exemplifica o cálculo da demanda para dois cruzamentos em sequência.
O sentido do movimento é indicado pelas setas. A entrada de veículos é indicado por
𝐸𝑛 , enquanto a saída é representada por 𝑆𝑛 . Esse exemplo demonstra o cálculo, por
exemplo, para os veículos que saem do cruzamento em 𝑆2 , os quais são resultantes
do número de veículos que convergem em 𝐸1 acrescido ao número de veículos que
seguem diretamente pela entrada 𝐸2 .
Figura 37: Exemplo do Cálculo da Demanda
A partir do fluxo de saturação 𝑆 e da demanda do cruzamento 𝑞𝑖 , calculou-se o
a taxa de ocupação 𝑦𝑖 para cada via do cruzamento, por meio da Equação (2.3). O
somatório das taxas de ocupação 𝑌 para cada via é definido conforme a Equação
(2.5).
Após a definição dos parâmetros, calculou-se o tempo de ciclo ótimo, segundo
Webster, para cada cruzamento da rede, por meio da Equação (2.6), e os tempos de
verde efetivo e verde real para cada fase do cruzamento a partir da Equação (2.7) e da
Equação (2.8), respectivamente. Como a demanda 𝑞𝑖 foi definida conforme a probabilidade dos veículos convergirem num determinado cruzamento, o tempo de verde real
resultante para algumas fases da interseção foi muito baixo, com valores próximos a 1
segundo. Partindo do princípio que esses valores não condizem com situações reais
de tráfego e seguindo o que recomenda o DENATRAN (1984), convencionou-se que
o tempo de verde para uma fase deve ser, no mínimo, igual a 15 segundos. A partir
5.3 Resultados Práticos e Análises
88
da definição desses tempos de verde, foram realizadas simulações, conforme os procedimentos definidos na seção 5.3.1, para que esse método pudesse ser comparado
com a referência da literatura utilizada e com os resultados obtidos pela geração de
tempos por meio das técnicas de IC empregadas.
5.3
Resultados Práticos e Análises
Nesta seção serão apresentados os resultados e análises para a avaliação e validação do gerador de tempos desenvolvido. As considerações gerais para os experimentos realizados serão descritas inicialmente. Em seguida, serão relatados os experimentos sem e com ponderações para Função de Avaliação. No terceiro experimento
serão descritos os resultados quando o tempo de execução do gerador foi próximo a
1 minuto, e comparados aos resultados obtidos a partir do Método de Webster. Posteriormente, a avaliação geral dos experimentos será apresentada, com as devidas
considerações e análises.
5.3.1
Considerações Iniciais
Como a geração dos tempos é um processo estocástico, o melhor resultado ao
final da geração de tempos foi simulado por 10 vezes, com 10.800 passos (3 horas) para
cada instância de simulação. Oliveira et al. (2005) avaliaram em seus experimentos o
tempo médio de percurso nas vias definidas no tópico anterior. Para que esse tipo de
informação pudesse ser avaliada, veículos instrumentados cíclicos foram inseridos em
cada ponto de entrada da rede nos passos 1, 10, 100, 1.000 e 5.000, e o tempo médio
de percurso desses veículos nas vias foi comparado com os resultados em questão. É
importante salientar que Oliveira et al. (2005) não levaram em consideração a geração
dos tempos e sim a coordenação dos semáforos a partir de planos definidos. Assim,
não era objetivo daquele trabalho otimizar nenhum critério de tráfego pré-definido.
Entretanto, os resultados daqueles autores foram imprescindíveis para comparação e
análise dos resultados deste trabalho.
Oliveira et al. (2005) realizaram quatro tipos de experimentos, como segue: no
primeiro tipo (Tipo I) o cenário é ideal e abstrato no qual não há semáforos e por consequência, não há desaceleração causada por filas. Nesse cenário, que representa
uma situação irreal, o cruzamento é adimensional, logo veículos podem cruzá-lo sem
89
colisões. No segundo (Tipo II), é o cenário no qual todos os semáforos da rota principal (Av. Independência + Av. Mostardeiro) estão sincronizados de maneira fixa e
pré-determinada, executando planos que priorizam esta via. No terceiro (Tipo III) é
o cenário no qual todos os semáforos executam planos que não priorizam nenhuma
rota. No quarto (Tipo IV ) os semáforos são controlados por agentes com comportamento de inseto social de acordo com o modelo proposto. Nesse caso, a abordagem
proposta foi simulada de duas maneiras diferentes: atualização do limiar de resposta
utilizando a função linear (Tipo IV - Linear ) ou a função exponencial (Tipo IV - Exponencial) de sucesso (OLIVEIRA et al., 2005). Como o Tipo I dos experimentos aborda
uma situação irreal, neste trabalho ele não foi considerado e os resultados foram comparados com os demais tipos. Os resultados apresentados por aqueles autores para
a Av. Goethe foram utilizados neste trabalho como referência em ambos os sentidos
discriminados (norte-sul e sul-norte).
Os parâmetros utilizados pelas técnicas de IC para a geração de tempos foram
obtidos por meio de experimentação. Além desses, serão descritos os parâmetros
referentes ao GISSIM-TL, como o intervalo permitido para geração dos tempos de
verde e o tempo de amarelo para cada semáforo. Serão apresentados os resultados
com a variação da ponderação da Função de Avaliação e a comparação de execuções
rápidas do gerador de tempos com o Método de Webster. Os experimentos foram
executados em um computador com processador Intel Core 2 Duo E6550 de 2.33
GHz, com 2GB de memória RAM, sob plataforma Microsoft Windows Vista.
As tabelas apresentam os resultados obtidos após a geração de tempos com o
emprego das técnicas de IC, bem como a comparação com os dados obtidos pela
simulação a partir do Método de Webster e por Oliveira et al. (2005). Para cada uma
das vias, serão apresentados o tempo médio de percurso em segundos, conforme o
tipo do experimento, e o percentual de diferença em relação à técnica utilizada. A
diferença foi calculada levando-se em consideração o tempo médio de percurso da
referência em questão e do resultado desses tempos obtido a partir das simulações,
após os tempos gerados por meio das técnicas de IC, conforme a Equação (5.3).
Nas tabelas, os resultados negativos, representados em vermelho, indicam a melhora
obtida por meio das técnicas empregadas.
(
𝐷=
sendo:
𝑅𝑂 − 𝑅𝐿
× 100
𝑅𝐿
)
(5.3)
90
∙ 𝐷: percentual de diferença (%);
∙ 𝑅𝑂: tempo médio de percurso obtido por meio das técnicas de IC;
∙ 𝑅𝐿: tempo médio de percurso de referência.
5.3.2
Parâmetros para os experimentos com variação da ponderação da Função de Avaliação
Os parâmetros para as técnicas de IC, bem como para o gerador de tempos, utilizados na execução dos experimentos dessa seção, são descritos nas Tabelas 3 e
4, respectivamente. Como o número de indivíduos e anticorpos avaliados em cada
geração difere entre as técnicas utilizadas, o número de gerações, o tamanho da população e o tamanho do repertório foram definidos afim de garantir que o número total
de avaliações realizadas fosse próximo em ambas as técnicas. O total de avaliações
realizadas na execução de cada técnica foi de, aproximadamente, 5.000. Outro fator
é permitir uma análise justa entre as técnicas, seja pelos resultados ou pelo tempo
de execução. Essa consideração fez com que ambas as técnicas, indiferentemente
da ponderação da Função Avaliação, processassem por 4 horas, em média, para a
geração dos tempos, conforme o critério de parada adotado.
Tabela 3: Parâmetros AG/GISSIM-TL
Parâmetro
5.3.3
Valor
Tamanho da população
Número de gerações
Taxa de crossover
Taxa de mutação
50 indivíduos
100
85%
1%
Tempo mínimo
Tempo máximo
Tempo de amarelo
15 segundos
40 segundos
5 segundos
Resultados com Função de Avaliação sem Ponderações
Os experimentos foram realizados, inicialmente, levando-se em consideração a
Função de Avaliação sem ponderações (FASP), na qual os valores para 𝑊𝑣𝑖𝑎 foram
iguais a 1. O resultado das avaliações dos indivíduos e anticorpos será apresentado, bem como o número de veículos gerados e coletados durante a simulação. Em
91
Tabela 4: Parâmetros CLONALG/GISSIM-TL
Parâmetro
Valor
Tamanho do repertório 𝐴𝑏
Clonagem por anticorpo (Fator 𝛽)
Probabilidade de hipermutação
Substituição de anticorpos (Fator 𝑑)
50
61
20%
10%
20%
Tempo mínimo
Tempo máximo
Tempo de amarelo
15 segundos
40 segundos
5 segundos
seguida, os resultados referentes ao tempo médio de percurso serão descritos e as
respectivas considerações. Os parâmetros para os experimentos foram definidos na
seção 5.3.2.
5.3.3.1
Resultados
O resultado das avaliações dos indivíduos e anticorpos apresenta o valor obtido a
partir da Função de Avaliação sem ponderação. É apresentado o melhor resultado a
cada 50 avaliações realizadas pelos métodos de IC. A Figura 38 ilustra as avaliações,
sendo que o CLONALG apresentou melhores resultado que o AG.
Como a Função de Avaliação considera o número de veículos que deixaram a
simulação, a Tabela 5 apresenta a comparação do número total de veículos que foram
gerados e o número de veículos que foram coletados em algum ponto de saída. A
melhora em relação ao Método de Webster foi calculada a partir da Equação (5.3). O
valor positivo indica que mais veículos foram coletados a partir das simulações com o
tempos gerados pelas técnicas de IC.
Tabela 5: Veículos que deixaram a Simulação - FASP
Experimento
Webster
AG
CLONALG
Veíc. gerados
Veíc. coletados
% Coletados
% Melhora (%D)
16.467
16.336
16.347
15.813
16.060
16.093
96,03%
98,31%
98,45%
–
2,38%
2,52%
A Tabela 6 apresenta os resultados referentes à Av. Independência. O tempo
médio de percurso obtido a partir do Método de Webster foi superado por ambas as
técnicas, sendo que com o AG a melhora foi próxima à 9%. Em relação à literatura, a
92
Figura 38: Resultado das Avaliações - Função de Avaliação sem Ponderação
melhora foi relativa em experimentos do Tipo IV, com superação apenas no Tipo IV Linear.
Tabela 6: Resultados - Av. Independência - Função de Avaliação sem Ponderação
Os resultados para Rua Garibaldi são apresentados na Tabela 7. Em relação à
literatura, todos os resultados foram superados por ambas as técnicas, com valores,
no mínimo, próximos a 18% e superiores à 70%. Para o Método de Webster, o valor foi
atingido. Considerando-se que apenas o cruzamento dessa via com a Av. Indepen-
93
dência possui movimentos conflitantes de tráfego, o limite inferior determinado para o
tempo de verde e que em cruzamentos isolados o Método de Webster determina o
tempo de ciclo ótimo (ver seção 2.1.3), é possível que o tempo obtido para essa via
seja o mínimo. Assim, o CLONALG conseguiu atingir o menor tempo possível para
via, conforme determinado pelo Método de Webster.
Tabela 7: Resultados - Rua Garibaldi - Função de Avaliação sem Ponderação
A Tabela 8 apresenta os resultados para a Av. Goethe, no sentido norte-sul. Para
esta via, o Método de Webster foi superado pelo CLONALG com valor próximo à 7%.
Os resultados, se comparados à literatura, foram superados por ambas as técnicas,
com valores superiores a 67%.
Tabela 8: Resultados - Av. Goethe (N/S) - Função de Avaliação sem Ponderação
Os resultados apresentados na Tabela 9 para a Av. Goethe, no sentido sul-norte,
foram os que demonstraram os melhores resultados em relação ao Método de Webster
94
para ambas as técnicas, se comparados aos demais experimentos dessa seção, com
valores superiores a 13%.
Tabela 9: Resultados - Av. Goethe (S/N) - Função de Avaliação sem Ponderação
5.3.3.2
Considerações sobre os Resultados
Os resultados dessa seção para a Av. Independência em relação à literatura mostraram uma melhora pequena. Como essa via é a que possui o maior fluxo de entrada
de veículos, a melhora em relação ao Método de Webster evidencia a restrição desse
método. O método aborda apenas cruzamentos isolados, enquanto as técnicas de IC
conseguiram reduzir os tempos médios de percurso da rede de tráfego como um todo.
Outra situação que reforça esse fato é a relação de veículos que foram gerados e coletados pela simulação, apresentados na Tabela 5. Essa relação para as técnicas de IC
foi superior em mais de 2%. Para as demais vias, esses resultados foram consistentes,
com os quais os resultados da literatura foram melhorados. Em relação ao Método de
Webster, essas vias demonstraram superação também, em até 13%. Esse método
apresentou inclusive alguns resultados melhores em relação à literatura adotada. A
condição da Rua Garibaldi, como descrito anteriormente, apresenta o tempo mínimo
para via, sendo esse atingido pelo CLONALG. Essa técnica ainda, como mostrado na
Figura 38, obteve uma melhor evolução para a Função de Avaliação. Nas vias em que
uma das técnicas foi superior a outra em relação ao Método de Webster, esse fato
também se repetiu em relação à literatura. Tal situação pode sugerir que as ponderações para as vias podem variar conforme a técnica utilizada. As técnicas possuem
operadores diferentes e, consequentemente, percorrem e avaliam de modo peculiar o
espaço de busca.
5.3.4
95
Resultados com Função de Avaliação com Ponderações
Os resultados desta seção foram realizados a partir da Função de Avaliação com
ponderações (FACP). O fluxo de entrada de veículos na rede considerado para a Av.
Independência, conforme determinado por (OLIVEIRA et al., 2005), é maior em relação
às demais vias e, em condições reais do trânsito, essa avenida necessita de maiores
tempos de verde para garantir a fluidez do tráfego. Para os experimentos demonstrados na seção 5.3.3, essa via apresentou uma melhora pequena em relação à literatura
e razoável em relação ao Método de Webster. Para que essa via fosse analisada de
acordo com situações reais de tráfego, experimentos foram realizados a partir da ponderação do número de veículos que deixaram a rede durante a simulação por essa
via, sendo 𝑊𝐼𝑛𝑑 = 5. Para as demais vias, as ponderações 𝑊𝑣𝑖𝑎 foram iguais a 1. Os
demais parâmetros para os experimentos foram definidos na seção 5.3.2.
5.3.4.1
Resultados
O resultado das avaliações dos indivíduos e anticorpos apresenta o valor obtido
a partir da Função de Avaliação sem ponderação. É apresentado o melhor resultado
a cada 50 avaliações realizadas pelos métodos de IC. A Figura 39 ilustra as avaliações, sendo que ambas as técnicas apresentaram resultados próximos, entretanto a
evolução do CLONALG foi melhor em relação ao AG.
A Tabela 10 apresenta a comparação do número total de veículos que foram gerados e o número de veículos que foram coletados em algum ponto de saída. A melhora
em relação ao Método de Webster foi calculada a partir da Equação (5.3). O valor positivo indica que mais veículos foram coletados a partir das simulações com o tempos
gerados pelas técnicas de IC. Os resultados apresentaram uma pequena redução na
melhor se comparados aos resultados da seção anterior (ver Tabela 5). Entretanto, a
melhora ainda supera o Método de Webster em mais de 2%.
Tabela 10: Veículos que deixaram a Simulação - FACP
Experimento
Webster
AG
CLONALG
Veíc. gerados
Veíc. coletados
% Coletados
% Melhora (%D)
16.467
16.335
16.340
15.813
16.040
16.059
96,03%
98,20%
98,29%
–
2,26%
2,35%
A Tabela 11 apresenta os resultados referentes à Av. Independência. O CLONALG
96
Figura 39: Resultado das Avaliações - Função de Avaliação com Ponderação
conseguiu uma redução em relação ao Método de Webster de, aproximadamente,
10%. Esta técnica ainda obteve resultados mais consistentes em relação ao experimento da seção 5.3.3, conforme os referenciais adotados. O AG, entretanto, apresentou resultados inferiores aos apresentados anteriormente. Ainda assim, conseguiu
superar o Método de Webster em quase 2%.
Tabela 11: Resultados - Av. Independência - Função de Avaliação com Ponderações
Para a Rua Garibaldi, os resultados são apresentados na Tabela 12. É possível
97
observar que o tempo médio de percurso para essa via aumentou, o que fez com que
o percentual de melhora fosse menor. Essa questão foi mais acentuada em relação ao
Método de Webster. Em relação à literatura, os resultados foram muito consistentes
ainda, com melhora acima de 60%.
Tabela 12: Resultados - Rua Garibaldi - Função de Avaliação com Ponderações
A Tabela 13 apresenta os resultados para a Av. Goethe no sentido norte-sul.
Em relação ao Método de Webster, a melhora aproximou-se de 10% por meio do
CLONALG, sendo essa maior se comparados aos resultados da seção 5.3.3. Para o
AG houve ainda melhora se comparados aos resultados daquela seção. Os resultados
em relação à literatura, de modo geral, foram melhores que os apresentados na Tabela
8, com valores superiores a 68%.
Tabela 13: Resultados - Av. Goethe (N/S) - Função de Avaliação com Ponderações
Para o sentido sul-norte da Av. Goethe, os resultados são apresentados na Tabela
98
14. Nessa via, é possível notar que os tempos médios em relação aos apresentados
na Tabela 9 aumentaram. Essa situação é mais notória em relação ao Método de
Webster, principalmente para o CLONALG. Em relação à literatura, a redução foi
menor, mas ainda com valores superiores a 60%.
Tabela 14: Resultados - Av. Goethe (S/N) - Função de Avaliação com Ponderações
5.3.4.2
Os resultados apresentados nesta seção foram consistentes e comprovaram a
eficiência das técnicas de AG. O número de veículos que deixaram a rede nestes
experimentos foram próximos aos apresentados na seção 5.3.3. A Av. Independência
apresentou melhora em relação ao resultados anteriores, principalmente se comparada ao Método de Webster. A ponderação utilizada mostrou-se efetiva, contribuindo
para o que foi apresentado. Era esperado também que as demais vias apresentassem
valores superiores em relação aos experimentos anteriores, devido à essa ponderação. Isso condição foi mais explícita para a Rua Garibaldi. Mesmo assim, as demais
vias mostraram, em determinados experimentos, resultados superiores a 60%. É possível afirmar que o observado nesses experimentos reflete a situação real do tráfego
no cenário de estudo, no qual o fluxo maior de veículos concentra-se na Av. Independência, exigindo porções maiores do tempo de verde. A ponderação dessa via
seguramente aumentaria o tempo de percurso em relação às vias transversais, os
quais são considerados aceitáveis, pois essas vias não foram muito prejudicadas, se
observados os resultados da seção 5.3.3.
5.3.5
99
Resultados com tempo de execução rápida
Esta seção apresenta os resultados da simulação com os tempos obtidos a partir
da execução rápida do gerador de tempos, sendo próxima a 1 minuto, e sem a ponderação da função de avaliação. Esses resultados foram comparados com o Método
de Webster e com a literatura de referência. O objetivo desses experimentos é avaliar
o resultado do gerador de tempos em situações nas quais são necessárias respostas
rápidas para a tomada de decisão pelos engenheiros de tráfego. Cenários como esses são, por exemplo, acidentes de trânsito, desastres naturais (alagamentos, queda
de árvores), veículos com problemas mecânicos e congestionando vias, dentre outros. Esses acontecimentos exigem o desvio de trânsito e a organização rápida dos
semáforos.
5.3.5.1
Parâmetros
O critério de parada adotado ainda foi o número de gerações, entretanto os parâmetros foram ajustados para que a execução fosse próxima a 1 minuto. Os parâmetros
para os experimentos dessa seção são descritos nas Tabelas 15 e 16.
Tabela 15: Parâmetros AG/GISSIM-TL
Parâmetro
5.3.5.2
Valor
Tamanho da população
Taxa de crossover
Taxa de mutação
3 indivíduos
2
85%
1%
Tempo mínimo
Tempo máximo
Tempo de amarelo
15 segundos
40 segundos
5 segundos
Resultados
A Tabela 17 apresenta a comparação do número total de veículos que foram gerados e o número de veículos que foram coletados em algum ponto de saída. A melhora
em relação ao Método de Webster foi calculada a partir da Equação (5.3). O valor
positivo indica que mais veículos foram coletados a partir das simulações com o tempos gerados pelas técnicas de IC. Os resultados foram relativamente superiores aos
apresentados nas Tabelas 5 e 10.
100
Tabela 16: Parâmetros CLONALG/GISSIM-TL
Parâmetro
Valor
Tamanho do repertório 𝐴𝑏
Clonagem por anticorpo (Fator 𝛽)
Probabilidade de hipermutação
Substituição de anticorpos (Fator 𝑑)
1
8
20%
10%
20%
Tempo mínimo
Tempo máximo
Tempo de amarelo
15 segundos
40 segundos
5 segundos
Tabela 17: Veículos que deixaram a Simulação - Execução Rápida
Experimento
Webster
AG
CLONALG
Veíc. gerados
Veíc. coletados
% Coletados
% Melhora (%D)
16.467
16.351
16.337
15.813
16.105
16.100
96,03%
98,49%
98,55%
–
2,57%
2,62%
A Tabela 18 apresenta os resultados referentes à Av. Independência. O AG conseguiu superar o Método de Webster em quase 2%, enquanto o CLONALG apresentou
valores relativamente próximos. Em relação à literatura, essa melhora também pode
ser observada em experimentos do Tipo IV.
Tabela 18: Resultados - Av. Independência - Execução Rápida
Os resultados para Rua Garibaldi são apresentados na Tabela 19. Em relação
ao Método de Webster, as técnicas apresentaram melhoras relativas. Para as demais
referências, as técnicas conseguiram reduções significativas em todos os tipos de
101
experimentos, com algumas reduções próximas a 70%.
Tabela 19: Resultados - Rua Garibaldi - Execução Rápida
A Tabela 20 apresenta os resultados para a Av. Goethe, no sentido norte-sul. O
AG para esta via também apresentou reduções para o Método de Webster, com valor
próximo a 4% e o CLONALG apresentou resultados uma melhora relativa. Em relação
à literatura, todos os experimentos foram superados, com valores superiores a 62%.
Tabela 20: Resultados - Av. Goethe (N/S) - Execução Rápida
mostram reduções em relação ao Método de Webster superiores a 7, 5%. Além disso,
se comparados à literatura, todos os resultados também foram superados, com valores
superiores a 61%, em alguns experimentos.
102
Tabela 21: Resultados - Av. Goethe (S/N) - Execução Rápida
5.3.5.3
Os resultados apresentados nesta seção mostraram que, mesmo o tempo de execução sendo baixo, as técnicas de IC conseguiram produzir resultados consistentes,
superando o Método de Webster e a referência da literatura. A geração dos tempos
nessas condições consegue atender plenamente à necessidade de engenheiro de
tráfego em situações críticas, nas quais são exigidas medidas e ações rápidas. Outro
ponto relevante é que os resultados tendem a evoluir quando são executados por mais
tempo, a partir de um número maior de gerações e indivíduos/anticorpos.
5.3.6
Análise Geral dos Resultados
Nos experimentos, a condição de trânsito mais próxima do real foi representada, a
partir do momento em que a avenida de maior fluxo foi ponderada. Essa situação conseguiu reduzir, mesmo que relativamente, o tempo médio de percurso para a avenida
principal, ao passo que para as demais esse tempo foi acrescido.
Mesmo que o Método de Webster consiga determinar o ciclo ótimo para um cruzamento, ele não é capaz de garantir que toda a microrregião seja beneficiada. Isso
pode ser observado nos experimentos, nos quais os resultados desse método foram
superados pelas técnica de IC. Outra observação é que o número médio de veículos
que deixaram a rede durante a simulação dos tempos gerados pelas técnica de IC foi
maior em relação ao método, o que garante o fluxo mais efetivo de veículos.
O tempo de execução para as técnicas de IC, em média 4 horas, é aceitável e viá-
103
vel para situações de planejamento e organização do trânsito pelos engenheiros de
tráfego. Nas situações que exigem respostas de operações em tempo real, as técnicas sendo executadas rapidamente, em média 1 minuto, mostraram resultados muito
satisfatórios, nos quais conseguiram superar os referencias adotados. Em ambas aplicações, pode-se ainda empregar outros critérios de parada, que não o número de gerações, como, por exemplo, o número de iterações sem melhora, tempo de execução,
valor limite para a função de avaliação, dentre outros. Outro ponto a ser observado é
na evolução da geração de tempos, na qual são computados o valor ponderado dos
veículos que deixaram a simulação. A melhor execução não foi necessariamente o
melhor resultado para as vias, não havendo uma relação direta, pois considerou-se
para avaliação das vias com a literatura o tempo médio de percurso.
A ponderação da função de avaliação implicou no aumento e redução dos tempos
médios de percurso não só na via principal. Essa situação sugere que as avaliações
sejam realizadas a partir de duas ou mais funções, por meio de técnicas de otimização multiobjetivo. Outro ponto relevante é o modo que as avaliações são realizadas.
A geração de tempos depende das simulações para a avaliação dos resultados por
meio da função de avaliação. Como a simulação é estocástica, a partir de eventos
discretos, consequentemente, a função de avaliação também é estocástica no tempo.
Essa característica de aleatoriedade aumenta a complexidade do problema e implica
na utilização de outras técnicas, como a otimização robusta com incertezas (noise
optimization).
A Av. Independência, conforme mostrado na Tabela 22 apresentou melhoras relativas se comparada à literatura, superando os resultados das mesma em alguns
resultados. Em relação ao Método de Webster a melhora foi mais significativa e próximas a 10%. A situação apresentada sugere que ponderações maiores sejam utilizadas
para essa via e/ou ponderações valores menor que 1, com valores, por exemplo, no
intervalo [0, 1..0, 99].
Os resultados para a Rua Garibaldi, se comparados a esse método e levando-se
em consideração ao que foi abordado para a via na seção 5.3.3, pode ter atingido ao
menor tempo. A partir do instante que a função de avaliação foi ponderada, os tempos
para essa via aumentaram, o que sugere que essa via também seja ponderada, com
peso maior que 1. Essa situação pode ser observada na Tabela 23.
Para a Av. Goethe, no sentido norte-sul, observou-se, como na da Tabela 24, que
Tabela 22: Resultados - Av. Independência - Análise Geral
Tabela 23: Resultados - Rua Garibaldi - Análise Geral
104
105
nos experimentos com a função de avaliação com ponderação da avenida principal, os
tempos médios de percurso para essa via reduziram, proporcionando um fluxo maior
de tráfego. Entretanto, o fluxo dessa via pode ter ocasionado a elevação do tempo
médio de percurso para a avenida principal. Isso pode sugerir que seja aplicado à
essa via uma ponderação menor que 1, privilegiando a avenida principal.
Tabela 24: Resultados - Av. Goethe (N/S) - Análise Geral
mostram que a via teve o tempo de percurso aumentado a partir do momento em
que a Av. Independência foi ponderada. Esse acontecimento pode ser justificado
pela ponderação aplicada à via principal e/ou à necessidade de ponderação da via no
sentido contrário, como abordado anteriormente. Para a execução rápida da geração
de tempos, essa via apresentou os melhores resultados, com valores superiores a 7%.
Tabela 25: Resultados - Av. Goethe (S/N) - Análise Geral
Os resultados, de modo geral, são satisfatórios e comprovam a eficiência das téc-
106
nicas de IC. A avaliação dos resultados a partir da literatura representaram ganhos
significativos, com melhora acima de 60% em alguns experimentos. Em quase todos
os experimentos a literatura em referência foi superada. Mesmo que a abordagem
dessa referência seja diferente, ela foi imprescindível para a avaliação e a validação
das técnicas de IC empregadas. A execução rápida da geração de tempos apresentou
resultados consistem e viabilizou sua utilização em situações de operação do trânsito
em tempo real. Outro fator é que esse experimento evidenciou a evolução do processo de geração dos tempos, mostrando a funcionalidade dos operadores genéticos
das técnicas de IC.
5.4
Nesse capítulo foram apresentados os experimentos para a avaliação e validação
do gerador de tempos. Como prova de conceito, utilizou-se uma região da cidade de
Porto Alegre, sendo representada no SIG OpenJUMP e recuperada pelo simulador.
O ambiente foi preparado a partir da adaptação do trabalho de Oliveira et al. (2005).
Outra referência utilizada foi a partir do Método de Webster, com o cálculo do tempo
de ciclo ótimo, segundo esse método, para os cruzamentos definidos.
A realização de experimentos de geração dos tempos de semáforos e a comparação dos resultados da simulação com o Método de Webster e a literatura comprovam
a eficiência das técnicas empregadas. A literatura em questão foi imprescindível para
a validação dessa técnica, pois utilizou uma região real para a realização dos experimentos, a qual possui resultados práticos e numéricos. Os resultados desse trabalho
apresentaram reduções no tempo médio de percurso de mais de 60% em relação
ao referencial da literatura empregado. A comparação dos resultados com o Método
de Webster demonstraram o rendimento do tráfego comprometido por esse método,
observando-se o número médio de veículos que deixaram a simulação. Outro fato é
que os tempos de percurso, a partir dos resultados das técnicas de IC, foram superiores em alguns experimentos em relação ao Método de Webster, especialmente na
avenida principal, com ganhos de aproximadamente 10%. A execução rápida das técnicas de IC para a geração de tempos permite a aplicação em situações de tempos
real na operação do trânsito, nas quais respostas objetivas e eficientes são necessárias.
107
6
CONCLUSÃO
6.1
Discussões Finais
Os trabalhos realizados pelo projeto GEOPROC contribuíram efetivamente para a
evolução das pesquisas em Geoprocessamento e SIG, agregando técnicas de IC. Viana Jr. (2004) contribuiu amplamente ao utilizar a lógica Fuzzy na sugestão do melhor
caminho entre dois pontos em um sistema viário. Silva (2006) automatizou processo
de coleta dos dados de entrada para o sistema Fuzzy, o cálculo da ITT e a atualização dos valores associados aos arcos da rede. A agregação dessas funcionalidades
a um SIG livre e extensível foi um enorme passo para as pesquisas desse projeto,
construindo um arcabouço fundamental para a evolução dos trabalhos. Saliba Neto
(2009) modelou e implementou um simulador microscópico de tráfego urbano incorporado ao SIG OpenJUMP. A construção desse simulador permitiu a avaliação dos
resultados dos trabalhos de Viana Jr. (2004) e Silva (2006), a partir de experimentos
com o menor e melhor caminho.
Como a programação semafórica tem papel preponderante na administração do
trânsito, buscou-se nesse trabalho o desenvolvimento de um gerador de tempos semafóricos por meio de técnicas de IC, o qual estivesse incorporado ao simulador construído por Saliba Neto (2009) e ao SIG OpenJUMP. Os experimentos realizados em
uma região real permitiu a comprovação da hipótese levantada na seção 1.3, sendo
verificada a viabilidade desse gerador.
Um estudo sobre os SIG, programação semafórica e técnicas de IC foi apresentado inicialmente, objetivando a contextualização do leitor, bem como a apresentação
do estado-da-arte. Essa conceituação foi imprescindível para a evolução do trabalho,
como também a justificativa para a aplicação de IC, em virtude das técnicas obsoletas
para a definição dos tempos dos semáforos.
O objetivo geral proposto por esse trabalho, como mostrado, foi alcançado satis-
6.2 Contribuições do trabalho
108
fatoriamente. O gerador de tempos foi desenvolvido de acordo com as premissas
desejadas e a comparação dos resultados com a literatura pode ser realizada com
sucesso. O plugin construído foi integrado ao SIG OpenJUMP, seguindo as mesmas
abordagens propostas por Silva (2006) e Saliba Neto (2009). Os objetivos específicos propostos também foram alcançados plenamente, conforme pode-se observar a
seguir:
∙ Modelar e implementar um plugin que permita a geração de tempos semafóricos,
utilizando técnicas de inteligência computacional: este objetivo foi alcançado
conforme abordado na seção 4.2, a qual descreve a arquitetura e os módulos
implementados.
∙ Integrar esse plugin ao OpenJUMP e ao simulador desenvolvido por Saliba Neto
(2009): a integração ao SIG e ao simulador foi obtida, conforme descrito nas
seções 4.2.2 e 4.2.3, respectivamente.
∙ Validar o plugin desenvolvido com a execução de experimentos práticos em alguma região de interesse: os resultados apresentados e discutidos no Capítulo
5 comprovam a eficiência da ferramenta desenvolvida.
6.2
Contribuições do trabalho
O desenvolvimento deste trabalho contribuiu efetivamente para o projeto GEOPROC ao agregar o gerenciamento de semáforos e incorporar a geração de tempos
por meio de técnicas de IC. A arquitetura desenvolvida permite que outras técnicas
sejam utilizadas para a geração desses tempos e amplia as possibilidades para a
avaliação dos experimentos.
Do ponto de vista acadêmico, a construção desse arcabouço permitiu o estudo e
a agregação de técnicas de IC a um SIG, contribuindo com a metodologia proposta
no projeto GEOPROC. A comparação dos resultados com a literatura sugere o refinamento dos parâmetros, bem como a utilização de outras funções de avaliação.
Os conceitos de modelagem orientada a objetos e de padrões de projeto empregados permitiram o desenvolvimento de uma ferramenta que pode ser facilmente
estendida, possibilitando a incorporação de outras técnicas de IC para a geração de
tempos e/ou para a aplicação dessas técnicas em outros tipos análise no SIG.
6.3 Propostas para Trabalhos Futuros
109
Em nível prático, o gerenciamento dos semáforos foi desenvolvido seguindo os
conceitos e regras definidas conforme a legislação do Brasil. Essa consideração é
relevante, pois a ferramenta está condizente com a realidade das cidades brasileiras. Outro fator é que esse trabalho é baseado no paradigma de software livre, sem
custo financeiro para a aquisição do SIG e das bibliotecas utilizadas. Essa abordagem permite que os órgãos responsáveis pela administração de trânsito utilizem essa
ferramenta livremente, sem custos para a sua aquisição.
6.3
Propostas para Trabalhos Futuros
As pesquisas em relação ao trânsito urbano e a geoprocessamento têm muito a
evoluir. Entretanto, a construção de ferramentas é uma tarefa difícil e complexa, demandando enorme tempo para desenvolvimento. Neste aspecto, durante a execução
desse trabalho, algumas melhorias e inovações foram identificadas, as quais não puderam ser implementadas em virtude do tempo disponível e devido às propostas para
esse trabalho.
A seguir são apresentadas propostas para trabalhos futuros, tanto no âmbito do
simulador quanto do gerador de tempos:
∙ empregar alguma técnica de distribuição de probabilidade discreta, como a distribuição de Poisson, para implementar entradas aleatórias de veículos na rede
para simulação;
∙ aplicar outros operadores para as técnicas de inteligência computacional utilizadas para a geração de tempos;
∙ aplicar técnicas de otimização robusta, considerando a natureza estocástica da
função de avaliação;
∙ realizar a geração de tempos em um ambiente distribuído, aplicando as técnicas
de IC em um cluster, objetivando-se aumentar o desempenho dessas técnicas;
∙ realizar a geração de tempos que o fluxo de entrada do veículos varia com tempo
(otimização dinâmica). Pode-se aplicar, por exemplo, um acréscimo no fluxo de
20% a cada 3.600 passos de simulação (1 hora), o que representaria horários em
que o tráfego de veículos torna-se intenso.
6.3 Propostas para Trabalhos Futuros
110
∙ criar outros tipos de veículos para o simulador, como motocicletas, ônibus e caminhões;
∙ implementar no simulador a funcionalidade de zoom, pois, como a área de estudo é em tamanho real, a observação da simulação torna-se difícil para a avaliação da representação do desenho, bem como para a execução da simulação;
∙ incorporar à geração de tempos o critério de defasagem entre cruzamentos /
semáforos;
∙ realizar a geração de tempos associada ao sincronismo dos semáforos, seja por
meio de alguma técnica baseada em agentes sociais ou a partir de redes neurais
artificiais, por exemplo;
∙ permitir a definição de semáforos em qualquer parte da via e não somente nos
cruzamentos, como aplicado nesse trabalho;
∙ aplicar outras funções para a avaliação dos tempos gerados, relacionando, por
exemplo, o número de paradas e atrasos, consumo de combustível, emissão de
poluentes, dentre outros. Pode-se ainda aplicar otimização multiobjetivo para a
consideração simultânea desses critérios. Para a definição desses critérios e
outras funções de avaliação, sugere-se a leitura de Guberinić, Šenborn e Lazić
(2008).
111
Referências
ALMEIDA, P. E. M.; EVSUKOFF, A. G. Sistemas fuzzy. In:
. REZENDE, S. O.
Sistemas Inteligentes: fundamentos e aplicações. Barueri, SP: Manole, 2005. cap. 7,
p. 169–201.
. REZENDE,
ALMEIDA, P. E. M.; EVSUKOFF, A. G. Sistemas neuro fuzzy. In:
S. O. Sistemas Inteligentes: fundamentos e aplicações. Barueri, SP: Manole, 2005.
cap. 8, p. 203–2224.
ARAÚJO, D. R. C. d. Comparação das simulações de tráfego dos modelos SATURN e
DRACULA. Dissertação (Mestrado) — Universidade Federal do Rio Grande do Sul. Escola de Engenharia. Programa de Pós-Graduação em Engenharia de Produção, Porto
Alegre, Jun 2003. Disponível em: <http://www.lume.ufrgs.br/handle/10183/4162>.
BEST, E.; DEVILLERS, R.; KOUTNY, M. Petri net algebra. New York, NY, USA:
Springer-Verlag New York, Inc., 2001. ISBN 3-540-67398-9.
BHTRANS. Tabela 14: Posição Comparativa da Frota de Veículos,
por Tipo: 2004 a 2008. Jul 2009. Http://www.bhtrans.pbh.gov.br/. Empresa de Transportes e Trânsito de Belo Horizonte S/A. Disponível em:
<http://bhtrans.pbh.gov.br/portal/page/portal/portalpublico/Estatísticas e Publicações/Indicadores/AE Tabela 14>.
BRAGA, A. P.; CARVALHO, A. C. P. de Leon Ferreira de; LUDERMIR, T. B. Redes
. REZENDE, S. O. Sistemas Inteligentes: fundamentos e
neurais artificiais. In:
aplicações. Barueri, SP: Manole, 2005. cap. 6, p. 141–168.
BROCKFELD, E. et al. Optimizing Traffic Lights in a Cellular Automaton Model for City
Traffic. 2001. Disponível em: <http://www.citebase.org/abstract?id=oai:arXiv.org:condmat/0107056>.
BUCKEY, D. J. GIS Introduction. Jul 2009. Acessado em: 27/07/2009. Disponível em:
<http://bgis.sanbi.org/GIS-primer/index.htm>.
CÂMARA, G. Representação computacional de dados geográficos. In:
.
[s.n.], 2001. Atualizado em 04/06/2001. livro on-line Cap. 1. Disponível em:
<http://www.dpi.inpe.br/livros/bdados/cap1.pdf>.
CÂMARA, G.; DAVIS JR., C. Introdução à ciência da geoinformação. In:
.
Câmara, Gilberto; Davis Jr., Clodoveu Augusto; Monteiro, Antônio Miguel Vieira
(ed)., 2001. Atualizado em 04/06/2001. livro on-line Cap. 1. Disponível em:
<http://www.dpi.inpe.br/gilberto/livro/introd/cap1-introducao.pdf>.
Referências
112
CARVALHO, A. C. P. de Leon Ferreira de; BRAGA, A. de P.; LUDERMIR, T. B.
. REZENDE, S. O. Sistemas Inteligentes: fundamentos
Computação evolutiva. In:
e aplicações. Barueri, SP: Manole, 2005. cap. 9, p. 225–248.
CELIKYILMAZ, A.; TÜRKSEN, I. B. Modeling Uncertainty with Fuzzy Logic: With
Recent Theory and Applications. [S.l.]: Springer, 2009. 400 p. (Studies in Fuzziness
and Soft Computing, v. 240).
CERVANTES, S. G. d. S. Um Algoritmo Descentralizado para Controle
de Tráfego Urbano em Tempo Real. Tese (Doutorado) — Universidade
Federal de Santa Catarina, Florianópolis, Março 2005. Disponível em:
<http://www.tede.ufsc.br/teses/PEEL1031.pdf>.
COUTO, F. C.; BRITO, J. B.; ROCHA, E. R. D. OpenJUMP guia do usuário.
Pernambuco. Recife-PE, 2006.
DAVIS, M. JUMP Unified Mapping Platform. [S.l.], Mar 2003. Acessado em:
15/08/2009. Disponível em: <http://www.vividsolutions.com/JUMP/bin/JUMP%
20Technical%20Report.pdf>.
DE CASTRO, L. N. Engenharia Imunológica: Desenvolvimento e Aplicação de
Ferramentas Computacionais Inspiradas em Sistemas Imunológicos Artificiais. Tese
(Tese (doutorado)) — Universidade Estadual de Campinas, Faculdade de Engenharia
Elétrica e de Computação, Campinas, SP, Maio 2001. Orientador: Fernando José Von
Zuben.
DE CASTRO, L. N.; VON ZUBEN, F. J. The clonal selection algorithm with engineering
applications. In: In Proc. GECCO 2000 Workshop on Artificial Immune Systems. [S.l.]:
Morgan Kaufmann, 2000. p. 36–37.
DE CASTRO, L. N.; VON ZUBEN, F. J. Learning and optimization using the clonal
selection principle. Evolutionary Computation, IEEE Transactions on, v. 6, n. 3, p.
239–251, Jun 2002. ISSN 1089-778X.
DE CASTRO, L. N.; VON ZUBEN, F. J. Recent Developments in Biologically Inspired
Computing. [S.l.]: IGI Publishing, 2005.
DEMERS, M. N. Fundamentals of Geographic Information Systems. 3rd. ed. [S.l.]:
John Wiley & Sons, Inc., 2005. 480 p.
DENATRAN. Manual de Semáforos. 2a ed. ed. Brasília-DF - Brasil, Dezembro 1984.
DETRAN-SP. Frota de Veículos. Julho 2009. Site. Departamento Estadual de Trânsito
de São Paulo. Disponível em: <http://www.detran.sp.gov.br/frota/frota.asp>.
ESRI. GIS.com - the Guide to Geographic Information Systems - Environmental
Systems Research Institute, Inc. (ESRI). Jul 2009. Acessado em: 27/07/2009.
Disponível em: <http://www.gis.com/>.
FEBBRARO, A. D.; GIGLIO, D.; SACCO, N. On applying petri nets
to determine optimal offsets for coordinated traffic light timings. Intelligent Transportation Systems, 2002. Proceedings. The IEEE 5th
Referências
113
International Conference on, p. 773–778, 2002. Disponível em:
<http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=22289&arnumber=1041317>.
FOGEL, D. B. Evolutionary Computation: Toward a New Philosophy of Machine
Intelligence. 3rd. ed. [S.l.]: Wiley-IEEE Press, 2006. 296 p. p.
GIRAULT, C.; VALK, R. Petri Nets for System Engineering: A Guide to Modeling,
Verification, and Applications. Secaucus, NJ, USA: Springer-Verlag New York, Inc.,
2001. ISBN 3540412174.
GOLDBERG, D. E. Genetic Algorithms in Search, Optimization and Machine Learning.
Reading, Massachusetts: Addison-Wesley Publishing Company, 1989.
GOOGLE. Google Earth. Jul 2009. Http://earth.google.com/intl/pt/. Acessado em:
jul/2009.
GUBERINIĆ, S.; ŠENBORN, G.; LAZIĆ, B. Optimal Traffic Control: Urban
Intersections. [S.l.]: CRC Press, 2008. 368 p.
HAYKIN, S. Neural Networks and Learning Machines. 3rd. ed. [S.l.]: Prentice Hall,
2008.
HEYWOOD, I.; CORNELIUS, S.; CARVER, S. An Introduction to Geographical
Information Systems. [S.l.]: Prentice Hall, 2006.
HONG, Y.-S.; JIN, H.; PARK, C.-K. New electrosensitive traffic light
using fuzzy neural network. Fuzzy Systems, IEEE Transactions on,
v. 7, n. 6, p. 759–767, Dec 1999. ISSN 1063-6706. Disponível em:
<http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=17610&arnumber=81124>.
HONG, Y. S. et al. Estimation of optimal green time simulation using fuzzy neural
network. Fuzzy Systems Conference Proceedings, 1999. FUZZ-IEEE ’99. 1999 IEEE
International, v. 2, p. 761–766 vol.2, 1999.
LÄMMER, S.; HELBING, D. Self-control of traffic lights and vehicle flows in
urban road networks. Journal of Statistical Mechanics: Theory and Experiment,
v. 2008, n. 04, p. P04019 (34pp), 2008. Disponível em: <http://stacks.iop.org/17425468/2008/P04019>.
. The revised monograph on
LIEBERMAN, E.; RATHI, A. K. Traffic simulation. In:
traffic flow theory. EUA: Federal Highway Administration, 1997. cap. 10. Disponível
em: <http://web.tongji.edu.cn/ yangdy/its/tft/chap10.pdf>.
LIMA, C. M. V. Otimização de Trânsito - Uma Abordagem Utilizando Algoritmos
Genéticos. Dissertação (Graduação) — Universidade Federal de Pernambuco, Recife,
Agosto 2005. Disponível em: <http://www.cin.ufpe.br/ tg/2005-1/cmvl.doc>.
LIU, R. Dracula microscopic traffic simulator. Leeds: Institute of Transport
Studies, University of Leeds. Its Working Paper 431, Dez 1994. Disponível em:
<http://eprints.whiterose.ac.uk/2149/>.
Referências
114
LIU, R.; VILET, D. V.; WATLING, D. P. Dracula: Dynamic route assignment
combining user learning and microsimulation. In: In Proceeding PTRC Summer
Annual Conference, Seminar E. [s.n.], 1995. p. 143–152. Disponível em:
<http://www.its.leeds.ac.uk/software/dracula/pubs.html>.
LÓPEZ, S. et al. Artificial neural networks as useful tools for the optimization of the relative offset between two consecutive sets of traffic lights.
In: MIRA, J.; SÁNCHEZ-ANDRÉS, J. V. (Ed.). IWANN (2). Springer,
1999. (Lecture Notes in Computer Science, v. 1607), p. 795–804. Disponível em:
<http://www.aic.uniovi.es/secundino/pag_personal/documentos/Articulos/iwann99.doc>.
LOUREIRO, C. F. G.; GOMES, M. J. T. L.; LEANDRO, C. H. P. Avaliação do desempenho nos períodos de pico do tráfego de interseções semaforizadas com controle
centralizado em tempo fixo e real. Sinal de Trânsito - Site, p. 13, 20 Nov 2005. Acesso:
12 jun 2008. Disponível em: <http://www.sinaldetransito.com.br/artigos/scoot.pdf>.
LUNA, M. d. S. d. Sobre o Fluxo de Saturação: Conceituação, Aplicação, Determinação e Variação. Dissertação (Mestrado) — Universidade Federal do Ceará, Fortaleza,
Setembro 2003. Disponível em: <http://metro.det.ufc.br/petran/teses/tese21.pdf>.
MACHADO, A. P. Com 1,14 milhão de veículos, BH pode parar em 15 anos. Jul 2009.
Jornal O Tempo - Online. Publicado em: 20/07/2009. Acessado em: 29/07/2009.
Disponível em: <http://www.otempo.com.br/otempo/noticias/?IdNoticia=116416>.
MARTINS, E. Centro de BH será reformulado para atender copa do Mundo. Jul 2009.
Jornal O Tempo - Online. Publicado em: 24/07/2009. Acessado em: 29/07/2009.
Disponível em: <http://www.otempo.com.br/otempo/noticias/?IdNoticia=116811>.
MCTRANS, C. Traffic Software Integrated System - Corridor Simulation - TSISCORSIM. [S.l.], Jul 2008. Disponível em: <http://mctrans.ce.ufl.edu/featured/tsis/>.
MENESES, H. B.; CARVALHO, L. E. X.; LOUREIRO, C. F. G. Transcoot: uma
interface lógica para modelar e georeferenciar dados dinâmicos do tráfego urbano.
Sinal de Trânsito - Site, p. 10, 7 Set 2006. Acesso: 13 jun 2008. Disponível em:
<http://www.sinaldetransito.com.br/artigos/transcoot.pdf>.
MICHALEWICZ, Z. Genetic Algorithms + Data Structures = Evolution Programs.
Third. [S.l.]: Springer-Verlag, 1996.
MONTEIRO, P. R. d. S. Notas de Aula. [S.l.], 2008. Disponível em:
<http://etg.ufmg.br/˜paulo/Notas_de_Aula/>.
NEGNEVITSKY, M. Artificial Intelligence: A Guide to Intelligent Systems. 2. ed. [S.l.]:
Addison Wesley, 2005. 440 p.
NIITTYMÄKI, J. Fuzzy traffic signal control – principles and applications. Helsinki
University of Technology, v. 42, n. 1, p. 22–26, jan. 12 2002. Disponível em:
<http://lib.tkk.fi/Diss/2002/isbn9512257017/>.
O’FLAHERTY, C. A. Highways: Traffic Planning and Engineering. 3rd. ed. Lodon:
Edward Arnold Ltd., 1986.
Referências
115
OLIVEIRA, D. de et al. Coordenação dinâmica de semáforos: dois casos de estudo. XXV Congresso da Sociedade Brasileira de Computação : V Encontro Nacinal de Inteligência Artificia ENIA’2005, UNISINOS
- São Leopoldo/RS, p. 761–770, 22 a 29 julho 2005. Disponível em:
<http://www.sbc.org.br/bibliotecadigital/download.php?paper=328>.
OPENJUMP. OpenJUMP Project. Jul 2009. Acessado em: 13/07/2009. Disponível
em: <http://openjump.org>.
REZENDE, S. O. Sistemas Inteligentes - Fundamentos e Aplicações. 1a reimp.. ed.
Barueri, SP, Brasil: Manole, 2005. ISBN 85-204-1683-7.
ROSSETTI, R. et al. An agent-based framework for the assessment of drivers’
decision-making. In: Intelligent Transportation Systems, 2000. Proceedings. 2000
IEEE. [S.l.: s.n.], 2000. p. 387–392.
ROUPHAIL, N. M.; PARK, B. B.; SACKS, J. Direct Signal Timing Optimization:
Strategy Development and Results. [S.l.], Nov. 19-23 2000. Disponível em:
<citeseer.ist.psu.edu/rouphail00direct.html>.
SAKA, A. A.; ANANDALINGAM, G.; GARBER, N. J. Traffic signal timing at isolated
intersections using simulation optimization. In: WSC ’86: Proceedings of the 18th
conference on Winter simulation. New York, NY, USA: ACM, 1986. p. 795–801. ISBN
0-911801-11-1.
SALIBA NETO, T. Desenvolvimento de um SIG de código aberto para simulação
microscópica de tráfego urbano. Dissertação (Mestrado) — Centro Federal de
Educação Tecnológica de Minas Gerais - CEFET/MG, Belo Horizonte-MG, Março
2009.
SANCHEZ, J.; GALAN, M.; RUBIO, E. Applying a traffic lights evolutionary optimization
technique to a real case: "las ramblas"area in santa cruz de tenerife. Evolutionary
Computation, IEEE Transactions on, v. 12, n. 1, p. 25–40, Feb 2008. ISSN 1089-778X.
SHAMSI, U. GIS Applications for Water, Wastewater, and Stormwater Systems. 1. ed.
[S.l.]: CRC Press, 2005. 440 p.
SILVA, E. L. d.; MENEZES, E. M. Metodologia da Pesquisa e Elaboração de
Dissertação. 3. ed. Florianópolis: Laboratório de ensino a distância da UFSC, 2001.
121 p. Disponível em: <http://projetos.inf.ufsc.br/arquivos/Metodologia da Pesquisa 3a edicao.pdf>.
SILVA, G. Modelagem e Implementação de uma Ferramenta Inteligente e de Código
Aberto para Inserção Automática de Inferência Fuzzy em Sig Convencionais.
Dissertação (Mestrado) — CEFET-MG, Belo Horizonte-MG, Agosto 2006. Disponível
em: <http://www.mmc.cefetmg.br/info/downloads/D020-GabrieldaSilva.pdf>.
SILVA, G.; ALMEIDA, P. E. M. On the shortest path problem: a new approach
with fuzzy inference systems and conventional geographic information systems. VII
International Conference on Intelligent Systems Design & Applications, 2007, Rio de
Janeiro, RJ, Brasil. Proceedings of Seventh International Conference on Intelligent
Systems Design and Applications. Rio de Janeiro, RJ : UERJ, v. 1, 2007.
Referências
116
SILVA, G.; JR, G. V.; ALMEIDA, P. E. M. RTIGIS: um sistema de informação geográfico
inteligente para escolha de trajetos com geração automática de atributos fuzzy. V
ENIA - Encontro Nacional de Inteligência Artificial, 2005, São Leopoldo, RS. Anais do
V ENIA, 2005.
SMITH, R. D. Simulation article. Encyclopedia of Computer Science, Nature Publishing Group, 1998. Disponível em:
<http://www.modelbenders.com/encyclopedia/encyclopedia.html>.
SOUZA, M. J. F. Inteligência Computacional para Otimização. Ago 2009. Acessado
em: 10/08/2009. Disponível em: <http://www.decom.ufop.br/prof/marcone/Disciplinas/
InteligenciaComputacional/InteligenciaComputacional.htm>.
SUN MICROSYSTEMS, INC. Developer Resources for Java Technology. Julho 2008.
Disponível em: <http://java.sun.com/>.
TELVENT. ITACA - Intelligent Traffic Adaptive Control Agent. [S.l.], 2008. Disponível
em: <http://www.telvent.com/products/traffic/Itaca_en.pdf>.
TRAFFICWARE LTD. Products. Jul 2008. Acessado em: 23/07/2008. Disponível em:
<http://www.trafficware.com/products.html>.
TRB (Ed.). Highway Capacity Manual 2000. [S.l.]: Transportation Research Board,
2000.
TRL SOFTWARE. TRANSYT. Ago 2009. Acessado em: 14/08/2009. Disponível em:
<http://www.trlsoftware.co.uk/>.
VIANA JR., G. F. Um Sistema de Informação Geográfico inteligente para escolha
de trajetos: uso do modelo de rede e da lógica fuzzy. Dissertação (Mestrado) —
CEFET-MG, Belo Horizonte-MG, 2004.
VIANA JR., G. F.; ALMEIDA, P. E. M.; MOURA, A. C. M. Um sistema informativo
geográfico inteligente para escolha de trajeto: uso do modelo de rede e da
lógica fuzzy. 2o. WTDIA, 2004, São Luiz, MA. Anais do 2o. Workshop de Teses e
Dissertações em Inteligência Artificial, p. 1–8, 2004.
VILLALOBOS, L. D. C. Metodologia para Otimizar o Cálculo de Planos para
Semáforos, considerando o Atraso e Poluição. Tese (Tese de Doutorado) —
Universidade Federal de Santa Catarina, Florianópolis-SC, Novembro 2001.
Disponível em: <http://teses.eps.ufsc.br/defesa/pdf/3822.pdf>.
VOGEL, A.; GOERICK, C.; SEELEN, W. von. Evolutionary algorithms
optimizing traffic signal operation. Proce. European Symposium on Intelligent Techniques (ESIT) 2000, p. 83–91, Sep 2000. Disponível em:
<http://www.erudit.de/erudit/events/esit2000/proceedings/AD-01-4-P.pdf>.
VON ZUBEN, F. J. Computação Evolutiva: Uma Abordagem Pragmática. Ago 2009. Acessado em: 10/08/2009. Disponível em:
<ftp://ftp.dca.fee.unicamp.br/pub/docs/vonzuben/tutorial/tutorialEC.pdf>.
Referências
117
VON ZUBEN, F. J. Engenharia Imunológica. Ago
2009. Acessado em: 10/08/2009. Disponível em:
<http://www.dca.fee.unicamp.br/ vonzuben/research/lnunes_dout/index.html>.
WIKIPEDIA. Traffic light. Ago 2009. Http://en.wikipedia.org/. Acessado em:
05/08/2009. Disponível em: <http://en.wikipedia.org/wiki/Traffic_light>.
WOLFRAM, S. Cellular automata. Los Alamos Science, v. 9, p. 2–21, 1983.
ZADEH, L. A. Fuzzy sets. Information and Control, v. 8, p. 338–353, 1965. Disponível
em: <http://www-bisc.cs.berkeley.edu/Zadeh-1965.pdf>.

- Modelagem Matemática e Computacional / CEFET-MG

Transcrição

Documentos relacionados

CRIAÇÃO DE UMA FERRAMENTA 3D PARA SIMULAÇÃO

1. História do PVsyst 2. Visão Geral do Software 3

Engenharia de Tráfego - departamento de transportes da ufpr

Criação de uma Ferramenta 3D para Simulação Microscópica de

Roteiro

SIG ENT - Ear Nose and Throat - RUTE 2010

Gestão e análise detalhada de tráfego para redes IP

a/0 b/0 c/0 d/1 e/1 1 0 0 0 0 1 1 1 1 0

Agenda de Atividades 2009 do SIG ENT

Simulação e Modelamento Comportamental de Sistemas