BRENO CARVALHO COSTA
PROGRAMAÇÃO SEMAFÓRICA DE TEMPO
FIXO EM MICRORREGIÕES UTILIZANDO
OTIMIZAÇÃO MULTIOBJETIVO E SIMULAÇÃO
MICROSCÓPICA
Belo Horizonte – MG
Maio de 2012
BRENO CARVALHO COSTA
PROGRAMAÇÃO SEMAFÓRICA DE TEMPO
FIXO EM MICRORREGIÕES UTILIZANDO
OTIMIZAÇÃO MULTIOBJETIVO E SIMULAÇÃO
MICROSCÓPICA
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 à obtenção do título de Mestre em
Modelagem Matemática e Computacional.
Orientador:
Prof. Dr. Paulo Eduardo Maciel de Almeida
Centro Federal de Educação Tecnológica de Minas Gerais
(CEFET-MG)
Co-orientador:
Prof. Dr. Eduardo Gontijo Carrano
Universidade Federal de Minas Gerais
(UFMG)
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
Maio de 2012
Ao meu avô Lauzinho, que me ensinou o alfabeto, os números
e me mostrou como ser um homem de caráter.
Aos meus pais, Rander e Valquíra, que, em suas sabedorias,
instigaram-me a “crescer na vida” e deram todo apoio para isso.
Agradecimentos
Agradeço sobretudo ao senhor Jesus, pela transformação da minha vida e pelas
bençãos derramadas;
À minha família, pelo apoio em todas as etapas da minha vida;
Aos meus irmãos, Matheus e Lucas, pela amizade incondicional;
À minha namorada Gisely, pelo amor, carinho e compreensão em todos os nossos
momentos difíceis;
Ao professor Paulo Almeida, pela sabedoria, confiança e conselhos;
Ao professor Eduardo Carrano, pelo auxílio em vários momentos desse trabalho;
Ao Evandro, pela amizade e pela contribuição no início do desenvolvimento;
Ao Saulo, caro amigo durante esse período, tanto nos momentos de estudo, quanto
nos vários momentos de risadas;
Ao Harley, Nilmar, Zé, Renan, pela amizade conquistada;
Aos amigos de Formiga, pelos poucos momentos de distração;
Aos colegas do MMC, pela companhia durante esse período;
Aos companheiros de trabalho do LSI;
Aos colegas do SIGA, Evandrino, Pedro, Thales, Ricardo, Felipe, Lucas, Renato;
Aos amigos e ex-professores do UNIFOR-MG, pelo incentivo e confiança;
Ao CEFET-MG, pela estrutura fornecida durante o curso;
À CAPES pelo apoio financeiro;
À empresa BHTRANS, pelo fornecimento dos dados para realização dos experimentos.
Aos demais, que, de algum modo, contribuíram comigo nessa jornada;
“Porque Dele e por Ele, e para Ele, são todas as coisas;
glória, pois, a Ele eternamente. Amém”
(Romanos 11:36)
“Talento é 1% inspiração e 99% transpiração”
(Thomas Edison)
Resumo
Atualmente grandes cidades lidam com sérios problemas no gerenciamento de tráfego, devido ao crescente número de veículos e pedestres. A Compania de Engenharia de Tráfego de São Paulo (CET-SP) criou um relatório em 2010, mostrando que a
velocidade média dos veículos caiu 33% na hora do rush entre 1997 e 2009. Com isso,
o uso de ferramentas de gerenciamento de tráfego é necessário para mitigar os efeitos
desse crescimento. Neste contexto, esse trabalho estuda o problema de programação
semafórica de tempo fixo em redes urbanas, que consiste em configurar parâmetros
operacionais dos semáforos ao longo do tempo, levando em conta medidas de desempenho. Para tanto, uma técnica de otimização multiobjetivo foi aplicada para gerar
tempos semafóricos em regiões específicas de uma grande área metropolitana. O
objetivo foi verificar o comportamento do algoritmo usando uma nova combinação de
funções objetivo, que ainda não tem sido encontrada na literatura: maximizar velocidade média dos veículos e minimizar variância da velocidade média deles. A primeira
função foi usada anteriormente em outros trabalhos e melhora o fluxo de veículos na
rede, enquanto que a segunda função é uma nova proposta para equilibrar velocidade
média nas vias. A combinação dessas funções é otimizada usando uma metodologia
que combina o método Nondominated Sorting Genetic Algorithm 2 (NSGA 2) utilizando conceitos de memória e operadores adaptativos e um simulador microscópico
GISSIM, acoplado ao sistema de informação geográfica OpenJUMP. Essa abordagem
foi validada por meio da realização de experimentos em uma região com dados atuais
de tráfego coletados em campo, para que os resultados fiquem próximos da realidade.
Os dados utilizados foram fornecidos pela BHTRANS (compania de engenharia de
tráfego de Belo Horizonte). Os resultados práticos obtidos foram comparados com os
planos semafóricos atuais da BHTRANS, uma implementação do algoritmo genético
mono-objetivo e uma implementação pura do NSGA2. As comparações mostraram
que essa proposta é eficiente em dois aspectos principais: é possível gerar planos
semafóricos melhores que os atuais e, além disso, é possível gerar um conjunto eficiente de planos semafóricos diferentes, cabendo ao engenheiro de tráfego escolher
o melhor plano para cenários particulares. Os resultados obtidos em experimentos
indicaram, de modo prático, que os dois objetivos foram simultaneamente alcançados:
aumentar a velocidade média dos veículos na área simulada e diminuir a diferença
das velocidades médias nas vias. Ademais, os impactos da otimização semafórica
para mitigar algumas complicações, tais como reduzir congestionamento de tráfego e
reduzir consumo de combustível, são claras a partir das simulações realizadas. Finalmente, verificou-se que a solução aqui proposta tem baixo custo de implementar em
ambientes urbanos usando equipamentos atualmente disponíveis, tornando-se confiável e viável a sua utilização.
PALAVRAS-CHAVE: Programação Semafórica, Otimização Multiobjetivo, Sistema de
Informação Geográfica, Simulação.
Abstract
Nowadays large cities deal with serious problems in traffic management, due to growing
number of vehicles and pedestrians. The Traffic Engineering Company of São Paulo
(CET-SP) published a report in 2010 showing that the average speed of vehicles decreased 33 percent in rush hour from 1997 to 2009. Therefore, use of traffic management
tools is needed to mitigate the growth effects. In this context, the present work addresses the fixed time traffic signal optimization problem in urban networks, that consists of
set time operational parameters of traffic signals along time, while taking into account
objective performance measures. To do so, we applied a multiobjective optimization
technique to generate traffic signal times in specific regions of a big metropolitan area.
Our goal was to check the algorithm behavior in traffic signal optimization using a new
combination of objective functions, not being found in literature so far: to maximize
vehicles average speed and to minimize their average speed variance. The first function was used previously in other works and improve vehicles flow in network, whereas,
the second function is a new proposal to balance average speed in the streets. The
combination of these functions is optimized using a methodology that combines Nondominated Sorting Genetic Algorithm 2 (NSGA-2) method, adaptive operators, memory
concepts, and microscopic simulator GISSIM running inside OpenJUMP GIS software.
This approach was validated through performing experiments in a region with actual
traffic data collected on the field, so that results are close to reality. We used data
provided by BHTRANS (traffic engineering company of Belo Horizonte, Brazil). The
obtained practical results were compared to BHTRANS current traffic signal plans,
to a genetic algorithm implementation using single objective function, and to a default NSGA 2 implementation. The comparison showed that our proposal is efficient
in two main aspects: it is possible to generate traffic signal plans better than current
ones, and also, it is possible to generate an efficient set of different traffic signal plans,
enabling the traffic engineer to choose the best plan for particular scenarios. The results obtained in experiments also indicated in a practical way that the two objectives
were simultaneously achieved: to increase average speed of vehicles in the simulated area and to decrease the difference of average speeds on the streets. Moreover,
the impacts of traffic signal optimization to mitigate some network problems, such as
reducing traffic congestion and reducing fuel consumption, are very clear from the performed simulations. Finally, we verified that the solution here proposed has low cost to
be implemented on urban environments using currently available equipment, making it
reliable and feasible to use.
KEYWORDS: Traffic Signal Optimization, Multiobjective Optimization, Geographic Information System, Simulation.
Lista de Figuras
1
Interseção com quatro movimentos. Adaptado de DENATRAN (1984) .
7
2
Diagrama de estágios. Adaptado de DENATRAN (1984) . . . . . . . . .
8
3
Estudo de movimentos x estágios. Adaptado de DENATRAN (1984) . .
8
4
Diagrama de tempos. Adaptado de DENATRAN (1984) . . . . . . . . .
9
5
Defasagem ao longo de uma via arterial. Extraído de CONTRAN (2012)
10
6
Exemplo de variação diária do volume de tráfego ao longo da semana.
Extraído de CONTRAN (2012) . . . . . . . . . . . . . . . . . . . . . . .
11
7
Comportamento do tráfego. Extraído de Oliveira e Almeida (2009) . . .
12
8
Estudo do comportamento do tráfego. Extraído de Oliveira e Almeida
(2009) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
12
Mapeamento de uma solução x (espaço de parâmetros) para o espaço
de objetivos Y feito pela função f (.) . . . . . . . . . . . . . . . . . . . .
35
10
Solução y1 domina y2 no espaço de objetivos Y
. . . . . . . . . . . . .
36
11
Fronteira Pareto-ótima no espaço de objetivos Y . . . . . . . . . . . . .
37
12
(a) Conjunto de pontos (b) Separação das fronteiras de dominância.
Adaptado de Deb (2008) . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
42
Cálculo do crowding distance. Pontos em negrito pertencem à mesma
fronteira. Extraído de Deb et al. (2002) . . . . . . . . . . . . . . . . . . .
43
14
Técnica aplicada ao problema de programação semafórica . . . . . . .
50
15
Diagrama de classes representando o plano semafórico de um conjunto
de interseções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
17
51
Cruzamento entre Rua dos Tupinambás e Rua dos Guaranis. Extraído
de Google Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
Cruzamento desenhado no OpenJUMP . . . . . . . . . . . . . . . . . .
54
18
Movimentos para o cruzamento . . . . . . . . . . . . . . . . . . . . . . .
54
19
Semáforos para o cruzamento (Fornecido pela BHTRANS) . . . . . . .
55
20
Tela do GISSIM-TL - Painel com a Área de Simulação . . . . . . . . . .
55
21
Tela do GISSIM-TL - Configurar Junção de Controle . . . . . . . . . . .
56
22
Tela do GISSIM-TL - Configurar Plano Semafórico por Grupo . . . . . .
57
23
Diagrama de tempos no intervalo de tempo (ID = 8) para o cruzamento
(Fornecido pela BHTRANS) . . . . . . . . . . . . . . . . . . . . . . . . .
57
24
Tela do GISSIM-TL - Configurar Ciclo . . . . . . . . . . . . . . . . . . .
58
25
Diagrama de objetos representando o plano semafórico do cruzamento
59
26
Exemplo de configuração do ciclo em uma interseção com oito semáforos 60
27
Representação da solução para o ciclo de três estágios . . . . . . . . .
61
28
Diagrama de classes do JFEMO . . . . . . . . . . . . . . . . . . . . . .
64
29
Fluxo do algoritmo MBVL-NSGA2
. . . . . . . . . . . . . . . . . . . . .
66
30
Diagrama de classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
31
Cruzamento em trecho de mão dupla. Adaptado de Google Maps . . .
73
32
Comparação dos desenhos do trecho de mão dupla . . . . . . . . . . .
74
33
Exemplo de trechos com movimentos permitidos e proibidos. Adaptado
de Google Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
34
Tela de configuração dos movimentos permitidos . . . . . . . . . . . . .
75
35
Exemplo de uma microrregião desenhada no OpenJUMP . . . . . . . .
76
36
Região de exemplo desenhada na interface gráfica de simulação . . . .
77
37
Zonas do modelo Lane Changing. Adaptado de Casas et al. (2010) . .
79
38
Lista dos próximos trechos a percorrer quando o veículo entra na rede .
80
39
Novo trecho selecionado pela matriz OD é adicionado à lista . . . . . .
81
40
Exemplo de cruzamento com semáforo no início de um trecho. Adap-
41
tado de Google Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
Semáforo configurado como ponto de controle semaforizado . . . . . .
82
42
Tela de simulação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
Exemplo de cálculo do hipervolume para um conjunto de soluções não
dominadas em um problema de minimização de f1 e f2 . . . . . . . . .
44
89
Via arterial ligando a Praça Sete e a Raul Soares. Adaptado de Google
Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
83
92
Via arterial ligando a Praça Sete e a Raul Soares desenhada no OpenJUMP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
46
Via arterial ligando a Praça Sete e a Raul Soares no GISSIM-TL . . . .
93
47
Resultado para Praça Sete - Raul Soares (Via Arterial) 7-8h . . . . . . .
94
48
Evolução das funções para Praça Sete - Raul Soares (Via Arterial) 7-8h
96
49
Resultado para Praça Sete - Raul Soares (Via Arterial) 17-18h . . . . .
97
50
Evolução das funções para Praça Sete - Raul Soares (Via Arterial) 17-18h 99
51
Boxplots dos indicadores de hipervolume da Praça Sete - Raul Soares
(Via Arterial) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
52
Distribuição bootstrap na Praça Sete - Raul Soares (Via Arterial) . . . . 101
53
Praça Raul Soares. Extraído de Google Maps . . . . . . . . . . . . . . . 102
54
Praça Raul Soares desenhada no OpenJUMP . . . . . . . . . . . . . . 102
55
Praça Raul Soares no simulador GISSIM . . . . . . . . . . . . . . . . . 103
56
Resultado para a região Praça Raul Soares (Rede) 7-8h . . . . . . . . . 105
57
Evolução das funções para Praça Raul Soares (Rede) 7-8h . . . . . . . 106
58
Resultado para a região Praça Raul Soares (Rede) 17-18h . . . . . . . 107
59
Evolução das funções para Praça Raul Soares (Rede) 17-18h
60
Boxplots dos indicadores de hipervolume da Praça Raul Soares (Rede)
61
Distribuição bootstrap na Praça Raul Soares (Rede) . . . . . . . . . . . 109
. . . . . 108
109
Lista de Tabelas
1
Divisão dos intervalos de tempo (Fornecido pela BHTRANS) . . . . . .
56
2
Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
3
Parâmetros dos algoritmos genéticos . . . . . . . . . . . . . . . . . . . .
87
4
Parâmetros do GISSIM-TL . . . . . . . . . . . . . . . . . . . . . . . . . .
88
5
Entrada de veículos da Praça Sete - Raul Soares (Via Arterial) . . . . .
94
6
Resultados para Praça Sete - Raul Soares (Via Arterial) 7-8h . . . . . .
95
7
Resultados para Praça Sete - Raul Soares (Via Arterial) 17-18h . . . . .
98
8
Valor-p encontrado para Praça Sete - Raul Soares (Via Arterial) . . . . 100
9
Entrada de veículos da Praça Raul Soares (Rede) . . . . . . . . . . . . 104
10
Resultados para a região Praça Raul Soares (Rede) 7-8h . . . . . . . . 104
11
Resultados para a região Praça Raul Soares (Rede) 17-18h . . . . . . . 107
12
Valor-p encontrado para Praça Raul Soares (Rede) . . . . . . . . . . . . 109
13
Resumo dos resultados de GA-FX1 e GA-FX2 . . . . . . . . . . . . . . 110
14
Resumo dos resultados de NSGA2 e MBVL-NSGA2 . . . . . . . . . . . 111
Lista de Abreviaturas e Siglas
AG Algoritmo Genético
IA Inteligência Artificial
ABNT Associação Brasileira de Normas Técnicas
BHTRANS Empresa de Transporte e Trânsito de Belo Horizonte S/A
CEFET-MG Centro Federal de Educação Tecnológica de Minas Gerais
CET-SP Companhia de Engenharia de Tráfego de São Paulo
CLONALG Algoritmo de Seleção CLONAL
DENATRAN Departamento Nacional de Trânsito
EMO Evolutionary Multiobjective Optimization
GEOPROC Geoprocessamento e Inteligência Computacional
GEPLO Gerência de Planejamento e Controle Operacional
GPSI Grupo de Pesquisa em Sistemas Inteligentes
HCM 2000 Highway Capacity Manual 2000
ITACA Intelligent Traffic Adaptive Control Agent
LSI Laboratório de Sistemas Inteligentes
MBVL-NSGA2 Memory-Based Variable-Length Encoding Non-Dominated Sorting Genetic Algorithm 2
MOGA Multiobjective Genetic Algorithm
NSGA Nondominated Sorting Genetic Algorithm
NPGA Niched-Pareto Genetic Algorithm
PAES Pareto Archived Evolution Strategy
PESA Pareto Envelope-based Selection Algorithm
SCATS Sydney Coordinated Adaptive Traffic System
SIG Sistema de Informação Geográfica
SCOOT Split, Cycle and Offset Optimization Technique
SPEA Strength Pareto Evolutionary Algorithm
VEGA Vector Evaluated Genetic Algorithm
UTM Universal Transverse Mercator
Sumário
1 INTRODUÇÃO
1
1.1 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.3 Organização da dissertação . . . . . . . . . . . . . . . . . . . . . . . . .
5
2 PROGRAMAÇÃO SEMAFÓRICA
6
2.1 Elementos Básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2.2 Programação Semafórica . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2.2.1 Volume de Tráfego . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.2.2 Fluxo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
2.2.2.1 Fluxo de Saturação . . . . . . . . . . . . . . . . . . . .
13
2.2.2.2 Tempo Perdido . . . . . . . . . . . . . . . . . . . . . . .
13
2.2.2.3 Taxa de Ocupação . . . . . . . . . . . . . . . . . . . . .
14
2.2.2.4 Grau de Saturação . . . . . . . . . . . . . . . . . . . . .
14
2.2.3 Ciclo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.2.3.1 Método do Grau de Saturação Máximo . . . . . . . . .
15
2.2.3.2 Método de Webster . . . . . . . . . . . . . . . . . . . .
16
2.2.4 Tempo de Verde . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.2.5 Defasagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.3 Controle e Operação . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.3.1 Tipos de Controle . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.3.2 Estratégias de Controle . . . . . . . . . . . . . . . . . . . . . . .
21
2.4 Medidas de Desempenho . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.4.1 Número de Paradas . . . . . . . . . . . . . . . . . . . . . . . . .
22
2.4.2 Fila Máxima . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
2.4.3 Atraso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.4.4 Tempo Médio de Viagem
. . . . . . . . . . . . . . . . . . . . . .
24
2.4.5 Velocidade Média . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
2.4.6 Número de Veículos Deixando a Rede de Tráfego
. . . . . . . .
25
2.5 Estado da Arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.5.1 Primeiras Abordagens . . . . . . . . . . . . . . . . . . . . . . . .
25
2.5.2 Algoritmos Genéticos . . . . . . . . . . . . . . . . . . . . . . . .
26
2.5.3 Algoritmos Evolucionários Multiobjetivo . . . . . . . . . . . . . .
30
2.5.4 Outros Métodos . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
2.5.5 Trabalhos do GEOPROC . . . . . . . . . . . . . . . . . . . . . .
33
3 OTIMIZAÇÃO MULTIOBJETIVO
3.1 Conjunto Pareto
34
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
3.1.1 Dominância . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
3.1.2 Solução Pareto-ótima . . . . . . . . . . . . . . . . . . . . . . . .
37
3.1.3 Fronteira Pareto-ótima . . . . . . . . . . . . . . . . . . . . . . . .
37
3.2 Algoritmos Relevantes . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
3.2.1 Funções agregadas . . . . . . . . . . . . . . . . . . . . . . . . .
38
3.2.2 Abordagens baseadas em população . . . . . . . . . . . . . . .
38
3.2.3 Abordagens baseadas em Pareto . . . . . . . . . . . . . . . . . .
39
3.3 Algoritmo NSGA 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
3.3.1 Procedimento Fast Nondominated Sort
. . . . . . . . . . . . . .
40
3.3.2 Preservação da Diversidade . . . . . . . . . . . . . . . . . . . . .
42
3.3.2.1 Estimativa de Densidade . . . . . . . . . . . . . . . . .
42
3.3.2.2 Operador Crowded-Comparison . . . . . . . . . . . . .
44
3.3.3 Esquema Geral . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
3.4 Memória e Vizinhança Adaptativa . . . . . . . . . . . . . . . . . . . . . .
45
3.4.1 Tabela Hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
3.4.2 Vizinhança Adaptativa . . . . . . . . . . . . . . . . . . . . . . . .
47
4 DESENVOLVIMENTO
49
4.1 Modelagem do Plano Semafórico . . . . . . . . . . . . . . . . . . . . . .
50
4.1.1 Escolher a Região . . . . . . . . . . . . . . . . . . . . . . . . . .
53
4.1.2 Desenhar no OpenJUMP . . . . . . . . . . . . . . . . . . . . . .
54
4.1.3 Configurar as Junções . . . . . . . . . . . . . . . . . . . . . . . .
55
4.1.4 Definir os Intervalos de Tempo . . . . . . . . . . . . . . . . . . .
56
4.1.5 Configurar os Ciclos por Intervalo de Tempo . . . . . . . . . . . .
57
4.1.6 Resultado da Modelagem . . . . . . . . . . . . . . . . . . . . . .
58
4.2 Algoritmo de Otimização Semafórica . . . . . . . . . . . . . . . . . . . .
60
4.2.1 Descrição do problema
. . . . . . . . . . . . . . . . . . . . . . .
60
4.2.1.1 Variáveis de decisão . . . . . . . . . . . . . . . . . . . .
60
4.2.1.2 Representação da solução . . . . . . . . . . . . . . . .
61
4.2.1.3 Funções de avaliação . . . . . . . . . . . . . . . . . . .
62
4.2.2 Framework de Otimização . . . . . . . . . . . . . . . . . . . . . .
63
4.2.3 Algoritmo MBVL-NSGA2 . . . . . . . . . . . . . . . . . . . . . . .
65
4.2.3.1 População Inicial . . . . . . . . . . . . . . . . . . . . . .
65
4.2.3.2 Memória . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
4.2.3.3 Avaliação de Soluções . . . . . . . . . . . . . . . . . . .
67
4.2.3.4 Operadores Genéticos . . . . . . . . . . . . . . . . . . .
67
4.2.3.5 Nova população . . . . . . . . . . . . . . . . . . . . . .
69
4.2.4 Diagrama de Classes . . . . . . . . . . . . . . . . . . . . . . . .
69
4.3 Simulador GISSIM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
4.3.1 Área de simulação . . . . . . . . . . . . . . . . . . . . . . . . . .
69
4.3.2 Interface gráfica . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
4.3.3 Máquina de simulação . . . . . . . . . . . . . . . . . . . . . . . .
71
4.3.4 Estatísticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
4.3.5 Modificações no simulador
. . . . . . . . . . . . . . . . . . . . .
72
4.3.5.1 Trechos de mão dupla . . . . . . . . . . . . . . . . . . .
72
4.3.5.2 Movimentos permitidos por trecho . . . . . . . . . . . .
74
4.3.5.3 Modelagem multifaixas . . . . . . . . . . . . . . . . . .
75
4.3.5.4 Mudança de faixas . . . . . . . . . . . . . . . . . . . . .
76
4.3.5.5 Conversões . . . . . . . . . . . . . . . . . . . . . . . . .
80
4.3.5.6 Pontos de controle . . . . . . . . . . . . . . . . . . . . .
81
4.3.5.7 Defasagem . . . . . . . . . . . . . . . . . . . . . . . . .
83
4.3.5.8 Interface gráfica de simulação . . . . . . . . . . . . . .
83
5 EXPERIMENTOS
85
5.1 Parâmetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
5.2 Metodologia de Comparação Estatística . . . . . . . . . . . . . . . . . .
88
5.2.1 Cálculo do Hipervolume . . . . . . . . . . . . . . . . . . . . . . .
88
5.2.2 Método Bootstrap . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
5.2.3 Teste T de Welch . . . . . . . . . . . . . . . . . . . . . . . . . . .
90
5.3 Praça Sete - Raul Soares (Via Arterial) . . . . . . . . . . . . . . . . . . .
91
5.3.1 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
5.3.1.1 7 às 8 horas
. . . . . . . . . . . . . . . . . . . . . . . .
94
5.3.1.2 17 às 18 horas . . . . . . . . . . . . . . . . . . . . . . .
97
5.3.2 Comparação Estatística . . . . . . . . . . . . . . . . . . . . . . .
99
5.4 Praça Raul Soares (Rede) . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.4.1 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.4.1.1 7 às 8 horas
. . . . . . . . . . . . . . . . . . . . . . . . 104
5.4.1.2 17 às 18 horas . . . . . . . . . . . . . . . . . . . . . . . 106
5.4.2 Comparação Estatística . . . . . . . . . . . . . . . . . . . . . . . 108
5.5 Análise Geral dos Resultados . . . . . . . . . . . . . . . . . . . . . . . . 110
6 CONCLUSÕES
114
6.1 Contribuições do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.2 Publicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.3 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
Referências
120
1
1
INTRODUÇÃO
Atualmente as grandes cidades lidam com sérios problemas no gerenciamento do
tráfego devido ao crescente número de veículos e pedestres. Um relatório criado pela
Companhia de Engenharia de Tráfego de São Paulo (CET-SP) (CET-SP, 2010) mostrou
que o fluxo de veículos da cidade de São Paulo aumentou 43,2% entre 1997 e 2009.
Naquele período, o aumento na população da cidade foi menor, representando cerca
de 8%. Além disso, o relatório mostrou que a cidade tem 61 veículos para cada 100
pessoas. O rodízio de veículos em São Paulo (estratégia para melhorar o tráfego)
perdeu totalmente seus efeitos, 13 anos depois de ser iniciado em 1997. Além disso,
a velocidade média dos veículos diminuiu 33% no horário de pico. Quando a estratégia
do rodízio se iniciou, o tráfego fluía em uma velocidade média de 17,5 Km/h, mas em
2009 o indicador caiu para 11,7 km/h.
O grande número de veículos nas vias é um dos principais agravantes para esse
problema. Segundo o relatório de Informações da Mobilidade Urbana de Belo Horizonte (BHTRANS, 2011), fornecido pela Empresa de Transporte e Trânsito de Belo
Horizonte (BHTRANS), é possível verificar o aumento da frota de veículos na cidade.
Entre 1999 e 2010, o número de automóveis licenciados, que era de 491.332, passou
a 937.819, ou seja, um aumento de 91%. Enquanto isso, o aumento do número de motocicletas foi superior, passando de 44.634 a 163.489, incríveis 266%. Considerando
a frota total, o aumento ficou em 103%. Além disso, nota-se que essa porcentagem
tem crescido a cada ano e, atualmente, o crescimento da frota está em 10% ao ano.
Mesmo assim, incentivos do governo brasileiro durante a crise de 2009 facilitaram
a compra de novos veículos e, segundo Downie (2008), o crescimento dos padrões
de vida em anos recentes tem facilitado significantemente o aumento destes números.
Com isso, perto de 1000 veículos chegam todos os dias às ruas do Brasil. Hoje em
dia, em meados de 2012, o governo brasileiro voltou a reduzir os impostos sobre a
venda de carros para aquecer a economia. O resultado disso, previsivelmente, são os
1 INTRODUÇÃO
2
problemas de congestionamento.
O problema de congestionamento traz a necessidade de gerenciamento e expansão das vias. Ademais, pessoas especializadas que cuidam do trânsito devem usar
ferramentas eficientes para melhorar o fluxo de veículos. Uma engenharia de tráfego
eficiente é essencial, sendo capaz de diminuir o impacto do crescimento incontrolável
das cidades. Para este fim, soluções práticas, rápidas e eficientes são necessárias
para o planejamento do tráfego, com o objetivo de assegurar o fluxo e segurança adequados. Neste contexto, algumas soluções têm sido estudadas para otimização de
tráfego e a programação semafórica é uma das mais importantes. Ela tem uma importância fundamental ao gerenciar os movimentos conflitantes nas junções, mas, além
disso, uma boa configuração semafórica pode otimizar o tráfego.
A programação semafórica tem sido abordada de maneiras diferentes na literatura.
Os primeiros estudos utilizavam métodos determinísticos para configurar os ciclos em
interseções isoladas (WEBSTER, 1958). Essa abordagem foi adotada em manuais semafóricos de todo o mundo (TRB, 1965) (SHEFFI; POWELL, 1983) (DENATRAN, 1984)
(TRB, 2000). Entretanto, a aplicação em uma rede de semáforos (situação predominante no mundo real) apresentava problemas. Com isso, esforços foram direcionados
aos estudos de programação semafórica em rede (ALLSOP; CHARLESWORTH, 1977).
Depois disso, o advento dos métodos computacionais trouxe novas possibilidades de
abordar o problema (SHEFFI; POWELL, 1983) (SAKA; ANANDALINGAM; GARBER, 1986).
Na década de 90, o sucesso da aplicação de algoritmos genéticos em problemas
de otimização fez com que, os algoritmos genéticos fossem utilizados para programar semáforos em interseções isoladas, vias arteriais ou redes de semáforos (FOY;
BENEKOHAL; GOLDBERG,
1992) (HADI; WALLACE, 1993) (ODA et al., 1996) (PARK, 1998)
(ROUPHAIL; PARK; SACKS, 2000) (MASTERTON; TOPIWALA, 2008) (SANCHEZ; GALAN; RUBIO,
2008) (TURKY; AHMAD; YUSOFF, 2009). Esses algoritmos obtiveram bons resul-
tados. Consequentemente, os algoritmos evolucionários multiobjetivo foram também
aplicados em interseções isoladas (SUN; BENEKOHAL; WALLER, 2003) (HU; GAO; YANG,
2010). No entanto, esses algoritmos têm sido negligenciados nesse campo de estudo,
sobretudo, na aplicação em redes de semáforos.
Nesta dissertação, estuda-se o problema de programação semafórica aplicado em
redes de semáforos, que, em suma, consiste em definir a configuração dos parâmetros
de operação de um conjunto de semáforos ao longo do tempo. Esses parâmetros
devem ser definidos cuidadosamente, pois a sua má configuração pode implicar em
1.1 Objetivos
3
geração de filas, atrasos, desrespeito por parte dos condutores, aumento da poluição,
redução da segurança, dentre outros problemas indesejáveis.
O problema é modelado aqui utilizando conceitos de otimização multiobjetivo e
propõe uma combinação de funções objetivo que, até então, não foi encontrada na
literatura. Essa combinação é constituída de duas funções: maximizar a velocidade
média dos veículos e minimizar a variância da velocidade média. A primeira função
já tinha sido usada na literatura anteriormente para aumentar o fluxo da rede, mas a
segunda função é uma nova proposta desse trabalho e tem, como objetivo, equilibrar
as velocidades dos veículos em todos os trechos da rede. Para otimizar esse conjunto
de funções, aplica-se o algoritmo Nondominated Sorting Genetic Algorithm 2 (NSGA
2) com conceitos de memória e vizinhança adaptativa. Para tanto, foi necessário estender o trabalho de Oliveira e Almeida (2010), que criaram o plugin GISSIM-TL para
realizar programação semafórica no SIG OpenJUMP. Por fim, experimentos foram realizados com dados reais da cidade de Belo Horizonte fornecidos pela BHTRANS e
uma comparação é feita entre os planos semafóricos atuais, um algoritmo genético
mono-objetivo e uma implementação do NSGA 2 puro.
1.1
Objetivos
O objetivo geral deste trabalho é realizar a programação semafórica por meio de
algoritmos evolucionários multiobjetivo, a fim de contribuir com o gerenciamento do
tráfego nas cidades. Sendo assim, os seguintes objetivos específicos são propostos:
• Estender a modelagem proposta por Oliveira e Almeida (2010), introduzindo a
avaliação simultânea de múltiplos objetivos;
• Implementar a técnica evolucionária multiobjetivo NSGA 2 aplicada ao problema
em questão;
• Adicionar conceitos sobre memória e vizinhança adaptativa à técnica implementada, baseado no trabalho de Carrano, Moreira e Takahashi (2011);
• Integrar a técnica desenvolvida ao plugin GISSIM-TL (acoplada ao OpenJUMP)
desenvolvido por Oliveira e Almeida (2010);
• Validar a modelagem e técnica com a execução de experimentos práticos em
microrregiões de interesse, com utilização de dados reais da cidade de Belo
1.2 Metodologia
4
Horizonte, MG.
1.2
Metodologia
Neste trabalho, pretende-se contribuir para a construção das seguintes hipóteses:
As técnicas de otimização evolucionária multiobjetivo produzem melhores
resultados do que técnicas de otimização mono-objetivo quando aplicadas à
programação semafórica.
A utilização de memória e vizinhança adaptativa em algoritmos evolucionários
multiobjetivo obtêm resultados eficientes quando aplicadas à programação
semafórica.
Os passos abaixo detalham a metodologia aplicada ao problema:
• Revisão da literatura: revisar a literatura sobre semáforos, programação semafórica, otimização multiobjetivo, técnicas evolucionárias multiobjetivo, algoritmo
NSGA 2, memória e vizinhança adaptativa. Além disso, buscar os principais trabalhos existentes atualmente sobre programação semafórica e otimização multiobjetivo, de modo que seja possível verificar as inovações nas pesquisas dessas
áreas;
• Modelagem do problema multiobjetivo: modelagem do problema de programação semafórica utilizando conceitos de otimização multiobjetivo. Neste contexto,
serão definidas as variáveis de decisão e funções de avaliação, visando obter o
melhor resultado;
• Implementação do algoritmo NSGA 2: utilizando o modelo criado, será implementado um algoritmo evolucionário multiobjetivo para realizar a programação
semafórica. Essa etapa consiste na implementação do algoritmo NSGA 2, definição de operadores e parâmetros. Finalmente, o algoritmo implementado será
integrado ao plugin GISSIM-TL (OLIVEIRA; ALMEIDA, 2010), para análise e avaliação dos resultados;
1.3 Organização da dissertação
5
• Desenho de microrregiões: essa etapa consiste, primeiramente, na definição
das microrregiões que serão utilizadas. Por conseguinte, é necessário desenhar essas regiões georreferenciadas no software OpenJUMP. As microrregiões
desenhadas serão utilizadas para realizar os experimentos práticos;
• Validação da proposta: os experimentos práticos realizados nas microrregiões
desenhadas são necessários para validar o modelo proposto para o problema,
bem como verificar a eficiência do algoritmo implementado. Os resultados dos
testes são comparados com correlatos na literatura e, por conseguinte, são analisados e discutidos. Finalmente, por meio dessa etapa, espera-se ser possível
validar as duas hipóteses propostas neste projeto.
1.3
Organização da dissertação
A dissertação está organizada como se segue. Os conceitos sobre programação semafórica são descritos no Capítulo 2, juntamente com o estado da arte. Os
conceitos sobre otimização multiobjetivo, juntamente com o algoritmo NSGA 2 são
abordados no Capítulo 3. No Capítulo 4, está detalhado o desenvolvimento da proposta, que, por sua vez, é validada no Capítulo 5, por meio de experimentos. Por fim,
as conclusões sobre o trabalho são apresentadas no Capítulo 6.
6
2
PROGRAMAÇÃO SEMAFÓRICA
Neste capítulo, são apresentados os conceitos sobre programação semafórica e
simulação microscópica aplicada à programação semafórica. Dentre as referências
utilizadas na engenharia de tráfego, de modo geral, têm-se o Manual de Semáforos
(DENATRAN, 1984), o Highway Capacity Manual 2000 - HCM 2000 (TRB, 2000) e o
Manual Brasileiro de Sinalização de Trânsito (CONTRAN, 2012).
O objetivo deste trabalho não é comparar os manuais, mas utilizá-los como embasamento para realizar a programação semafórica. Para tanto, o padrão definido no
Brasil pelo CONTRAN e DENATRAN será empregado, visando atender as necessidades e determinações das normas do país. Sendo assim, as próximas seções têm
como objetivo explicar conceitos sobre programação semafórica, a fim de fazer com
que o leitor compreenda o assunto. Esses conceitos são fundamentais para o entendimento do trabalho.
2.1
Elementos Básicos
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 indica o sentido. Traço e barra indicam movimento
interrompido. Movimentos convergentes são aqueles que possuem origens diferentes e mesmo destino, por outro lado, os movimentos divergentes têm mesma origem
e destinos diferentes. Um conjunto de múltiplos movimentos realizados simultaneamente é chamado de grupo de movimentos. A Figura 1 apresenta o esquema de um
cruzamento entre duas vias de mão única, com seus quatro movimentos permitidos.
Uma interseção pode conter movimentos conflitantes entre si. Isso se dá quando
dois movimentos se cruzam e, por isso, não podem ser realizados simultaneamente.
Para diminuir os riscos de acidentes entre veículos é necessário gerenciar esses con-
2.1 Elementos Básicos
7
Figura 1: Interseção com quatro movimentos. Adaptado de DENATRAN (1984)
flitos. Em vias de menor volume de tráfego, basta a utilização de placas “PARE” nas
vias transversais, indicando a contenção do fluxo naquele ponto. Entretanto, com o
aumento do volume de tráfego, atrasos podem ser gerados devido a espera dos motoristas. Para superar isso, criou-se um dispositivo chamado semáforo.
O semáforo é um dispositivo de controle do tráfego que alterna o direito de passagem entre motoristas e/ou pedestres a partir de indicações luminosas em interseções
de múltiplas vias. Ele é composto de luzes que são dispostas ao lado das vias ou
suspensas sobre elas. O objetivo principal do semáforo veicular é autorizar/proibir o
movimento de veículos de uma corrente de tráfego. Para tanto, utiliza-se as cores:
verde/vermelho, respectivamente. Para evitar uma interrupção brusca de movimento,
utiliza-se um tempo de atenção (amarelo), indicando ao motorista sobre a proximidade
da mudança para o vermelho.
A sequência de indicação de cores de um semáforo é verde, amarelo, vermelho
e verde novamente. Cada uma dessas indicações possui um intervalo de tempo, em
segundos, cujo objetivo é limitar o tempo em que cada grupo de movimentos será
realizado. Essa sequência aplicada a uma ou mais correntes de tráfego (grupo de
movimentos) é denominada fase. Portanto, conclui-se que o tempo total de uma fase
é a soma dos tempos de verde, amarelo e vermelho. O tempo total é igual para todas
as fases e é denominado ciclo, pois é usado repetidamente para gerar uma sequência
de sinalização.
O intervalo de tempo em que um ou mais grupos de movimentos recebem o direito
de passagem é denominado estágio. O estágio compreende o tempo de verde e o
tempo de atenção que o segue, também chamado de tempo entreverdes. O tempo
de entreverdes é o intervalo de tempo compreendido entre o fim do verde de uma fase,
2.1 Elementos Básicos
8
que está perdendo o direito de passagem, e o início de outra, que o está ganhando.
O diagrama de estágios é a representação gráfica da alocação dos movimentos
que podem ser realizados em cada estágio do ciclo. A Figura 2 mostra um exemplo
de diagrama de estágios para os movimentos apresentados na Figura 1.
Figura 2: Diagrama de estágios. Adaptado de DENATRAN (1984)
O estudo de movimentos x estágios relaciona os movimentos permitidos para cada
estágio e, a partir disso, identifica quantos grupos focais são necessários para operar
o cruzamento. Um grupo focal é um conjunto de semáforos que controla um determinado grupo de movimentos. Uma tabela de movimentos referente à interseção
apresentada anteriormente é dada na Figura 3.
Figura 3: Estudo de movimentos x estágios. Adaptado de DENATRAN (1984)
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 Figura 4 ilustra um diagrama de tempos da interseção
apresentada anteriormente.
A interseção utilizada como exemplo possui quatro movimentos, sendo os movimentos 1 e 2 conflitantes com os movimentos 3 e 4. Portanto, os movimentos são
2.1 Elementos Básicos
9
Figura 4: Diagrama de tempos. Adaptado de DENATRAN (1984)
dispostos em dois grupos. O primeiro representa a fase 1 e o segundo representa a
fase 2, controladas pelos grupos focais G1 e G2 , respectivamente. Cada uma das fases
é divida em dois estágios: o estágio 1 possui dimensão de 30 segundos e um período
de entreverdes I1 de 3 segundos e o estágio 2 possui dimensão de 24 segundos e um
período de entreverdes I2 de 3 segundos. Por fim, nota-se que a soma dos tempos
de estágios corresponde ao tempo total das fases, que corresponde ao tempo de ciclo
dessa interseção. Esses parâmetros devem ser configurados para cada interseção da
rede.
Quando a programação de múltiplos semáforos é feita simultaneamente, em contraponto à configuração de um semáforo isolado, a sincronização entre interseções
deve ser definida. Considerando-se uma corrente de tráfego que passa por duas interseções semaforizadas pertencentes à mesma rede, denomina-se defasagem o intervalo de tempo decorrido entre o início do verde que essa corrente recebe nas duas
interseções. Com esse atributo, é possível fazer com que uma fila de veículos siga
durante um período de tempo em vários semáforos abertos seguidamente. A Figura
5 apresenta diagramas espaço-tempo, que ilustram a defasagem entre sinalizações
semafóricas ao longo de uma avenida, tendo como referência o início do verde da
interseção mais à esquerda.
A programação semafórica consiste na definição dos parâmetros de operação
de um ou mais semáforos ao longo do tempo. Esses parâmetros devem ser definidos
cuidadosamente, pois sua má configuração pode implicar em geração de filas, atrasos,
desrespeito por parte dos condutores, aumento da poluição, redução da segurança,
dentre outros problemas indesejáveis.
2.2 Programação Semafórica
10
Figura 5: Defasagem ao longo de uma via arterial. Extraído de CONTRAN (2012)
2.2
Programação Semafórica
Segundo o DENATRAN (1984), regular um semáforo significa determinar o tempo
de ciclo ótimo da interseção, calcular os tempos de verde necessários para cada fase
em função do ciclo adotado e calcular as defasagens entre os semáforos, se necessário. Portanto, para regular semáforos deve-se ter um plano semafórico que configura o
tráfego segundo um critério específico. O plano semafórico deve conter as seguintes
configurações:
• tempo de ciclo;
• número de fases e, consequentemente, os grupos focais que as controlam;
• número, sequência e dimensão dos estágios para cada fase;
• sincronização com outras interseções (defasagens).
Nesta seção serão abordados os principais elementos envolvidos na programação
semafórica, seus conceitos e modos de determinação.
2.2 Programação Semafórica
2.2.1
11
Volume de Tráfego
Segundo CONTRAN (2012), o volume de tráfego é o número de veículos que
passa por uma determinada via em um determinado período de tempo. Esse volume
é calculado por meio de contagem, seja visual ou por aparelhos da engenharia de
tráfego. O volume de tráfego varia ao longo do tempo, sendo em função da hora, do
dia ou do mês em que o movimento é observado. A Figura 6 ilustra a variação diária
do volume de tráfego ao longo da semana.
Figura 6: Exemplo de variação diária do volume de tráfego ao longo da semana. Extraído de CONTRAN (2012)
Na figura, é possível identificar os diferentes comportamentos do tráfego, definindo
alguns aspectos importantes, como os horários em que os semáforos podem ser desligados (amarelo intermitente), os horários de pico, etc. Na programação semafórica,
é importante analisar tais variações, especialmente ao longo do dia e da semana, já
que por meio dessa análise é possível estabelecer diferentes planos semafóricos em
diferentes intervalos de tempo.
2.2 Programação Semafórica
2.2.2
12
Fluxo
O fluxo de um movimento é o número de veículos projetado para o período de
uma hora a partir dos volumes de tráfego medidos em uma via. Segundo DENATRAN
(1984), o comportamento de desmanche de fila pode ser observado na Figura 7.
Figura 7: Comportamento do tráfego. Extraído de Oliveira e Almeida (2009)
Observa-se que, no início do período de verde, os veículos levam algum tempo
para começar seu deslocamento e acelerar até sua velocidade normal de viagem, o
que indica um atraso inicial. Entretanto, depois de alguns segundos, a fila de veículos
descarrega a uma taxa constante, até que o semáforo indique o estado de atenção em
que os veículos iniciam a desaceleração. Sendo assim, o tempo de verde oferecido
não é totalmente utilizado. O estudo desse comportamento está na Figura 8.
Figura 8: Estudo do comportamento do tráfego. Extraído de Oliveira e Almeida (2009)
2.2 Programação Semafórica
13
Na figura, observa-se alguns conceitos importantes para o cálculo da programação
semafórica, como o fluxo de saturação, tempo perdido do ciclo, tempo de verde efetivo.
2.2.2.1
Fluxo de Saturação
Segundo DENATRAN (1984), o fluxo de saturação é aquele 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 (veiculos/htv). 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 (S) pode ser
estimado a partir da Equação (2.1),
S = 525L
(2.1)
onde:
L é a largura da aproximação (metros).
2.2.2.2
Tempo Perdido
O DENATRAN (1984) apresenta a decomposição dos tempos em que o movimento
é autorizado 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, devido às reações dos motoristas
no início e no fim do tempo de verde. O tempo perdido total (Tp ) no cruzamento
durante um ciclo é igual à soma dos tempos perdidos de cada estágio, dado pela
Equação (2.2),
n
X
Tp = tep +
(tpini + tpf ni )
i=1
onde:
tep é o tempo de estágio exclusivo para pedestres (segundos);
n é o número de estágios;
(2.2)
2.2 Programação Semafórica
14
tpini é o tempo perdido no início do estágio i (segundos); e
tpf ni é o tempo perdido no final do estágio i (segundos).
Quando não é possível determinar o tempo perdido de cada estágio, um valor
aproximado para o tempo perdido total pode ser adotado como numericamente igual
à soma dos tempos amarelos dos estágios envolvidos.
2.2.2.3
Taxa de Ocupação
Segundo CONTRAN (2012), a taxa de ocupação (y) é a relação entre o fluxo e
o respectivo fluxo de saturação de um determinado grupo de movimentos, calculada
pela Equação (2.3),
y=
F
S
(2.3)
onde:
F é o fluxo do grupo de movimentos (veículos/hora); e
S é o fluxo de saturação do grupo de movimentos (veículos/hora).
2.2.2.4
Grau de Saturação
Segundo CONTRAN (2012), o grau de saturação é obtido pela relação entre o
volume do grupo de movimentos e a capacidade de atendimento desse volume no
período de tempo considerado. Sendo assim, um grau de saturação (x) indica se um
grupo de movimentos está próximo da saturação, dado pela Equação (2.4),
x=
V
cap
onde:
V é o volume do grupo de movimentos (veículos/hora); e
cap é a capacidade (veículos/hora).
(2.4)
2.2 Programação Semafórica
2.2.3
15
Ciclo
O cálculo dos tempos de ciclo são feitos por dois métodos principais: Método do
grau de saturação máximo e Método de Webster. Como valores altos para o tempo
de ciclo implicam em tempos de espera muito elevados, nas situações comuns de
controle esse valor não deve superar 120 segundos. Em situações excepcionais de
tráfego e/ou de geometria da interseção, pode ser necessário adotar tempos de ciclo
maiores. Nesses casos, deve ser dada especial atenção ao tratamento para a travessia dos pedestres no local, adotando-se medidas como implantação de travessia em
etapas, travessia em desnível, dentre outras soluções possíveis.
2.2.3.1
Método do Grau de Saturação Máximo
Este método é baseado no grau de saturação máximo definido para cada grupo
de movimentos. O método inicia pelo cálculo da fração de verde necessária para o
estágio i (pi ), por meio da Equação (2.5),
pi =
yi
,
xmi
(2.5)
onde:
yi é a taxa de ocupação do grupo de movimentos do estágio i (veículos/hora); e
xmi é o grau de saturação máximo definido para o grupo de movimentos do estágio i (veículos/hora).
A partir do cálculo da fração de verde para cada estágio, o tempo de ciclo (tc ) é
calculado em segundos, por meio da Equação (2.6),
tc =
1−
T
Ppn
onde:
Tp é o tempo perdido total (segundos); e
n é o número de estágios.
i=1
pi
,
(2.6)
2.2 Programação Semafórica
16
No caso geral em que se deseja adotar o mesmo grau de saturação xm para os
grupos de movimentos críticos de todos os estágios, a determinação do tempo de ciclo
é feita por meio da Equação (2.7), que é um caso geral da Equação (2.6),
tc =
xm · Tp
P
.
xm − ni=1 yi
(2.7)
Geralmente, adotam-se valores de grau de saturação compreendidos entre 0,75 e
0,90. Valores superiores a 0,90 podem conduzir a uma reserva de capacidade insuficiente para absorver tanto a flutuação aleatória do trânsito como a redução ocasional do
fluxo de saturação devido à ocorrência de incidentes. Por outro lado, valores inferiores
a 0,75 podem conduzir a tempos de ciclo injustificadamente elevados.
2.2.3.2
Método de Webster
De modo resumido, este método calcula o tempo de ciclo ótimo, de modo que o
tempo de espera veicular seja mínimo. O tempo de ciclo ótimo (tco ) é calculado em
segundos, por meio da Equação (2.8),
tco =
1, 5 · Tp + 5
P
,
1 − ni=1 yi
(2.8)
onde:
Tp é o tempo total perdido (segundos);
yi é a taxa de ocupação do grupo de movimentos crítico do estágio i; e
n é o número de estágios.
De acordo com Webster, tempos de ciclo na faixa de 0,75 a 1,5 do tempo de
ciclo ótimo produzem atrasos médios por veículos no máximo 20% superiores ao valor
do atraso obtido com o ciclo ótimo. O método de cálculo de ciclo ótimo apresenta
restrições, dentre as quais o próprio Webster 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 é
2.2 Programação Semafórica
17
apropriada e um método mais complexo é necessário para se obter
um tempo de ciclo adequado (WEBSTER, 1958).
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.
2.2.4
Tempo de Verde
Segundo CONTRAN (2012), o tempo de verde é classificado em dois tipos: efetivo
e real. Denomina-se tempo de verde efetivo de um estágio ao tempo de verde de um
ciclo que seria efetivamente utilizado pelo fluxo do grupo de movimentos, se este fosse
descarregado com valor igual ao fluxo de saturação.
Quando o ciclo for determinado pelo Método do Grau de Saturação Máximo, o
tempo de verde efetivo do estágio i (tvei ) é calculado pela Equação (2.9),
tvei = pi × tc ,
(2.9)
onde:
pi é a fração de verde requerida para o estágio i; e
tc é o tempo de ciclo (segundos).
Quando o ciclo for determinado pelo Método de Webster, o tempo de verde efetivo
do estágio i (tvei ) é calculado pela Equação (2.10),
yi
tvei = (tc − Tp ) × Pn
i=1
yi
,
onde:
tc é o tempo de ciclo (segundos);
Tp é o tempo perdido total (segundos);
yi é a taxa de ocupação do grupo de movimentos do estágio i; e
(2.10)
2.2 Programação Semafórica
18
n é o número de estágios.
Denomina-se tempo de verde real de um estágio a duração do período em que o
respectivo grupo focal permanece em verde, durante um ciclo. O tempo de verde real
(tvr ) é calculado pela relação com o tempo de verde efetivo, pela Equação (2.11),
tvr = tve − tent + tpin + tpf n ,
(2.11)
onde:
tve é o tempo de verde efetivo (segundos);
tent é o tempo de entreverdes (segundos);
tpin é o tempo perdido no início (segundos); e
tpf n é o tempo perdido no final (segundos).
2.2.5
Defasagem
Quando a maior parte do tráfego é feita em trechos sem desnível, e o fluxo em
superfícies com desnível (rampas) não é maior que os volumes normais de conversão
nas interseções, a defasagem padrão deve ser usada. Esta defasagem padrão (θij ) é
igual ao tempo de viagem da linha de parada da interseção de origem (i) à interseção
de destino (j) na velocidade média do tráfego, calculada pela Equação (2.12),
θij =
L
,
S
(2.12)
onde:
L é o tamanho da ligação (i − j) da linha de parada da interseção de origem e a
linha de parada da interseção de destino (metros); e
S é a velocidade média de corrida (metros/segundo).
Normalmente, entretanto, movimentos com desníveis (rampas) são suficientes
2.2 Programação Semafórica
19
para criar filas na ligação entre as interseções. Nesses casos, a defasagem ideal
deveria ser baseada na desobstrução da fila na interseção de destino, calculada pela
Equação (2.13),
θij =
L (1 − P ) · v · C
−
,
S
s
(2.13)
onde:
P é a proporção de veículos chegando no tempo verde;
v é a taxa do fluxo de chegada na interseção de destino (veículos/hora);
C é o tamanho do ciclo (segundos);
s é a taxa do fluxo de saturação na interseção de destino (veículos/hora).
Uma terceira opção para otimização de defasagens está disponível. Esse critério
é baseado em minimizar a demanda e está relacionada ao fluxo de saturação máximo
do trecho entre as interseções. Para minimizar a demanda, a defasagem deveria ser
maior ou igual ao resultado da Equação (2.14),
θij =
L 3600 · N · L
−
,
S
s·l
(2.14)
onde:
N é o número de faixas no trecho de ligação i − j;
l é o tamanho de armazenamento da fila por veículo (metros).
Geralmente, a seleção de uma defasagem deve considerar muitos fatores, incluindo o fluxo, o padrão de tráfego e o grau de saturação do semáforo da interseção
de destino. Entretanto, para melhorar a eficiência da transferência durante condições
de pico, a defasagem deveria ser maior ou igual ao maior valor produzido pelas equações (2.13) e (2.14).
2.3 Controle e Operação
2.3
20
Controle e Operação
O controle de tráfego em uma interseção (ou grupo de interseções) por meio da
sinalização semafórica pode ser realizado de acordo com diferentes estratégias e pode
ser implementado de diferentes modos. Os tipos e estratégias de controle, assim como
os modos de operação deles são descritos nesta seção, de acordo com o CONTRAN
(2012).
2.3.1
Tipos de Controle
Basicamente, existem dois tipos de controle semafórico: tempo fixo e atuado. Esses dois tipos definem como a programação semafórica é realizada e como as variações de tráfego causam impacto para atribuição de planos semafóricos.
O controle de tempo fixo calcula os planos semafóricos baseado nos intervalos de
tempo previamente definidos. Para obter esses intervalos, é necessário dividir o dia
em períodos de tempo, de acordo com as demandas de fluxo nas vias. Isso deve ser
feito para todos os dias da semana. Os intervalos representam as variações de fluxo,
obtidos por contagens volumétricas e outros levantamentos de campo. Sendo assim,
a partir do histórico de fluxo, cria-se os intervalos de tempo e, por fim, define-se os
planos semafóricos, calculando os tempos manualmente ou utilizando algum método
computacional.
O controle atuado é, em geral, empregado em cruzamentos de vias de grande
fluxo (vias principais) com vias de baixo fluxo de tráfego (vias secundárias). Esse tipo
de controle decorre do monitoramento da demanda de tráfego na interseção, mediante
a implantação de detectores de tráfego em todas as suas aproximações, permitindo
alterações nos tempos dos estágios. O princípio básico do funcionamento em modo
atuado é o da determinação do tempo de verde associado a cada estágio de sinalização, variando entre um valor mínimo e um valor máximo previamente estabelecidos.
Esse tipo de controle permite o ajuste em tempo real dos valores de alguns dos parâmetros de programação.
2.4 Medidas de Desempenho
2.3.2
21
Estratégias de Controle
Após definir o controle semafórico, o projetista deve decidir entre duas estratégias
básicas de controle: controle isolado ou controle em rede.
No controle semafórico isolado, cada interseção é controlada independentemente
das demais, ou seja, não ocorre nenhum tipo de coordenação semafórica. Nesse
caso, a definição da programação semafórica leva em conta apenas a demanda (histórica ou atual) do tráfego em todas as aproximações. Essa estratégia pode comprometer seriamente o desempenho da circulação do tráfego em situações cujas interseções
controladas por sinalização semafórica estiverem muito próximas entre si.
O controle em rede pode visar o aumento do desempenho da circulação do tráfego
ao longo de uma rede aberta ou de uma rede fechada. O controle em rede aberta visa
privilegiar a circulação do tráfego em uma via (ou em um percurso pré-estabelecido)
e, por isso, é comumente referido como controle em corredor. O controle em rede fechada, que visa melhorar o desempenho geral do tráfego em uma determinada região,
é denominado controle em área. A estratégia de controle em rede permite a programação da sinalização semafórica visando não somente o desempenho do tráfego em
cada interseção mas, sobretudo, o seu desempenho global ao longo do conjunto de
cruzamentos. Esse desempenho é avaliado com base em critérios definidos pelo órgão gestor do trânsito, em função do propósito do controle.
2.4
Medidas de Desempenho
Após uma implantação de planos semafóricos (programação semafórica) ser efetuada, é necessário fazer constantes avaliações, sejam em interseções isoladas ou
em rede, para verificar se o desempenho da operação de tráfego é suficientemente
bom. A avaliação deve ser feita logo após a implantação, mas continua a ser necessária a posteriori, pois o trânsito possui caráter dinâmico. Com isso, novas configurações
podem ser necessárias, caso algum problema seja detectado.
Existem várias medidas de desempenho que podem ser empregadas nesta avaliação, dentre as quais as mais utilizadas são fila máxima, velocidade média, número de
paradas, atraso, consumo de combustível, emissão de poluentes e custo monetário.
Essas medidas podem ser determinadas usando simulações de trânsito por meio de
programas de computador, ou ainda, podem ser obtidas diretamente por meio de pes-
2.4 Medidas de Desempenho
22
quisas em campo. Além disso, a partir de algumas hipóteses simplificadoras, algumas
das medidas de desempenho mais empregadas, como o atraso total e a fila máxima
podem ser estimadas de modo analítico por expressões matemáticas.
Nas próximas subseções, são discutidas algumas medidas de desempenho que
podem ser utilizadas.
2.4.1
Número de Paradas
O número de paradas é um dos principais indicadores de qualidade da operação
do trânsito, podendo ser caracterizado pelo número total de paradas, número médio
de paradas por veículo, ou porcentagem de veículos que param devido à sinalização
semafórica.
A programação semafórica deve visar a minimização do número de paradas que,
além de gerar desconforto ao usuário, aumenta o consumo de combustível e a emissão de determinados poluentes. O número de veículos que sofrem parada por ciclo
(np ), no caso de operação não saturada e fluxos de chegada e partida constantes,
pode ser calculado pela Equação (2.15),
np =
F · S tc − tve
·
,
S−F
3600
(2.15)
onde:
F é o fluxo (veículos/hora);
S é o fluxo de saturação (veículos/hora);
tc é o tempo de ciclo (segundos); e
tve é o tempo de verde efetivo (segundos).
2.4.2
Fila Máxima
Define-se fila, em uma rede de tráfego, como o número total de veículos aguardando em um trecho para transpor uma interseção semaforizada. Veículos aproximandose devagar do final de uma fila geralmente também são considerados como integrantes da mesma.
2.4 Medidas de Desempenho
23
O indicador “fila máxima” é um dos mais utilizados devido à facilidade com que
pode ser observado diretamente em campo e ao fato de que reflete adequadamente
os outros indicadores. A obtenção em campo do indicador “fila máxima” é feita pela
observação, ao longo de vários ciclos, do número máximo de veículos na fila por ciclo.
O valor do indicador é calculado como a média das filas máximas observadas em
campo.
2.4.3
Atraso
O indicador “atraso” visa medir a espera causada aos veículos pela sinalização
semafórica. Esse atributo representa a diferença entre o tempo gasto por um veículo
para percorrer um determinado trecho sob o controle semafórico e o tempo que gastaria se percorresse o mesmo trecho em regime de fluxo ininterrupto, na velocidade
desejada.
Nas situações de trânsito livre, em que todos os veículos conseguem passar no primeiro período de verde, o atraso é composto pelas parcelas atraso uniforme e atraso
aleatório. À medida que o trânsito vai ficando saturado, surge também uma terceira
parcela que é o atraso por sobredemanda. Quando a operação atinge o congestionamento total, o atraso aleatório desaparece, permanecendo os outros dois.
O valor do atraso uniforme médio de um veículo (au ), dado em segundos, pode ser
determinado pela Equação (2.16),
tc (1 − p)2
au =
,
2(1 − px)
(2.16)
onde:
tc é o tempo de ciclo (segundos);
p é a fração de verde (relação entre o tempo de verde efetivo e o tempo de ciclo);
e
x é o grau de saturação.
2.4 Medidas de Desempenho
2.4.4
24
Tempo Médio de Viagem
O tempo médio de viagem é uma medida utilizada para calcular a média gasta
pelos veículos para percorrer os trajetos na rede, ou seja, mede-se qual o tempo de
percurso para cada veículo (do ponto de entrada ao ponto de saída da rede), depois
calcula-se o tempo médio de viagem dos veículos na rede (tmv) em segundos, pela
Equação (2.17),
n
X
tmv =
tvi
i=1
n
,
(2.17)
onde:
tvi é o tempo de viagem do veículo i (segundos); e
n é o número de veículos.
2.4.5
Velocidade Média
A velocidade média é uma medida que pode ser obtida a partir de simuladores
de trânsito. Primeiramente, deve-se medir a velocidade média por veículo, ou seja,
mede-se a distância percorrida por veículo desde a entrada dele na rede até sua
saída. Depois o valor da distância é dividido pelo tempo gasto no trajeto e, com isso,
tem-se a medida de velocidade média para cada veículo. Logo depois, deve-se obter
a velocidade média dos veículos na rede (vm) em metros/segundo. Esse cálculo é
expresso na Equação (2.18),
n
X
vm =
vmi
i=1
n
,
onde:
vmi é a velocidade média do veículo i (metros/segundo); e
n é o número de veículos.
(2.18)
2.5 Estado da Arte
2.4.6
25
Número de Veículos Deixando a Rede de Tráfego
Essa medida é utilizada para aproximar a “vazão” da rede de tráfego como um
todo, ou seja, quanto maior o número de veículos saindo da rede, melhor será o fluxo
naquela rede, se comparado com outra de configuração igual para o volume. Para
medi-lo basta obter o valor absoluto do número de veículos que deixaram a rede durante a simulação ou durante uma medida de tempo.
2.5
Estado da Arte
Diversos trabalhos sobre programação semafórica podem ser encontrados na literatura. Dentre esses, alguns podem ser destacados por sua relevância e modo com
que o problema foi abordado.
2.5.1
Primeiras Abordagens
O método proposto por Webster (1958) utilizou métodos determinísticos (apresentados na Seção 2.2.3.2) para fazer o cálculo de ciclos ótimos em interseções isoladas
de tempo fixo. Desde então, foi referenciado em inúmeros trabalhos relacionados, tais
como Sheffi e Powell (1983), DENATRAN (1984), TRB (2000), Kesur (2009), Guberinic, Senborn e Lazic (2008), Cervantes (2009), CONTRAN (2012). Embora o seu
sucesso tenha sido muito grande, este método tem alguns problemas. Um dos problemas é o ajuste de muitas interseções, que pode produzir resultados insatisfatórios,
afetando o tráfego e a segurança dos motoristas. Além disso, problemas foram observados quando existe variação no fluxo de rotas de tráfego durante o dia. Mesmo com
os problemas, o Método de Webster proporcionou uma grande contribuição para as
áreas operacional e de pesquisa.
Robertson (1969) desenvolveu um programa chamado TRANSYT que otimiza a
alocação de tempos de verde para estágios em cada interseção, o tempo de início
do ciclo em cada interseção (defasagem) e o tempo de ciclo, por meio do método
de subida da montanha (hill-climbing). O TRANSYT leva em conta a necessidade de
coordenação dos semáforos. A função objetivo é uma combinação linear de atraso e
número de paradas.
Allsop e Charlesworth (1977) combinaram técnicas existentes para calcular os
2.5 Estado da Arte
26
tempos semafóricos, minimizando o tempo total de viagem. Para uma rede e movimentos de origem-destino dados, este trabalho descreveu um caso no qual duas
soluções distintas foram encontradas para uma rede realística pequena. Essas duas
soluções possuíam padrões diferentes de tráfego, o que permitiu a escolha entre as
mesmas observando propósitos distintos, tais como aumento da segurança ou diminuição do atraso.
Sheffi e Powell (1983) estudaram o problema de encontrar os tempos ótimos do
plano semafórico, de acordo com algum critério de equilíbrio do usuário. Para os autores, o problema era encontrar um conjunto de tempos para os verdes de todas as
interseções, em que o tempo de viagem fosse minimizado. Para isso, os autores sugeriram um algoritmo de busca simplificado baseado no gradiente, que poderia ser
aplicado somente em pequenas redes. Logo depois, os autores apresentaram uma
heurística aplicável a redes maiores. Nessa heurística, uma abordagem iterativa bem
simples foi proposta para a otimização de semáforos localmente (utilizando o método
de Webster). Com isso, os autores conseguiram obter melhores padrões de fluxo nos
exemplos de testes, encontrando valores mínimos, mas aquele algoritmo não conseguiu garantir os mínimos globais para o problema.
Saka, Anandalingam e Garber (1986) apresentaram duas técnicas de otimização
semafórica estocásticas para interseções isoladas. O objetivo era determinar o ciclo
ótimo e os tempos de verde. Para isso, propuseram a minimização do atraso médio
total na interseção em um período de observação, utilizando programação dinâmica e
simulação. Nos testes, os autores utilizaram uma interseção semaforizada de quatro
fases e os resultados empíricos mostraram padrões de tráfego regulares. Ademais, os
autores ressaltaram a importância da simulação, concluindo que não existe método
que possa ser aplicado a todas as condições de tráfego (não saturadas, saturadas e
sobressaturadas), mas a simulação tem essa característica.
2.5.2
Algoritmos Genéticos
Foy, Benekohal e Goldberg (1992) foram os primeiros a aplicar algoritmos genéticos ao problema de temporização semafórica. A codificação do problema incluiu tamanho do ciclo, tempos de verde e defasagens. O cálculo dos atrasos foi feito usando
um modelo de simulação microscópica de tráfego. Uma rede hipotética de quatro semáforos sobre o controle de duas fases teve o atraso minimizado usando um algoritmo
genético simples (AG).
2.5 Estado da Arte
27
Hadi e Wallace (1993) envolveram quatro elementos no projeto: sequência de fases, tamanho do ciclo, tempos de verde e defasagem. O objetivo proposto foi aplicar
o AG usando essas variáveis para aumentar o desempenho dos algoritmos existentes
até então, como por exemplo no programa TRANSYT. Para isso, os autores fizeram
duas propostas, na primeira os autores utilizaram o AG junto ao TRANSYT que são
executados concorrentemente para conseguir uma solução ótima. Na segunda proposta, o AG é usado para otimizar os atributos e depois inserido no TRANSYT para
ajustar a temporização semafórica restante. Os resultados mostraram que a primeira
abordagem tem maior potencial para a otimização semafórica, mas necessita de um
grande tempo de execução.
Oda et al. (1996) compararam o método de subida da montanha (hill-climbing) do
programa TRANSYT (ROBERTSON, 1969), o algoritmo de busca randômica, e também
um AG com cruzamento de ponto duplo e estratégia elitista. Os métodos foram executados em duas grandes redes. A avaliação da função objetivo foi feita pelo modelo de
simulação TRANSYT. O AG superou os outros dois métodos de otimização em ambas
as redes. Memon e Bullen (1996) compararam a eficiência de otimização do algoritmo
de busca Quasi-Newton e do AG em uma rede de cinco semáforos. Os cálculos dos
atrasos foram obtidos por meio de um modelo de simulação macroscópico. A otimização da sequência das fases não foi considerada. Os autores observaram desempenho
superior do AG quando comparados ao Quasi-Newton.
Park (1998) aplicou um AG para otimizar todas as variáveis de tempo, além do número e estrutura de estágios dos semáforos. Ele utilizou os operadores de cruzamento
uniforme, seleção por torneio binário e o método elitista. Uma variedade de critérios
de otimização foram considerados e as medidas de desempenho foram calculadas por
um modelo estocástico de simulação de tráfego. O AG trouxe resultado satisfatório na
otimização de redes hipotéticas de dois e quatro semáforos e superou o procedimento
de subida da montanha (hill-climbing) do TRANSYT-7F.
Vogel, Goerick e Seelen (2000) realizaram a otimização dos tempos semafóricos
utilizando também um AG. Entretanto, essa otimização teve como base dados locais e
interseções isoladas. A justificativa dos autores é de que os dados locais seriam base
para adaptação dos semáforos de modo reativo, ou seja, conforme o fluxo no local em
determinado horário.
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). Na-
2.5 Estado da Arte
28
quele trabalho, os autores realizaram a otimização dos tempos usando o TRANSYT-7F
e compararam os resultados com um AG desenvolvido pelos autores. Os critérios para
medição da eficiência foram os atrasos no trecho da ligação (link ) e o tamanho das
filas na rede. Para simulação de tráfego, juntamente com o AG, 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 para avaliação do algoritmo. Segundo aqueles autores, esse processo atrasa a convergência do algoritmo e consequentemente provoca uma demora
para obtenção dos resultados.
Park e Schneeberger (2002) avaliaram métodos de programação semafórica existentes na literatura aplicados em dados reais coletados em Virginia (EUA). Primeiramente, calibraram o modelo de simulação microscópica VISSIM com os dados coletados. Depois avaliaram se o comportamento da simulação era semelhante ao mundo
real. Depois de validar a área de simulação, cinco tipos de planos semafóricos foram testados: um plano antigo do departamento de transporte de Virginia, um plano
atual, um plano gerado por um AG, um plano gerado pelo programa Synchro e, por
fim, um plano gerado pelo programa TRANSYT-7F. Naquele experimento, aqueles autores constataram que não houve uma melhora significante por meio dos programas
de otimização.
Park et al. (2003) apresentaram um trabalho em que o AG otimizava intervalos
de planos semafóricos durante o dia (em programação semafórica de tempo fixo). O
algoritmo conseguiu estabelecer intervalos estáveis com um desempenho comparado
ao existente anteriormente. O estudo também comparou o desempenho de diferentes
números de intervalos usando múltiplas execuções do programa SimTraffic. Por fim, os
autores concluíram que usar o AG para minimizar o atraso é um caminho efetivo para
automatizar os planos semafóricos diários com consideráveis mudanças no volume
do tráfego.
Ceylan e Bell (2004) aplicaram um AG em conjunto ao programa TRANSYT e
ao PFE, criando assim o método GATRANSPFE, em uma abordagem diferente. O
método tinha duas propostas: gerar os planos semafóricos da rede enquanto resolvia
um problema de equilíbrio nas rotas dos motoristas. Os resultados mostraram que o
AG foi eficiente e simples para resolver o problema.
Lo e Chow (2004) usaram um AG com fitness dimensionado para comparar políticas estáticas e dinâmicas de temporização semafórica em uma via arterial de três
2.5 Estado da Arte
29
interseções. Os planos semafóricos gerados foram avaliados por um modelo de transmissão celular, que é uma alternativa de modelagem macroscópica para redes de
tráfego. Os resultados de um experimento em Hong Kong sobressaíram aos planos
existentes em 30-40% na redução do atraso global, dada uma boa solução inicial para
o algoritmo.
Tong, Cui e Fan (2006) apresentaram um modelo matemático de alocação do
tempo de trânsito na interseção proposta, cujo objetivo é maximizar a capacidade
do fluxo e minimizar atrasos de veículos na interseção. O AG foi utilizado para buscar
o resultado otimizado do modelo. Os resultados mostraram que o método proposto foi
eficiente na resolução do problema.
Masterton e Topiwala (2008) propuseram o uso de agentes de software distribuídos com AG para otimizar fase de semáforos em tempo real, assim adaptando-se
rapidamente a condições anormais de tráfego. Eles demonstraram a eficiência do uso
colaborativo de comunidades de agente de software para otimizar o fluxo do tráfego
em uma rede. Dentre as vantagens obtidas por aquele método, pode-se citar: cada
interseção pode gerenciar congestionamentos localmente, agente pode adaptar seu
plano para as melhores condições de tráfego e pode descobrir novas sequências de
fases para melhorar condições de tráfego inesperados.
Sanchez, Galan e Rubio (2008) aplicaram um técnica evolucionária baseada em
AG 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 Beowulf, com cinco nós (master e slave), o
que julgaram tornar o sistema escalável. Segundo os autores, após alguns testes,
decidiram utilizar como função de 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. No trabalho, a
região de estudo precisou ser discretizada para a utilização no modelo de simulação,
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 da técnica em outras regiões.
Singh, Tripathi e Arora (2009) propuseram uma estratégia de controle semafórico
em tempo real baseada em AG para prover bom desempenho nas interseções. O sistema inteligente desenvolvido faz decisões em tempo real para modificar tempos de
verde para um conjunto de semáforos. O modelo é desenvolvido usando um AG imple-
2.5 Estado da Arte
30
mentado em MATLAB. Além disso, desenvolveram um emulador para representação
de condições de tráfego em uma interseção isolada com as seguintes características: interface gráfica de usuário (GUI) desenvolvido em Java, geração aleatória de
veículos, direção veicular aleatória, exclusão de colisões, sinais com sequência fixa
de fases e semáforos com duração mínima do tempo de verde. O AG foi usado para
otimização semafórica e os resultados mostraram uma eficiência do sistema proposto.
Turky, Ahmad e Yusoff (2009) aplicaram o AG em um sistema de controle de tráfego
e travessia de pedestre para prover tempos verdes inteligentes baseado em carga de
tráfego dinâmico. A tecnologia foi aplicada em uma junção de duas faixas e otimizaram
dinamicamente os tempos de verde e vermelho para controlar o fluxo de veículos e
pedestres. Os resultados mostraram que o controlador dinâmico usando AG obteve
resultados melhores que o controlador de tempo fixo.
Sanchez, Moreno e Royo (2010) fizeram a otimização combinando um AG e um simulador microscópico de tráfego em um computador com arquitetura paralela (clusters
Beowulf ). Eles aplicaram a metodologia em uma área de “La Almozara”, Saragossa,
Espanha. A metodologia aplicada é bem semelhante com a utilizada em Sanchez,
Galan e Rubio (2008). Como no trabalho anterior, os autores também conseguiram
sucesso na aplicação.
Nota-se que os AG consolidaram-se nesse campo de pesquisa, pois como visto
acima, são vários os resultados satisfatórios nas aplicações. As abordagens são aplicadas nos diversos tipos de situações, sejam interseções isoladas ou em rede, sejam
planos semafóricos de tempo fixo, semi-atuado ou atuado. Portanto, a utilização de
algoritmos evolucionários multiobjetivo foi um caminho natural, a partir do momento
que se mostraram eficientes em problemas semelhantes.
2.5.3
Algoritmos Evolucionários Multiobjetivo
O avanço das pesquisas em otimização multiobjetivo sugeriu sua aplicação aos
problemas de programação semafórica, já que os AG tinham demonstrado eficiência.
Os trabalhos encontrados na literatura que utilizaram algoritmos evolucionários multiobjetivo baseados em Pareto são descritos nesta subseção, devido as semelhanças
com este trabalho.
Sun, Benekohal e Waller (2003) conduziram uma pesquisa sobre otimização semafórica multiobjetivo usando o algoritmo NSGA 2 (DEB et al., 2002), recentemente
2.5 Estado da Arte
31
lançado. Essa pesquisa é considerada a primeira que combinou o método evolucionário multiobjetivo ao problema em questão. Segundo eles, seria possível combinar as
duas funções mais utilizadas (atraso médio e número de paradas) para formular uma
nova estratégia. O método de Webster foi utilizado para calcular essas duas funções e
definir a qualidade das soluções geradas pelo NSGA 2. Para investigar a aplicação do
algoritmo utilizando o modelo proposto, os autores criaram um cenário de uma interseção isolada de duas fases. Os parâmetros do algoritmo foram: tamanho da população
igual a 150, codificação binária de 60 bits, 300 gerações, seleção por torneio binário,
cruzamento de ponto único com probabilidade de 0, 95, mutação com probabilidade de
0, 008.
A modelagem proposta foi testada em três problemas de teste criados pelos autores: padrão de tráfego uniforme sem restrição de ciclo no método de Webster, padrão
de tráfego uniforme com restrição de ciclo mínimo no método de Webster e padrão de
tráfego estocástico com restrição de ciclo mínimo no método de Webster. Nos três experimentos realizados foi possível encontrar um conjunto de soluções não-dominadas
em poucas gerações. Com isso, os autores concluíram que o AG multiobjetivo teria
potencial a ser usado no problema, além de verificar que o NSGA 2 pôde encontrar
múltiplas soluções com planos de desenho ótimo segundo as fórmulas de Webster.
Por fim, os autores mostraram que a convergência do algoritmo é aceitável, mas assumiram que a aplicação do NSGA 2 em redes de controle semafórico deveria ser
futuramente investigada.
Hu, Gao e Yang (2010) apresentaram um modelo multiobjetivo de controle semafórico de tempo fixo em interseções isoladas não saturadas. Além disso, compararam
os diferentes índices de desempenho do algoritmo. Para isso, os autores propuseram
um modelo em que as variáveis otimizadas seriam o tamanho do ciclo e os tempos de
verde. Para tanto, o modelo foi definido com três funções objetivo: atraso médio dos
veículos, número médio de paradas dos veículos e tamanho relativo máximo da fila de
veículos. Essas equações também foram extraídas do método de Webster. Ao terminar o modelo, os autores implementaram um algoritmo NSGA 2 seguindo o modelo
tradicional proposto por Deb et al. (2002).
Para testar o modelo, utilizaram uma interseção localizada em Yangpu, Shanghai.
A interseção cruzava duas ruas e continha quatro fases. Ademais, os dados de volume foram obtidos de 10 às 11 da manhã. Os parâmetros usados no NSGA 2 foram:
800 gerações, população de 120 indivíduos, probabilidade de cruzamento igual a 0, 95
2.5 Estado da Arte
32
e probabilidade de mutação igual a 0, 05. Ademais, os limites configurados da programação semafórica foram: tamanho mínimo de ciclo igual a 56 segundos e tamanho
máximo igual a 240 segundos, tempo mínimo de verde igual a 10 segundos e tempo
máximo igual a 100 segundos. A partir dos resultados, os autores concluíram que as
funções objetivo atraso médio e tamanho relativo máximo da fila não são conflitantes
entre si e mostraram que as duas estão linearmente correlacionadas, enquanto que a
função número médio de paradas conflita com as demais. Depois os autores compararam o trabalho com o método de Webster e verificaram que o método proposto diminui
o atraso médio em 47, 9% e reduz o tamanho relativo máximo da fila em 48, 3%, enquanto ligeiramente aumenta o número de paradas em 3, 3%. Portanto, demonstrou-se
que a técnica evolucionária multiobjetivo proposta pôde resolver o problema.
2.5.4
Outros Métodos
O foco deste trabalho é o uso de métodos de otimização baseado nos AG, principalmente os métodos evolucionários multiobjetivo. Entretanto, outros métodos têm
sido aplicados ao problema. Nesta seção, alguns trabalhos serão citados, com o objetivo de fornecer referências para tipos diferentes de abordagens. Dentre os métodos
mais utilizados no problema de programação semafórica, destacam-se pela capacidade de aplicação.
Nas abordagens multi-agentes ou baseadas em teoria de jogos, os trabalhos de
Bazzan (1995), Porche e Lafortune (1998), Roozemond (2001), Choy, Srinivasan e
Cheu (2003), Kosonen (2003), Bazzan (2005), Oliveira e Bazzan (2005), Cheng, Epelman e Smith (2006), Srinivasan e Choy (2006), Alvarez, Poznyak e Malo (2007), Lammer e Helbing (2008), Shamshirband et al. (2008), Xie et al. (2011) se destacam por
suas aplicações. Esses trabalhos geralmente consideram os semáforos e os veículos
como agentes e trabalham a interação entre eles, em busca do equilíbrio na rede.
Os trabalhos de Spall e Chin (1997), Henry, Farges e Gallego (1998), López
(1999), Saito e Fan (2000), Bingham (2001), Guojiang e Youxian (2005), Choy, Srinivasan e Cheu (2006), Srinivasan, Choy e Cheu (2006), Shen e Kong (2009) utilizaram redes neurais artificiais para solucionar o problema de programação semafórica.
Algumas dessas aplicações são utilizadas em conjunto com lógica fuzzy. Outros trabalhos dedicam-se ao uso exclusivo de lógica fuzzy, tais como Chiu (1993), Kim (1997),
Hong et al. (1999), Lee e Lee-Kwang (1999), Trabia, Kaseko e M. (1999), Chou e
Teng (2002), Murat e Gedizlioglu (2005), Zarandi e Rezapour (2009), Azimirad, Pariz
2.5 Estado da Arte
33
e Sistani (2010), Gokulan e Srinivasan (2010), Ma, Geng e Yan (2012).
São também aplicados à programação de semáforos, o método branch-and-bound
em Pillai e Rathi (1998) e Yan, Dridi e El Moudni (2008), a técnica swarm intelligence
em Oliveira e Bazzan (2006) e Renfrew e Yu (2009). Recentemente, o método de
otimização por colônia de formigas foi empregado, como em Renfrew (2009), Zechman
et al. (2010), Dacierno, Gallo e Montella (2010), Baskan e Haldenbilen (2011), He e
Hou (2011), Putha, Quadrifoglio e Zechman (2012).
Por fim, é necessário observar a grande importância dos manuais de programação semafórica usados nas agências controladoras do tráfego, como, por exemplo,
DENATRAN (1984), TRB (2000), Fitzpatrick, Wooldridge e Blaschke (2005), Guberinic, Senborn e Lazic (2008), Koonce (2008), Bonneson, Sunkari e Pratt (2009), TRB
(2010), CONTRAN (2012). Tais manuais definem diretrizes para as prefeituras das
cidades em todo o mundo.
2.5.5
Trabalhos do GEOPROC
Neto e Almeida (2009) desenvolveram uma ferramenta de código aberto chamada
GISSIM, incorporada ao OpenJUMP, que realiza simulação microscópica, no qual é
possível reproduzir o comportamento do tráfego. Os resultados permitem realizar avaliações de várias situações reais de trânsito e são utilizados para auxiliar engenheiros
de tráfego nas tomadas de decisão.
Oliveira e Almeida (2010) criaram o GISSIM-TL, uma ferramenta capaz de gerar tempos semafóricos utilizando técnicas de inteligência computacional. Os autores
utilizaram duas técnicas para testar sua ferramenta: AG e algoritmo de seleção CLONAL (CLONALG). GISSIM-TL foi acoplado ao GISSIM, já que este recupera redes de
tráfego diretamente do SIG OpenJUMP, sem necessidade de redesenho das microrregiões. Problemas práticos foram avaliados por meio de experimentos e comparações
com a literatura, mostrando a eficiência da ferramenta. Os autores utilizaram técnicas baseadas em abordagem mono-objetivo. Essa é uma limitação daquele trabalho,
já que a abordagem multiobjetivo é capaz de realizar uma análise mais completa de
problemas do mundo real e, como consequência, obter melhores resultados.
34
3
OTIMIZAÇÃO MULTIOBJETIVO
De acordo com Coello (1999a), otimização multiobjetivo é um tópico de pesquisa
muito importante, tanto para cientistas quanto para engenheiros, devido à natureza
multiobjetivo da maioria dos problemas do mundo real. Por isso, esse campo de pesquisa tem crescido consideravelmente nos últimos anos, como indica o número notável
de artigos publicados, principalmente nos últimos 25 anos, em conferências internacionais e periódicos em todo o mundo.
Segundo Justesen (2009), problemas multiobjetivo são problemas com dois ou
mais objetivos, geralmente conflitantes. A principal diferença para a otimização monoobjetivo é que um problema com múltiplos objetivos não possui uma única solução
ótima; ao contrário, possui um conjunto de soluções ótimas, no qual cada solução
compete com as outras, representando ganho ou perda (trade-off ) em determinados
objetivos.
Deb (2008) define que um problema de otimização multiobjetivo consiste em um
problema de otimização que envolve um número de funções objetivo a serem minimizadas e/ou maximizadas simultaneamente. Além disso, um problema pode ser constituído por equações e inequações restritivas, que devem ser satisfeitas para produzir
soluções factíveis.
Osyczka (1985) define melhor um problema de otimização multiobjetivo como:
“problema de encontrar um vetor de variáveis de decisão que satisfaça
as restrições e otimize um vetor de funções, cujos elementos representam as funções objetivo. Essas funções formam uma descrição
matemática de desempenho e estão geralmente em conflito, uma com
outra. Portanto, o termo otimizar neste contexto significa encontrar
uma solução com valores aceitáveis para todas as funções objetivo.”
Segundo Coello (1999a), a declaração formal para um problema multiobjetivo constituise de:
3 OTIMIZAÇÃO MULTIOBJETIVO
35
Encontrar o vetor X ∗ = [x∗1 , x∗2 , ..., x∗n ]T que satisfaz as m inequações restritivas:
gi (X) ≥ 0 i = 1, 2, ..., m;
(3.1)
hi (X) = 0 i = 1, 2, ..., p;
(3.2)
as p equações restritivas:
e otimiza o vetor de funções:
F = [f1 (X), f2 (X), ..., fk (X)]T ,
(3.3)
onde X = [x1 , x2 , ..., xn ]T é o vetor de variáveis de decisão.
Em outras palavras, dentre o conjunto de todos os números que satisfaçam as
equações (3.1) e (3.2), é necessário determinar um conjunto particular x∗1 , x∗2 , ..., x∗k
que renda os valores ótimos das funções na Equação (3.3).
A Figura 9 ilustra a região factível do problema bi-objetivo F x, exemplificando uma
solução X = (x1, x2) no espaço de parâmetros X, que, a partir da transformação
utilizando a função f (.) gera a solução y1 no espaço de objetivos Y .
Figura 9: Mapeamento de uma solução x (espaço de parâmetros) para o espaço de
objetivos Y feito pela função f (.)
No processo de tomada de decisão (em problemas do mundo real) é necessário
obter a solução ótima. Embora existam vários caminhos para abordar um problema
3.1 Conjunto Pareto
36
de otimização multiobjetivo, o trabalho maior está concentrado na aproximação do
conjunto Pareto.
3.1
Conjunto Pareto
De acordo com Takahashi (2007), o objeto fundamental da otimização multiobjetivo
consiste em definir um conjunto de soluções X ∗ , denominado conjunto Pareto, que irá
conter possíveis soluções ótimas para o problema. Os elementos desse conjunto são
definidos a seguir.
3.1.1
Dominância
Considerando um problema de otimização, sendo x1 e x2 dois pontos quaisquer
no espaço de variáveis X, diz-se que o ponto x1 domina o ponto x2 se f (x1 ) ≤ f (x2 ) e
x1 6= x2 , o que significa que f (x1 ) é melhor que f (x2 ) em ao menos uma coordenada
sem ser pior em nenhuma outra. Equivalentemente, diz-se que f (x1 ) ∈ Y domina
f (x2 ) ∈ Y , nessas mesmas condições (TAKAHASHI, 2007).
Sabendo-se que y1 = f (x1 ) e y2 = f (x2 ), a Figura 10 ilustra a dominância da
solução y1 em relação y2 no espaço de objetivos Y .
Figura 10: Solução y1 domina y2 no espaço de objetivos Y
Na figura, o ponto y1 é melhor (ou menor) nas duas funções objetivo f 1 e f 2 que
o ponto y2, o que indica a sua dominância.
3.2 Algoritmos Relevantes
3.1.2
37
Solução Pareto-ótima
Diz-se que x∗ ∈ X é uma solução Pareto-ótima (eficiente, não-dominada, nãoinferior) se não existe outra solução x ∈ X tal que f (x) ≤ f (x∗ ) e x 6= x∗ , ou seja, se
x∗ não é dominada por nenhuma outra solução factível (TAKAHASHI, 2007).
3.1.3
Fronteira Pareto-ótima
Segundo Coello (1999b), o conceito de conjunto Pareto foi formulado por Vilfredo
Pareto no século XIX, e constituiu a origem da pesquisa em otimização multiobjetivo.
O conjunto de todas as soluções Pareto-ótima do problema no espaço dos objetivos é denominado de Fronteira Pareto-ótima. Na Figura 11, os pontos y1 e y2
pertencem à Fronteira Pareto-ótima. Nota-se também que as soluções dessa fronteira
não se dominam.
Figura 11: Fronteira Pareto-ótima no espaço de objetivos Y
3.2
Algoritmos Relevantes
Um grande número de técnicas estocásticas de otimização como simulated annealing, busca tabu, colônia de formigas, etc. podem ser usadas para gerar o conjunto
de soluções ótimas. Mas, de acordo com Abraham e Jain (2005), as soluções obtidas frequentemente tendem a prender-se em uma boa aproximação e, com isso, eles
3.2 Algoritmos Relevantes
38
não garantem identificar o conjunto Pareto. Os algoritmos evolucionários são caracterizados por possuir uma população de soluções candidatas e, portanto, algoritmos
evolucionários multiobjetivo podem trabalhar com um conjunto inteiro de soluções potenciais, melhorando o processo de busca. Por isso, esse grupo de algoritmos atingiu
grande aplicabilidade.
O pesquisador mexicano Carlos A. Coello Coello, autor de vários surveys1 (COELLO, 1999a) (COELLO, 1999b) (COELLO, 2000) (COELLO; LAMONT, 2004) (COELLO, 2005),
divide a classe dos algoritmos evolucionários multiobjetivo em três tipos principais:
funções agregadas, abordagens baseadas em população e abordagens baseadas em
Pareto.
3.2.1
Funções agregadas
Funções agregadas consistem da abordagem mais simplificada para tratar múltiplos objetivos. Ela tem como principal característica combinar todos os objetivos em
um único, utilizando adição, multiplicação ou alguma outra combinação de operadores
aritméticos. Esses são os métodos mais antigos de otimização multiobjetivo e foram
utilizados com relativo sucesso na literatura, como, por exemplo, em teoria de jogos
(RAO, 1987) (PÉRIAUX; SEFRIOUI; MANTEL, 1997), goal programming (WIENKE; LUCASIS;
KATEMAN,
1992) (DEB, 1999), goal attainment (WILSON; MACLEOD, 1993) (ZEBULUM; PA-
CHECO; VELLASCO,
ANSEN,
1998) e algoritmos min-max (HAJELA; LIN, 1992) (COELLO; CHRISTI-
1998). Entretanto, essa abordagem é hoje negligenciada pelos pesquisadores
da área, devido ao surgimento de técnicas mais eficientes e à sua limitação, como o
fato de não encontrar múltiplas soluções eficientes em uma única execução.
3.2.2
Abordagens baseadas em população
Nestas abordagens, a população do algoritmo evolucionário é usada para diversificar a busca, mas o conceito de dominância não é diretamente incorporado no processo de seleção. O maior exemplo desse tipo de abordagem é o Vector Evaluated Genetic Algorithm (VEGA), proposto por Schaffer (SCHAFFER, 1985). VEGA consiste de um simples algoritmo genético com um mecanismo de seleção modificado.
Esse tipo de abordagem possui alguns problemas mas, devido à sua simplicidade,
1
Coello mantém uma lista de referências bibliográficas sobre Otimização Evolucionária Multiobjetivo
no sítio: http://www.lania.mx/∼ccoello/EMOO/EMOObib.html
3.2 Algoritmos Relevantes
39
tem atraído vários pesquisadores que, inclusive, propuseram variações (VENUGOPAL;
NARENDRAN,
1992) (SRIDHAR; RAJENDRAN, 1996) (NORRIS; CROSSLEY, 1998) (ROGERS,
2000).
3.2.3
Abordagens baseadas em Pareto
Goldberg (1989) discorreu sobre o caminho para melhorar a resolução de problemas multiobjetivo, tomando como base os problemas existentes na abordagem do
algoritmo VEGA. O procedimento dele consistiu em adicionar um esquema de seleção
baseado no conceito de Pareto. Essa proposta tornou-se, desde então, o padrão dos
algoritmos evolucionários multiobjetivo. Duas gerações de algoritmos surgiram após a
proposta de Goldberg.
A primeira geração caracteriza-se pelo uso de compartilhamento e nicho do fitness combinado com classificação do Pareto. Os algoritmos mais relevantes dessa
geração foram: Multiobjective Genetic Algorithm (MOGA) (FONSECA; FLEMING, 1993),
Niched-Pareto Genetic Algorithm (NPGA) (HORN; NAFPLIOTIS; GOLDBERG, 1994), Nondominated Sorting Genetic Algorithm (NSGA) (SRINIVAS; DEB, 1995).
A segunda geração caracteriza-se pela introdução de elitismo. Essa estratégia
trouxe uma melhora para os algoritmos, cujos mais relevantes são: Strength Pareto
Evolutionary Algorithm (SPEA) (ZITZLER; THIELE, 1999), Pareto Envelope-based Selection Algorithm (PESA) (CORNE; KNOWLES; OATES, 2000), Pareto Archived Evolution
Strategy (PAES) (KNOWLES; CORNE, 2000), Micro-Genetic Algorithm (COELLO; PULIDO,
2001), Strength Pareto Evolutionary Algorithm 2 (SPEA 2) (ZITZLER; LAUMANNS; THIELE,
2001), Niched Pareto Genetic Algorithm 2 (NPGA 2) (ERICKSON; MAYER; HORN, 2001),
Nondominated Sorting Genetic Algorithm 2 (NSGA 2) (DEB et al., 2002).
Segundo Coello (2005), uma análise da evolução da literatura sobre otimização
evolucionária multiobjetivo revela um grande interesse sobre a aplicação de tais técnicas em problemas do mundo real, já que a maioria dos problemas do mundo real
são de natureza multiobjetivo. As aplicações estendem-se sobre toda a engenharia
(elétrica, hidráulica, estrutural, aeronáutica, robótica, controle, etc.), química, física,
medicina e ciência da computação, dentre outras.
3.3 Algoritmo NSGA 2
3.3
40
Algoritmo NSGA 2
O algoritmo Nondominated Sorting Genetic Algorithm (NSGA) foi proposto por Srinivas e Deb (1995), sendo um dos primeiros algoritmos evolucionários multiobjetivo
para otimização de funções. Entretanto, com o decorrer dos anos, foi necessário propor a extensão da primeira versão do NSGA, devido ao surgimento de críticas. Com
isso, o NSGA 2 foi apresentado por Deb et al. (2002) para minimizar três dificuldades
existentes até então:
• Alta complexidade computacional do procedimento de classificação das fronteiras não dominadas: o algoritmo existente tinha complexidade computacional de
O(M N 3 ) (onde M é o número de objetivos e N é o tamanho da população);
• Abordagem não elitista: estratégias elitistas podem acelerar o desempenho do
AG significantemente, pois ajudam a prevenir a perda de boas soluções a cada
vez que são encontradas;
• Necessidade de especificação do parâmetro σshare : o principal problema é a
especificação de um parâmetro, já que o uso de parâmetros errados pode trazer
dificuldades à convergência do algoritmo. Um mecanismo para preservação de
diversidade sem parâmetros é desejável.
O NSGA 2 herda as características dos algoritmos genéticos tradicionais, como a
geração da população, operadores genéticos etc. Entretanto, o operador de classificação dos indivíduos, que define a “qualidade” das soluções é dividido em duas etapas:
classificação das fronteiras e atribuição do operador de diversidade. Nas próximas
subseções, as etapas do algoritmo são detalhadas.
3.3.1
Procedimento Fast Nondominated Sort
Este procedimento, dado pelo Algoritmo 1, é responsável por classificar os níveis
de dominância de cada solução e, por fim, gerar as fronteiras para classificação das
soluções.
Primeiramente, para cada solução, duas entidades são calculadas: contador de
dominância np (o número de soluções que dominam a solução p) e o conjunto de
soluções que a solução p domina, representado por Sp . Isso requer O(M N 2 ) comparações. Todas as soluções na primeira fronteira não dominada terão o contador de
3.3 Algoritmo NSGA 2
41
Algoritmo 1 Fast Nondominated Sort. Adaptado de Deb et al. (2002)
1: para cada p ∈ P faça
2:
Sp = ∅ // Conjunto de soluções que p domina
3:
np = O // Contador de soluções que dominam p
4:
F1 = ∅ // Primeira fronteira não dominada
5:
para cada q ∈ P faça
6:
se (p ≺ q) então
7:
Sp = Sp ∪ {q} // Se p domina q, então adiciona q no conjunto Sp
8:
senão se (q ≺ p) então
9:
np = np + 1 // Se q domina p, então incrementa o contador np
10:
fim se
11:
fim para
12:
se (np = 0) então
13:
prank = 1 // Se o contador np é zero, então é uma solução não-dominada
14:
F1 = F1 ∪ {p} // Pertence à primeira fronteira
15:
fim se
16: fim para
17: i = 1 // Contador de fronteiras, inicia na primeira fronteira (soluções nãodominadas encontradas anteriormente)
18: enquanto Fi 6= ∅ faça
19:
Q = ∅ // Conjunto de soluções pertencentes a fronteira i + 1
20:
para cada p ∈ Fi faça
21:
para cada q ∈ Sp faça
22:
nq = nq −1 // Para cada solução q dominada por p decrementa-se o contador
23:
se (nq = 0) então
24:
qrank = i + 1 // Se nq é zero, então não existe outra solução que domina q
25:
Q = Q ∪ {q} // Pertence à fronteira i + 1
26:
fim se
27:
fim para
28:
fim para
29:
i=i+1
30:
Fi = Q // Fronteira i recebe as soluções encontradas do conjunto Q
31: fim enquanto
dominância igual a zero. Agora, para cada solução p com np = 0, o algoritmo visita
cada membro q do conjunto Sp e reduz o contador de dominância por um. Fazendo
isso, se para qualquer membro q o contador de dominância torna-se zero, ele é colocado em uma lista separada Q. Esses membros pertencem à segunda fronteira
não dominada. Agora, o procedimento continua com cada membro de Q e a terceira
fronteira é identificada. Esse processo continua até todas as fronteiras serem identificadas. Para cada solução p no segundo nível e em níveis superiores, o contador de
dominância np pode ser N − 1. Assim, cada solução p será visitada ao menos N − 1
vezes antes que o contador de dominância torne-se zero. Neste ponto, o nível de
dominância é atribuído à solução e esta nunca será visitada novamente. Desde que
3.3 Algoritmo NSGA 2
42
existam na maioria N − 1 de tais soluções, a complexidade total é O(N 2 ). Portanto, a
complexidade global do procedimento é O(M N 2 ).
Para um problema de minimização de duas funções objetivo, um exemplo do procedimento descrito no Algoritmo 1 é ilustrado na Figura 12.
Figura 12: (a) Conjunto de pontos (b) Separação das fronteiras de dominância. Adaptado de Deb (2008)
Portanto, a partir da classificação das fronteiras define-se a dominância entre soluções de diferentes fronteiras. Ainda assim, verifica-se que as soluções que não são
dominadas por nenhuma outra, pertencem à fronteira não dominada.
3.3.2
Preservação da Diversidade
O NSGA original usou a abordagem conhecida como função de compartilhamento
para manter diversidade em uma população. Esse método envolve o uso de um parâmetro σshare . Entretanto, no algoritmo NSGA 2, a função de compartilhamento foi
substituída pelo procedimento Crowding Distance Assignment. Esta nova abordagem
não requer nenhum parâmetro definido pelo usuário para manter a diversidade entre
os membros da população (DEB et al., 2002). Além disso, esse novo procedimento
tem uma melhor complexidade computacional. O procedimento foi dividido em duas
partes.
3.3.2.1
Estimativa de Densidade
Este procedimento primeiramente ordena a população para cada função objetivo
em ordem ascendente de magnitude. Depois, atribui um valor infinito às soluções limites (soluções com menor e maior valores da função). Para todas as outras soluções
3.3 Algoritmo NSGA 2
43
intermediárias são atribuídos um valor de distância igual à diferença absoluta normalizada nos valores de funções das duas soluções adjacentes. Este calculo é feito para
as outras funções objetivo. Cada função objetivo é normalizada antes de calcular o
crowding distance. O Algoritmo 2 mostra a atribuição do crowding distance em um
conjunto não dominado I.
Algoritmo 2 Crowding Distance Assignment. Adaptado de Deb et al. (2002)
1: l = |I|
2: para cada i faça
3:
I[i]distancia = 0 // Inicializa todos os atributos como zero
4: fim para
5: para cada objetivo m faça
6:
I = ordena(I, m) // Ordena usando valor de cada objetivo
7:
I[1]distancia = I[l]distancia = ∞ // Valor infinito para soluções limite
8:
para i = 2 até (l − 1) faça
min
max
) // Cálculo do
− fm
9:
I[i]distancia = I[i]distancia + (I[i + 1].m − I[i − 1].m)/(fm
crowding distance
10:
fim para
11: fim para
O valor I[i].m refere-se ao valor da m-ésima função objetivo do i-ésimo indivíduo
min
max
são os valores máximo e mínimo da me fm
no conjunto I e os parâmetros fm
ésima função objetivo. A Figura 13 mostra um exemplo para este cálculo.
Figura 13: Cálculo do crowding distance. Pontos em negrito pertencem à mesma
fronteira. Extraído de Deb et al. (2002)
A complexidade deste procedimento é definida pelo algoritmo de ordenação. Desde
que as M ordenações independentes em todas as N soluções (quando todos os membros da população estão na fronteira I) sejam consideradas, o algoritmo tem complexidade computacional igual a O(M N logN ). Quando todos os membros da população
no conjunto I possuem um valor para o crowding distance, será possível comparar
duas soluções.
3.3 Algoritmo NSGA 2
3.3.2.2
44
Operador Crowded-Comparison
O operador (≺n ) guia o processo de seleção do algoritmo. Assume-se que cada
indivíduo i na população tem dois atributos: rank de dominação (irank ) e crowding
distance (idistancia ). Define-se uma ordem parcial ≺n como:
se (irank < jrank ) ou ((irank = jrank ) e (idistancia > jdistancia )) então i ≺n j.
O rank de dominação representa a fronteira em que a solução se localiza. Entre
duas soluções com diferentes ranks de dominação, a solução com menor rank é escolhida. Entretanto, se ambas soluções pertencem à mesma fronteira, então a solução
com maior crowding distance é escolhida (região menos povoada).
3.3.3
Esquema Geral
Finalmente, após detalhar os operadores específicos do NSGA 2, tem-se o procedimento geral mostrado no Algoritmo 3.
Algoritmo 3 Pseudo-código do NSGA 2. Adaptado de Deb et al. (2002)
1: t = 0; // Geração atual
2: Pt = gera_população_inicial(tamanho_da_populacao); // Gera população de 2N
3: Pt = avaliação_de_soluções(Pt );
4: Qt = 0; // População de filhos
5: enquanto (nao_chega_no_criterio_de_parada) faça
6:
Rt = Pt ∪ Qt ; // Rt é a população de pais e filhos
7:
F = fast_non_dominated_sort(Rt ); // Classificação das fronteiras de dominância
8:
Pt+1 = 0;
9:
i = 1; // Contador para o número de fronteiras
10:
enquanto |Pt+1 | + |Fi | ≤ tamanho_da_populacao faça
11:
crowding_distance_assignment(Fi ); // Atribuição do crowding distance
12:
Pt+1 = Pt+1 ∪ Fi ;
13:
i = i + 1;
14:
fim enquanto
15:
ordena(Fi , ≺ n); // Ordena a fronteira Fi
16:
Pt+1 = Pt+1 ∪ Fi [1 : (tamanho_da_populacao − |Pt+1 |)]; // Adiciona os indivíduos
restantes para completar a população
17:
Qt+1 = operadores_genéticos(Pt+1 ); // Seleção, cruzamento e mutação
18:
Qt+1 = avaliação_de_soluções(Qt+1 );
19:
t = t + 1;
20: fim enquanto
3.4 Memória e Vizinhança Adaptativa
45
Nesse procedimento, a população inicial é gerada aleatoriamente com 2N indivíduos. Depois os indivíduos são avaliados, utilizando o modelo de simulação adotado
para o problema. Os operadores do NSGA 2 (Fast Nondominated Sort e Crowding
Distance) são aplicados sobre as soluções geradas. Com isso, é possível definir as
melhores soluções, e N pais são selecionados para gerar os descendentes. Os N
pais cruzam-se, gerando outros N filhos e o operador de mutação é aplicado sobre
eles. Finalmente, os N filhos são avaliados e, juntamente com os N pais, integram a
geração futura de tamanho 2N (com fortes características de elitismo). Esse processo
é repetido até que o critério de parada seja satisfeito.
3.4
Memória e Vizinhança Adaptativa
Segundo Yuen e Chow (2009), em muitos problemas do mundo real, o processo
de avaliação de funções é a parte mais cara do processo de otimização nos algoritmos
estocásticos. Esse fator pode ser agravado em problemas cujas funções constituemse de funções complexas, ou ainda, modelos baseados em simulação. Uma medição
recente em nosso projeto comprovou essa premissa, pois o tempo de avaliação da
função no algoritmo utilizado consumia 99,9% do tempo total de solução. Uma característica agravante para o consumo de tempo é a revisitação de soluções, ou seja, a
reavaliação de soluções que já tinham sido geradas anteriormente. Um mecanismo
para armazenar soluções já visitadas torna-se interessante, já que exclui esse fator.
Muitos algoritmos estocásticos (algoritmos genéticos, simulated annealing, colônia de formigas) não memorizam soluções já visitadas. De acordo com Yuen e Chow
(2009), uma exceção notável é o método Busca Tabu. Entretanto, tal método não
armazena todas as soluções e, portanto, essa reavaliação é inevitável. Segundo Carrano, Moreira e Takahashi (2011), a associação de um algoritmo evolucionário com
um mecanismo de memória pode eliminar a reavaliação de soluções. Além disso, tem
a habilidade de não incluir soluções duplicadas na população. Essa característica é
essencial, pois cria uma regra importante para manutenção da diversidade, evitando
a convergência prematura do algoritmo.
Carrano, Moreira e Takahashi (2011) apresentaram um algoritmo genético baseado em memória para resolver problemas de otimização multiobjetivo. Esse algoritmo
é uma implementação binária do NSGA 2 e utiliza uma tabela Hash para armazenar
todas as soluções já visitadas durante a execução. Na técnica, a estrutura de dados
3.4 Memória e Vizinhança Adaptativa
46
exclui a revisitação de soluções e provê a recuperação e armazenamento de dados
com baixo custo computacional. Ademais, a estrutura controla a densidade de avaliações de função no espaço de variáveis. Isso é obtido por meio de uma codificação
de tamanho variável. Tal esquema de codificação proporciona uma vizinhança adaptativa, controlando a densidade da amostragem de novas soluções. Essa adaptação
é feita sem configuração de parâmetros.
O problema abordado no presente trabalho utiliza uma simulação como método
de avaliação. Essa etapa demanda um grande tempo e, portanto, excluir a revisitação de soluções é desejável. Para conseguir isso, a proposta de Carrano, Moreira e
Takahashi (2011) será adotada como referência. Nas próximas subseções, são explicados conceitos sobre Tabela Hash e operadores adaptativos.
3.4.1
Tabela Hash
Tabelas Hash são estruturas de dados que realizam armazenamento e indexação
de dados usando transformação de chaves. Seja M o tamanho da tabela Hash (número de slots no qual é possível armazenar dados), N o número de pontos que serão
armazenados, e P N o número de todos os possíveis pontos que seriam encontrados. Supõe-se que cada registro será armazenado como uma única chave. O slot da
Tabela Hash cujo registro i será armazenado (posi ) é definido na Equação (3.4),
posi = hash(keyi ),
(3.4)
onde:
hash(.) é a função hash adotada; e
keyi é a chave única do registro i.
Carrano, Moreira e Takahashi (2011) adotaram uma adaptação da função hash de
Pearson para armazenar os pontos visitados por um algoritmo genético multiobjetivo.
O número de slots no qual é possível armazenar dados (M ) é definido na Equação
(3.5),
M = 2bind ,
(3.5)
3.4 Memória e Vizinhança Adaptativa
47
onde:
bind é o número de bits usados na indexação.
Com base nessa definição, cada indivíduo é dividido em palavras binárias de tamanho bind e estas palavras são usadas para encontrar o slot correspondente usando
o Algoritmo 4.
Algoritmo 4 Pseudo-código do hash de Pearson. Adaptado de Carrano, Moreira e
Takahashi (2011)
1: h[0] = 0 l
m
n·nbits
2: nloops =
bind
3: para i = 1...nloops faça
4:
h[i] = T [Bin2Dec(Dec2Bin(h[i − 1]) ⊕ key[(i − 1).bind + 1, ..., i.bind ])]
5: fim para
6: return h[nloops ]
No algoritmo, n é o número de variáveis de decisão, nbits é o número de bits por variável, T é um vetor que contém uma permutação aleatória da sequência {0, ..., (2bind −
1)}, T [p] é o p-ésimo termo de tal permutação, BIN 2DEC(B) converte uma palavra
binária B de tamanho bind para decimal, DEC2BIN (D) converte um valor decimal D
na faixa {0, ..., 2bind } para binário de tamanho bind , ⊕ é a função ou-exclusivo (XOR),
key[a, ..., b] retorna os bits que estão nas posições a, ..., b da palavra binária key.
3.4.2
Vizinhança Adaptativa
Algoritmos genéticos tradicionais possuem a vizinhança geralmente definida pela
distância de Hamming, e os operadores de mutação e cruzamento são geralmente
construídos baseando-se em tal distância. Carrano, Moreira e Takahashi (2011) propuseram a criação de uma vizinhança adaptativa usando um tipo de codificação de
tamanho variável, na qual cada variável i em um indivíduo é representada por uma
palavra binária de tamanho nbits e um parâmetro individual depi ≤ nbits , que indica a
profundidade da variável. A variável de profundidade define que somente os depi bits
mais significantes da variável i podem ser alterados pelos operadores genéticos.
Obviamente é necessário incrementar a profundidade das variáveis com o objetivo de alcançar a precisão desejável do algoritmo. Esta é a chave de como a vizinhança adaptativa baseada em memória trabalha (CARRANO; MOREIRA; TAKAHASHI,
3.4 Memória e Vizinhança Adaptativa
48
2011). Cada vez que o algoritmo tentar visitar uma solução previamente visitada, ele
considera a tentativa de reavaliação como uma indicação de que a região em torno
de tal solução será explorada com uma precisão melhorada. Portanto, a profundidade
de uma das variáveis é aumentado, com o objetivo de aumentar a cardinalidade da
vizinhança daquela solução. Sendo assim, é possível melhorar o processo de busca
do algoritmo, encontrando melhores soluções com essa abordagem. Tal fato foi demonstrado por experimentos realizados em problemas da literatura.
49
4
DESENVOLVIMENTO
O problema de programação semafórica tem sido abordado de diferentes maneiras
na literatura, seja na modelagem, no tipo de controle ou estratégia adotada. O foco
deste trabalho está em duas características principais relacionadas à sua aplicação:
1. Tempo fixo: o plano semafórico de um dia é dividido em intervalos de horário.
Esses intervalos geralmente correspondem às configurações diferentes para as
variações do fluxo. O plano é configurado de acordo com os dias da semana
(domingo, segunda, terça, quarta, quinta, sexta e sábado). Com isso, é possível gerenciar as diferentes demandas diárias de fluxo, como, por exemplo, nos
horários de picos dos dias úteis em contraste aos domingos. Para realizar esse
tipo de controle é necessário fazer a contagem volumétrica dos trechos anteriormente citados, depois configurar os planos de acordo com o volume encontrado
nas regiões;
2. Controle em Rede: o plano semafórico é definido para uma rede de tráfego,
que contém uma rede de semáforos trabalhando em conjunto. Essa estratégia
de controle visa otimizar o tráfego global da rede e não somente interseções
isoladas. Na verdade, essa estratégia de controle tem sido menos utilizada que
a otimização em interseções isoladas, embora o funcionamento em rede seja
uma característica predominante em todos os casos reais.
O problema tratado neste trabalho define-se como um controle semafórico de
tempo fixo em rede. Para solucioná-lo, propõe-se uma técnica que alia a modelagem
de planos semafóricos de tempo fixo em redes de tráfego, um algoritmo de otimização multiobjetivo NSGA 2 (DEB et al., 2002) com conceitos de memória e operadores
adaptativos (CARRANO; MOREIRA; TAKAHASHI, 2011) e o simulador microscópico GISSIM (NETO; ALMEIDA, 2009). Esta técnica está ilustrada na Figura 14.
4.1 Modelagem do Plano Semafórico
50
Figura 14: Técnica aplicada ao problema de programação semafórica
Na figura observa-se que é necessário fazer um projeto do plano semafórico inicial,
indicando o número de fases e estágios para as interseções da rede. Depois disso, o
algoritmo multiobjetivo NSGA 2 otimiza os tempos semafóricos e gera um conjunto de
planos semafóricos otimizados, que, por sua vez, são atribuídos ao simulador GISSIM
para realizar simulação microscópica estocástica na área de estudo, retornando os
resultados da simulação. Esses resultados definem a “qualidade” de cada plano semafórico gerado. Esse processo é repetido até que se obtenha resultados satisfatórios
para otimizar o tráfego da área simulada.
Cada etapa tem características próprias que são detalhadas nas próximas subseções, iniciando pela modelagem dos planos semafóricos de tempo fixo em redes
de tráfego. Em seguida, o framework para otimização multiobjetivo é descrito, assim
como sua extensão para o algoritmo NSGA 2. Por fim, os pontos relevantes do simulador GISSIM são apresentados, bem como as modificações feitas nele para melhorá-lo.
4.1
Modelagem do Plano Semafórico
Para modelar as características dos planos semafóricos, propõe-se um conjunto
de classes Java. Oliveira e Almeida (2010) propuseram uma modelagem inicial para
problemas simples, mas agora foi necessário rever aquela implementação, de modo
que fosse possível atender os novos requisitos impostos pela abordagem mutiobjetivo
e o controle em rede. Essas classes estão implementadas no plugin GISSIM-TL e
estão ilustradas pelo diagrama da Figura 15.
4.1 Modelagem do Plano Semafórico
51
Figura 15: Diagrama de classes representando o plano semafórico de um conjunto de
interseções
Abaixo a descrição das classes utilizadas:
• NodeType: define o tipo da junção, isto é, se é um ponto de controle, cruzamento
semaforizado ou não semaforizado, prioritário. Na programação semafórica, as
junções são junções de controle semaforizadas;
• Junction: representa uma junção, e contém os atributos description (permite
escrever uma descrição), nodeType (atribui um NodeType à junção), junctionsGroup (insere esta junção à um grupo de junções);
• JunctionsGroup: é a classe que representa um grupo de junções que compartilham o mesmo ciclo. Ademais, essa classe contém uma lista de planos semafóricos, que é responsável pelas diferentes configurações de acordo com o intervalo
de tempo desejado;
• TrafficSignalPlan: é o plano semafórico, que é configurado para um determinado intervalo de tempo e, para isso, possui os atributos daysOfWeek (dias da
semana), beginTime (hora de início), endTime (hora de término), offset (defasagem) e cycle (ciclo). Com esses atributos é possível configurar diferentes ciclos
4.1 Modelagem do Plano Semafórico
52
para horários especificados pelo usuário, melhorando assim, o controle semafórico de acordo com o fluxo;
• Cycle: representa o ciclo semafórico para um determinado grupo de junções.
Para isso, contém os atributos definedTime (tempo de ciclo), minTime (tempo
mínimo de ciclo)1 , maxTime (tempo máximo de ciclo)1 e phases (lista de fases);
• Phase: representa uma fase, que é sequência de sinalização de um determinada
junção, por isso contém o atributo junctionId. Essa sequência é representada
pela lista de estágios (atributo stages);
• Stage: classe que define as características de um estágio. Contém os atributos
time (tempo), state (estado do semáforo, segundo a classe TrafficSignalState),
intergreen (tempo de entreverdes) e intergreenState (estado do entreverdes - geralmente amarelo, mas pode assumir outras cores em determinadas situações).
• TrafficSignalState: estado do semáforo, que é definido pelas cores verde (livre),
amarelo (atenção) ou vermelho (pare).
O processo de modelagem de uma região utilizando as classes descritas no diagrama é realizado em cinco etapas:
1. Escolher a região: um cenário deve ser escolhido no mapa, o qual contém trechos (ruas ou avenidas) e junções;
2. Desenhar no OpenJUMP: utilizando os dados da região escolhida, deve-se desenhar o mapa no OpenJUMP. Geralmente, as prefeituras têm os mapas georreferenciados salvos em arquivos shapefile, que podem ser carregados no SIG;
3. Configurar as junções: devem ser configuradas, depois de desenhar o mapa no
OpenJUMP, de acordo com suas características. Essa configuração indica se
uma junção é de controle ou semaforizada. A junção de controle simplesmente
conecta dois trechos, enquanto que a junção semaforizada adiciona semáforos
à essa conexão;
4. Definir os intervalos de tempo: observando as variações na demanda de fluxo,
deve-se dividir o dia e a semana em intervalos de tempo, cujos ciclos serão
configurados particularmente para aquelas condições;
1
Utilizados na programação semafórica com ciclo de tamanho variável
4.1 Modelagem do Plano Semafórico
53
5. Configurar um ciclo por intervalo de tempo: finalmente um ciclo (fases e estágios)
deve ser configurado para cada intervalo de tempo.
Para melhorar o entendimento da proposta de modelagem, esse processo será
exemplificado para um caso real da cidade de Belo Horizonte (MG). Nesse exemplo,
um cruzamento entre a Rua dos Tupinambás e a Rua dos Guaranis gera movimentos
conflitantes e, com isso, é necessário instalar/configurar semáforos para controlar o
fluxo. Os dados do plano semafórico utilizado nesse exemplo foram fornecidos pela
BHTRANS e correspondem àqueles utilizados atualmente na cidade.
4.1.1
Escolher a Região
O cruzamento escolhido aqui é entre a Rua dos Tupinambás e Rua dos Guaranis,
localizadas no hipercentro de Belo Horizonte (MG). A Figura 16 mostra o cruzamento
no Google Maps.
Figura 16: Cruzamento entre Rua dos Tupinambás e Rua dos Guaranis. Extraído de
Google Maps
4.1 Modelagem do Plano Semafórico
4.1.2
54
Desenhar no OpenJUMP
A região escolhida deve ser desenhada e configurada no OpenJUMP, para que
seja utilizada na programação semafórica e simulação. Nessa etapa deve-se utilizar as
ferramentas de edição ou carregar um arquivo shapefile (extensão .shp). O desenho
da região de exemplo feito no OpenJUMP está ilustrado na Figura 17.
Figura 17: Cruzamento desenhado no OpenJUMP
Na figura, nota-se as ruas cruzando entre si e as setas indicam o sentido das ruas.
Nesse cruzamento, existem quatro movimentos permitidos ilustrados na Figura 18.
Figura 18: Movimentos para o cruzamento
Os movimentos 1 e 2 conflitam com os movimentos 3 e 4 e, por isso, devem
ser gerenciados por semáforos. Portanto, é necessário adicionar dois semáforos ao
cruzamento, que são representados por dois pontos de controle, que foram definidos
no módulo GISSIM-TL como junções de controle semaforizadas. Na Figura 17, as
junções estão identificadas pelos números 42 e 50. Depois do desenho, é necessário
configurar as junções semaforizadas.
4.1 Modelagem do Plano Semafórico
4.1.3
55
Configurar as Junções
De acordo com os dados fornecidos pela BHTRANS pode-se visualizar a instalação dos semáforos na Figura 19.
Figura 19: Semáforos para o cruzamento (Fornecido pela BHTRANS)
Os dois semáforos (S1 e S2) estão instalados para gerenciar os dois movimentos
conflitantes. Agora é necessário configurar os semáforos, isto é, definir os intervalos
de tempo, configuração dos ciclos (número de fases, estágios), temporização, etc.
Para configurar os semáforos, projetou-se uma tela no GISSIM-TL, que mostra a área
de simulação destacando as junções de controle em pequenos quadrados (Figura
20). Ao clicar em uma das junções, a tela para configurar junções de controle é exibida
(Figura 21). As junções desse tipo podem ser de controle ou semaforizadas. Ademais,
o grupo semafórico deve ser configurado na mesma tela.
Figura 20: Tela do GISSIM-TL - Painel com a Área de Simulação
4.1 Modelagem do Plano Semafórico
56
Figura 21: Tela do GISSIM-TL - Configurar Junção de Controle
4.1.4
Definir os Intervalos de Tempo
A programação semafórica de tempo fixo é feita de acordo com os intervalos de
tempo divididos durante a semana. Nesse exemplo, a divisão dos intervalos de tempo
é dada na Tabela 1. Cada intervalo de tempo deve ser ligado a uma configuração
de ciclo. Por isso, é possível configurar vários ciclos de acordo com as diferentes
demandas utilizando os intervalos de tempo.
Tabela 1: Divisão dos intervalos de tempo (Fornecido pela BHTRANS)
ID Dia Hora de Início Hora de Término
1 2-6
00:01
05:30
2 2-6
05:31
06:30
06:31
09:20
3 2-6
09:21
11:00
4 2-6
5 2-6
11:01
12:40
6 2-6
12:41
14:30
7 2-6
14:31
17:00
8 2-6
17:01
20:30
9 2-6
20:31
00:00
00:01
05:30
10 1-7
11
1
05:31
00:00
12
7
05:31
00:00
Na tabela é possível visualizar quatro colunas: ID, Dia, Hora de Início e Hora de
Término. Na coluna dia deve-se configurar o dia da semana: domingo (1), segunda
(2), terça (3), quarta (4), quinta (5), sexta (6), sábado (7), ou ainda, uma sequência
de dias. A hora de início e hora de término indicam ao simulador quando um plano
semafórico inicia e termina.
Uma tela chamada “Configurar Plano Semafórico por Grupo” foi implementada
no GISSIM-TL para configurar planos semafóricos em diferentes intervalos de tempo
4.1 Modelagem do Plano Semafórico
57
(Figura 22).
Figura 22: Tela do GISSIM-TL - Configurar Plano Semafórico por Grupo
4.1.5
Configurar os Ciclos por Intervalo de Tempo
Para exemplificar a configuração do cruzamento descrito anteriormente, foi adotado o intervalo de tempo com ID igual a 8 e um plano semafórico deve ser configurado. Esse intervalo corresponde aos horários de pico durante a semana e está
destacado em negrito na Tabela 1, isto é, de segunda a sexta de 17:00 às 20:30.
De acordo com os dados fornecidos pela BHTRANS, o diagrama de tempos do plano
semafórico utilizado nesse intervalo está ilustrado na Figura 23.
Figura 23: Diagrama de tempos no intervalo de tempo (ID = 8) para o cruzamento
(Fornecido pela BHTRANS)
4.1 Modelagem do Plano Semafórico
58
No diagrama de tempos pode ser visto que o cruzamento de dois semáforos possui duas fases, com dois estágios cada. O primeiro estágio é de 72 segundos e o
entreverdes é igual a 3 segundos, o segundo estágio é de 42 segundos e o entreverdes é igual a 3 segundos. Para configurar o ciclo também foi necessário criar uma tela
no GISSIM-TL (Figura 24).
Figura 24: Tela do GISSIM-TL - Configurar Ciclo
Nessa tela é possível configurar o número de fases, o número de estágios, o tempo
de ciclo, tempo de defasagem e definir, de maneira bem interativa, a disposição de
fases e estágios, bem como, seus estados e tempos. Portanto, pode-se ver que o
GISSIM-TL ficou mais interativo desde o início do processo de modelagem até a última
etapa.
4.1.6
Resultado da Modelagem
As configurações devem ser feitas para todos os intervalos de tempo de cada
grupo de junções. Embora não seja viável demonstrar as configurações de todas as
junções neste trabalho, a configuração do cruzamento da Figura 16, utilizada como
exemplo, embora simples, é suficiente para entender o processo de modelagem. Por
fim, o diagrama de objetos dado na Figura 25 exibe o estado de execução após a
modelagem.
O diagrama de objetos mostra a configuração do cruzamento que possui as junções de controle semaforizadas junction42 e junction50. Essas duas junções per-
4.1 Modelagem do Plano Semafórico
59
Figura 25: Diagrama de objetos representando o plano semafórico do cruzamento
tencem ao grupo de junções 10. A partir daí, vários planos semafóricos podem ser
configurados para o grupo, de acordo com os intervalos de tempo definidos para a
região.
Quaisquer regiões podem ser configuradas utilizando o exemplo acima, já que
elas se modificam entre si apenas em relação ao número de junções ou número de
intervalos de tempo, o que é facilmente estendido, caso seja necessário.
4.2 Algoritmo de Otimização Semafórica
4.2
60
Algoritmo de Otimização Semafórica
A otimização semafórica é realizada por um algoritmo evolucionário multiobjetivo.
Para tanto, foi necessário construir um framework de otimização, cujo objetivo é prover
um conjunto de classes que auxiliam o uso de técnicas para solução de problemas de
otimização em geral. Com isso, é possível estender as classes para implementar o
problema de programação semafórica, já que este tem suas particularidades.
4.2.1
Descrição do problema
Um problema de otimização é constituído de duas partes principais: variáveis de
otimização e funções de avaliação. As variáveis representam os valores que são otimizados ao longo do tempo e, após cada modificação, é necessário calcular a “qualidade” da solução utilizando as funções de avaliação.
4.2.1.1
Variáveis de decisão
Foi necessário avaliar qual variável seria utilizada no processo de otimização. Nas
primeiras abordagens, adotou-se os tempos de verde dos semáforos e, foi obtido bom
desempenho em casos de teste simples, cujas interseções não tinham mais de dois
semáforos cada. No entanto, realizando estudos em regiões mais complexas, alguns
problemas foram encontrados. Por exemplo, a Figura 26 exemplifica a configuração
do ciclo de uma interseção com oito semáforos.
Figura 26: Exemplo de configuração do ciclo em uma interseção com oito semáforos
Nesse caso, se os tempos de verde dos semáforos fossem utilizados como variável de otimização, a solução otimizaria 14 variáveis (número de tempos de verde nos
estágios 1, 2 e 3). Nessa configuração seria impossível que dois tempos de verde
4.2 Algoritmo de Otimização Semafórica
61
do mesmo estágio (por exemplo, o estágio 1 da fase 1 e 2) fossem modificados com
valores diferentes, pois o estágio é uniforme para todas as fases. Como o fator citado
acima é predominante em muitas regiões, foi preciso modificar a modelagem. Para
não modificar muito a representação, que havia apresentado bons resultados anteriormente, definiu-se que a variável de otimização é o tempo do estágio. Com isso, é
possível obter o mesmo comportamento para interseções de dois semáforos e resolver
o problema citado em interseções mais complexas.
Como visto no Capítulo 2, a programação semafórica de uma rede é feita com
um tempo de ciclo único para todas as interseções. Portanto, foi necessário considerar isso ao representar uma solução. Já que o tempo de ciclo corresponde a soma
dos tempos de todos estágios e os tempos de entreverdes, ao modificar os valores
de todos os estágios do ciclo, inevitavelmente, o tempo total seria diferente do tempo
de ciclo configurado. Como isso não é desejável, adotou-se que o número de variáveis para cada ciclo seria o número de estágios menos um. O último estágio seria o
complemento de tempo necessário para completar o ciclo.
Enfim, pode-se dizer que para cada interseção com n estágios, o número de variáveis é n − 1. Consequentemente, para uma rede com várias interseções, o número
de variáveis é a soma do número de variáveis de todas as interseções, constituindo a
solução que é otimizada.
4.2.1.2
Representação da solução
Os indivíduos da população foram codificados usando representação binária com
precisão de 10 bits para cada variável. No diagrama da Figura 26, nota-se que aquele
ciclo possui três estágios. Portanto, o número de variáveis é igual a dois. Um exemplo
de solução para aquela interseção é dado na Figura 27.
Figura 27: Representação da solução para o ciclo de três estágios
Os índices representam a precisão e as variáveis foram distintas pelos números
1 e 2. Este vetor simboliza características genéticas (genótipo) e a combinação dos
elementos do vetor simboliza as características reais (fenótipo) do indivíduo. Portanto,
4.2 Algoritmo de Otimização Semafórica
62
dada uma cadeia binária é possível convertê-la para um valor decimal que representa
os tempos de estágio do ciclo. Essa conversão é feita pelo método de normalização
da Equação (4.1),
vnorm = (vbin ∗ (dmax − dmin )/(2p − 1)) + dmin ,
(4.1)
onde:
vnorm é o valor normalizado;
vbin é o valor binário decodificado;
dmin é o valor mínimo do domínio;
dmax é o valor máximo do domínio; e
p é a precisão.
O método de normalização decodifica a variável binária entre os limites de domínio. Por exemplo, considerando o estágio com tempo mínimo de 30 segundos e
máximo de 90 segundos, na Figura 27 o resultado das conversões normalizadas para
a primeira variável é 46 segundos, e para a segunda variável é 77 segundos.
4.2.1.3
Funções de avaliação
O método de avaliação do algoritmo usa o simulador GISSIM. Primeiro os valores
das variáveis são atribuídos aos semáforos da área simulada e a simulação é executada para coletar resultados, que correspondem aos valores das funções objetivo dos
indivíduos. Diferentes funções poderiam ser adotadas para qualificar uma solução, alguns exemplos foram dados na Seção 2.4. Algumas delas foram testadas, mas existe
uma dificuldade grande para encontrar funções que não sejam correlacionadas nesse
problema.
Depois de testar algumas combinações de funções, tal como maximizar o número
de veículos deixando a rede e minimizar o tempo de trânsito (COSTA; ALMEIDA; CALDEIRA,
2011), definiu-se uma combinação que alcançou os melhores resultados em
experimentos:
FX1 → maximizar fvm (x∗ ): velocidade média dos veículos;
4.2 Algoritmo de Otimização Semafórica
63
FX2 → minimizar fvv (x∗ ): variância da velocidade média dos veículos.
A primeira função está relacionada a uma melhora no fluxo, isto é, maximizando a
velocidade dos veículos na rede pretende-se fazer com que mais veículos trafeguem
pela rede durante um intervalo de tempo. Em contrapartida, a segunda função deseja
minimizar a variação da velocidade média dos veículos, trazendo uma uniformidade
da velocidade em todos os trechos, que por sua vez, contribui para equilibrar a rede.
4.2.2 Framework de Otimização
O framework foi desenvolvido neste trabalho para fornecer um conjunto de classes
para implementação de problemas de otimização. O foco é utilizá-lo em problemas
multiobjetivo, aproveitando as características de reutilização de código do paradigma
de programação orientada a objetos. Com isso, a implementação de novos problemas,
novas técnicas ou operadores, é facilitada. O nome escolhido para o framework é
Java Framework for Evolutionary Multiobjective Optimization (JFEMO). Sua estrutura
é ilustrada na Figura 28.
Primeiramente, deve-se definir o problema de otimização. Isso é feito utilizando
a classe Problem, que possui alguns atributos como title (título do problema), comments (comentários), numberOfVariables (número de variáveis), lowerBounds (limites
inferiores do conjunto de variáveis) e upperBounds (limites superiores do conjunto de
variáveis). Depois de definir esses atributos, deve-se implementar as funções objetivo
do problema. Ele deve ter uma ou mais funções, que são de minimização ou maximização, de acordo com sua proposta. Cada nova classe de função deve estender a
classe abstrata Function, que, por sua vez, possui o método evaluate(individual: Individual): double que deve ser escrito. Esse método retorna o cálculo da função objetivo
para o indivíduo de entrada.
Depois de definir o problema, juntamente com suas funções, deve-se implementar
a técnica de otimização. Para isso, a técnica criada deve primeiramente estender a
classe Algorithm que possui o atributo name (nome da técnica). Na classe da nova
técnica, o método build() realiza a construção dos objetos de acordo com os parâmetros passados. O método run() deve ser escrito, pois ele é responsável pela execução
do algoritmo implementado. Do mesmo modo, deve-se implementar uma classe de
parâmetros específicos para a técnica. Para tanto, deve-se herdar a classe Parameters, que possui os atributos precision (número de bits por indivíduo), populationSize
4.2 Algoritmo de Otimização Semafórica
64
Figura 28: Diagrama de classes do JFEMO
(tamanho da população), generations (número de gerações), variableType (tipo de variável binária ou real). Na classe de parâmetros deve-se incluir atributos e métodos
específicos da técnica desejada.
Por fim, os operadores genéticos de seleção, cruzamento e mutação devem ser
criados. É possível implementar vários operadores diferentes e usá-los de acordo
com a necessidade. Com isso, é possível comparar a eficiência de cada operador e
escolher aquele que se comporta melhor para o problema estudado. O operador de
seleção deve estender a classe Selection, o operador de cruzamento deve estender
a classe Crossover, que possui o atributo rate (taxa de cruzamento), enquanto que o
operador de mutação deve estender a classe Mutation, que também possui o atributo
rate (taxa de mutação). Todos os operadores possuem o método run() que executa
4.2 Algoritmo de Otimização Semafórica
65
o operador e, por isso, ele deve ser escrito na classe estendida de acordo com as
características do operador implementado.
Essas três etapas devem ser cumpridas para utilizar o framework JFEMO. Contudo, depois de realizar a primeira implementação, pode-se criar quaisquer entidades
separadamente. Por exemplo, depois de criar o algoritmo NSGA 2 para solucionar
um problema de otimização utilizando cruzamento uniforme e mutação por troca, é
possível implementar o algoritmo SPEA 2 para solucionar o mesmo problema aproveitando os operadores que tinham sido criados. Essa é a principal característica do
framework.
4.2.3
Algoritmo MBVL-NSGA2
O algoritmo Memory-Based Variable-Length Encoding Non-Dominated Sorting Genetic Algorithm 2 (MBVL-NSGA2), basicamente, segue a mesma estrutura do algoritmo NSGA 2 descrito na subseção anterior. No entanto, ele possui algumas características diferentes: uso de memória, processo de avaliação e operadores genéticos
adaptativos. O fluxo geral do algoritmo MBVL-NSGA2 é dado na Figura 29.
O algoritmo inicialmente gera um conjunto de soluções e faz a simulação delas
utilizando o simulador GISSIM, que retorna o conjunto de soluções avaliados. Depois
disso, o algoritmo entra em um loop, que realiza as seguintes operações: classifica as
soluções segundo suas fronteiras e valores de crowding distance, faz a seleção das
melhores soluções para serem os pais da próxima geração, aplica os operadores de
cruzamento e mutação para gerar os filhos, que, por sua vez, são avaliados utilizando
o simulador. Esse processo é repetido até que o critério de parada seja satisfeito.
4.2.3.1
População Inicial
A população inicial, em princípio, foi gerada aleatoriamente, mas os resultados não
foram satisfatórios. Isso, porque, ao gerar soluções completamente aleatórias, muitos
indivíduos de baixa qualidade eram criados deixando a máquina de simulação muito
lenta ao simulador o trânsito. Esse fator elevou o custo computacional de avaliação
dos indivíduos, tornando a proposta impraticável.
Com o objetivo de melhorar as primeiras soluções, decidiu-se usar as configurações da BHTRANS para gerar a população inicial. Com isso, o algoritmo parte de
4.2 Algoritmo de Otimização Semafórica
66
Figura 29: Fluxo do algoritmo MBVL-NSGA2
soluções baseadas em planos semafóricos existentes e, a partir de tais dados, realiza
o processo de otimização. Portanto, essa solução foi adotada e todos os indivíduos
da população inicial têm sido gerados com a configuração atual da BHTRANS.
4.2.3.2
Memória
O algoritmo utiliza uma memória para armazenar as soluções visitadas durante a
sua execução. A memória é uma tabela hash como descrita na Seção 3.4.1. Para
tanto, foi criada a classe Memory, que representa a tabela e contém suas operações,
tais como adicionar, remover, alterar e consultar. Na classe Memory, como em toda
tabela, foi necessário definir a chave e o conteúdo de cada slot. Neste trabalho, a
chave é gerada pelo hash de Pearson a partir da cadeira binária do indivíduo e o
conteúdo da tabela são os valores das funções de avaliação.
4.2 Algoritmo de Otimização Semafórica
4.2.3.3
67
Avaliação de Soluções
Um novo processo de avaliação é proposto nesse algoritmo, utilizando os conceitos de memória abordado anteriormente. Nesse contexto, quando uma solução
requisita uma avaliação, primeiramente verifica-se se ela já foi avaliada anteriormente.
Se a solução ainda não foi avaliada, o operador a avalia, armazena o resultado em
memória e retorna a avaliação. Caso ela já tenha sido avaliada, o operador gera uma
nova solução ainda não visitada próxima à solução já visitada, depois avalia a nova
solução, armazena em memória e retorna o valor da função. O Algoritmo 5 detalha
esse esquema.
Algoritmo 5 Pseudo-código do processo de avaliação. Adaptado de Carrano, Moreira
e Takahashi (2011)
1: entrada ind; // Indivíduo que é avaliado
2: avaliado = f alse;
3: enquanto (avaliado == f alse) faça
4:
visitado = RECU P ERA(ind); // Verifica se já foi avaliado
5:
se (visitado == f alse) então
6:
f = AV ALIA(ind); // Avalia indivíduo
7:
ARM AZEN A(ind, f ); // Armazenar avaliação na memória
8:
avaliado = true;
9:
senão
10:
Svar = ∅; // Variáveis que podem ser mutadas
11:
para i = 1, .., n faça
12:
se (ind.dep(i) < nbits ) então
13:
Svar = Svar ∪ i // Adiciona variável i ao conjunto Svar
14:
fim se
15:
fim para
16:
se (Svar 6= 0)) então
17:
v = RAN DOM (Svar ); // Sorteia variável v que será mutada
18:
ind.dep(v) = ind.dep(v) + 1;
19:
ind.bin(ind.dep(v)) = ind.bin(ind.dep(v)); // Muta bit ind.dep(v) da variável i
20:
senão
21:
ind = N OV OIN D; // Gera indivíduo aleatório
22:
fim se
23:
fim se
24: fim enquanto
25: saída ind;
4.2.3.4
Operadores Genéticos
Os três operadores genéticos são utilizados: seleção, cruzamento e mutação.
Existe um número variado de implementações desses operadores na literatura, e al-
4.2 Algoritmo de Otimização Semafórica
68
guns deles foram testados para o problema. Os operadores de cruzamento e mutação
desse algoritmo são adaptativos, baseando-se em um atributo de profundidade das
variáveis dos indivíduos. Os operadores que obtiveram melhores resultados estão
descritos abaixo.
Seleção: os pais são selecionados usando seleção por torneio binário, em que as
soluções são escolhidas pelo operador Crowded Comparison (DEB et al., 2002);
Cruzamento: é baseado no cruzamento de ponto único por variável. Entretanto,
a diferença é que os bits cruzados da variávei i são aqueles menores que ind.dep(i),
ou seja, entre dois pais, o operador sorteia um ponto de corte entre 1, .., ind.dep(i) e
realiza o cruzamento. O Algoritmo 6 detalha esse esquema.
Algoritmo 6 Pseudo-código do operador de cruzamento adaptativo. Adaptado de
Carrano, Moreira e Takahashi (2011)
1: entrada inda , indb ;
2: indc = inda ;
3: indd = indb ;
4: para i = 1, .., n faça
5:
indc .dep(i) = min(inda .dep(i), indb );
6:
pc = RAN DOM ({1, .., indc .dep(i)});
7:
indc (i; {1, .., pc }) = indb (i; {1, .., pc });
8:
indd .dep(i) = max(inda .dep(i), indb .dep(i));
9:
pd = RAN DOM ({1, .., indd .dep(i)});
10:
indd (i; {1, .., pd }) = inda (i; {1, .., pd });
11: fim para
12: saída indc , indd ;
Mutação: é baseado na mutação por inversão. A única diferença é que os únicos
bits modificados em uma variável i são aqueles menores que ind.dep(i). O operador
é dado no Algoritmo 7.
Algoritmo 7 Pseudo-código do operador de mutação adaptativo. Adaptado de Carrano, Moreira e Takahashi (2011)
1: entrada indb ;
2: inda = indb ;
3: va = RAN DOM ({1, .., n});
4: pa = RAN DOM ({1, .., inda .dep(i)});
5: inda (va , pa ) = inda (va , pa );
6: saída inda ;
4.3 Simulador GISSIM
4.2.3.5
69
Nova população
Para compor a nova população para a próxima geração é necessário mesclar população pai e filha, logo depois, ordenar indivíduos usando operador de comparação
crowded e selecionar N melhores indivíduos, onde N representa o tamanho da população.
4.2.4
Diagrama de Classes
Depois de definir o problema, configurar o algoritmo MBVL-NSGA2, chegou-se ao
diagrama de classes dado na Figura 30.
No diagrama, as propriedades do framework JFEMO foram herdadas para implementar as novas propostas. Para configurar o problema de programação semafórica
foi necessário criar a classe TrafficSignalTimingProblem e suas duas funções AverageSpeed e SpeedVariance. Além disso, os operadores genéticos foram implementados: BinaryTournamentSelection, AdaptiveCrossover e AdaptiveMutation. Depois o
MBVL_NSGA2Algorithm foi implementado.
4.3
Simulador GISSIM
A ferramenta GISSIM desenvolvida por Neto e Almeida (2009) é 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 e das limitações de processamento dos computadores atuais, a área de simulação deve ser restrita a uma pequena região de estudo.
4.3.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 rede viária seleci-
4.3 Simulador GISSIM
70
Figura 30: Diagrama de classes
onada quais são os pontos de entrada/saída de veículos (SourceSinkJunction) e os
cruzamentos. 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;
4.3 Simulador GISSIM
71
• 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 rede viária.
4.3.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 (NETO;
ALMEIDA,
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 é que, o objeto responsável por desenhar os componentes do sistema é totalmente desacoplado da máquina de simulação. Foi aplicada 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.3.3
Máquina de simulação
Segundo Neto e Almeida (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. 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.
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
4.3 Simulador GISSIM
72
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 trabalho, 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 (NETO; ALMEIDA, 2009).
4.3.4
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 (NETO; ALMEIDA, 2009).
4.3.5
Modificações no simulador
A modelagem proposta por Neto e Almeida (2009) e, logo depois, refatorada por
Oliveira e Almeida (2010), possui limitações na representação de algumas situações
reais. Dentre os problemas levantados, alguns merecem ser destacados: problema
na modelagem dos trechos de mão dupla, não contemplação de trechos com número
de faixas diferentes, não atribuição dos movimentos permitidos para cada trecho, semáforos não podendo ser localizados no meio de um trecho, dentre outros.
Com o objetivo de melhorar o simulador GISSIM e torná-lo cada vez mais realístico, esses problemas foram sanados seguindo diretrizes da engenharia de tráfego. As
soluções para os problemas são detalhadas nas subseções abaixo.
4.3.5.1
Trechos de mão dupla
Para representar um trecho de mão dupla, Neto e Almeida (2009) utilizaram um
atributo chamado “MAODUPLA”, que poderia assumir os valores “S” ou “N” (sim ou
não). Quando esse atributo era “S”, o simulador automaticamente criava um trecho de
ida e um de volta. Embora essa abordagem funcione e possa ser utilizada em alguns
casos, ela possui um problema. É impossível instalar um semáforo para controlar o
4.3 Simulador GISSIM
73
movimento no trecho de interseção, quando cruza-se um trecho de mão dupla com
outro trecho qualquer. Esse problema pode ser observado na Figura 31.
Figura 31: Cruzamento em trecho de mão dupla. Adaptado de Google Maps
Na figura, nota-se que a Av. Tereza Cristina é uma avenida de mão dupla e os
trechos são separados por um rio. Devido a essa separação, onde há um cruzamento
com a Rua Bom Sucesso torna-se um novo trecho, que, mesmo sendo curto, traz
consigo a necessidade de um semáforo para controlar o movimento. Nesse caso, o
semáforo da Rua Bom Sucesso está identificado no quadrado.
Na modelagem proposta por Neto e Almeida (2009), a Av. Tereza Cristina e a Rua
Bom Sucesso seriam representadas por uma reta cada e, para controlar as características do trecho de mão dupla, seria necessário utilizar o atributo “MAODUPLA”.
Entretanto, seria impossível adicionar um semáforo àquele trecho.
Agora propõe-se que todos os trechos de mão dupla do simulador sejam desenhados com duas retas. Então, para o exemplo dado, uma reta deve ser desenhada representando a Rua Bom Sucesso e duas retas devem ser desenhadas representando
a Av. Tereza Cristina. A comparação entre a antiga abordagem e a nova proposta
pode ser vista na Figura 32.
Por conseguinte, o atributo “MAODUPLA” foi removido e o simulador reconhece
um trecho de mão dupla pelo desenho.
4.3 Simulador GISSIM
74
Figura 32: Comparação dos desenhos do trecho de mão dupla
4.3.5.2
Movimentos permitidos por trecho
Em uma rede de tráfego, os trechos devem conter informações sobre os próximos
trechos em que os veículos poderão convergir. Essa é uma característica importante
e deve ser tratada pelo simulador. Ademais, a modelagem dos trechos de mão dupla,
explicada na subseção anterior, agrava essa necessidade. A Figura 33 exemplifica
isso.
Figura 33: Exemplo de trechos com movimentos permitidos e proibidos. Adaptado de
Google Maps
Nesse exemplo, tem-se o cruzamento entre a Av. Afonso Pena, a Rua Espírito
Santo e a Rua dos Tamoios. O movimento permitido está destacado na cor verde,
enquanto os movimentos proibidos estão destacados na cor vermelha. Portanto, é necessário restringir os movimentos dos veículos para que realizem somente movimentos permitidos. Para implementar essa característica, um atributo chamado “NEXTRO-
4.3 Simulador GISSIM
75
ADS” foi adicionado à camada do mapa no OpenJUMP e é utilizado para armazenar
quais os trechos permitidos para conversão a partir do trecho atual. Esse atributo é
utilizado na criação das áreas de simulação. Para configurá-lo, deve-se usar uma tela
que foi criada, em que um exemplo de configuração é ilustrado na Figura 34.
Figura 34: Tela de configuração dos movimentos permitidos
Na estrutura interna do simulador, foi necessário modificar a classe FeatureRoad,
que está no pacote br.cefetmg.lsi.gissim.simulation.network. Essa classe representa
um trecho (de uma junção de origem à outra junção de destino) e possui características de um trecho, tais como id, nome, número de faixas, comprimento, etc. Nessa
classe, uma lista chamada nextRoads foi adicionada e tem a mesma função do atributo
“NEXTROADS” descrito anteriormente.
4.3.5.3
Modelagem multifaixas
Os trechos com duas ou mais faixas estão presentes na totalidade dos municípios
brasileiros. Sendo assim, é fundamental incluir essas características na modelagem
do simulador. Mas até então, o simulador GISSIM possuía um problema muito grave,
ele fazia simulações somente quando o número de faixas era igual em todos os trechos
da área simulada. Caso essa premissa não fosse obedecida, a máquina de simulação
retornava um erro ao usuário.
Em alguns casos particulares, seria possível utilizar essa modelagem simples. No
entanto, para expandir a aplicação do simulador, tornou-se necessário implementar
a multiplicidade de faixas e as interações decorrentes dela, como, por exemplo, as
mudanças de faixas, as conversões etc.
Primeiramente, a interação com o usuário não sofreu nenhuma modificação, já que
o atributo que define o número de faixas por trecho já tinha sido definido anteriormente.
4.3 Simulador GISSIM
76
Contudo, era necessário modificar o funcionamento da máquina de simulação para
trabalhar corretamente com números diferentes de faixas nos trechos, pois alguns
erros eram retornados no desenho da interface gráfica de simulação.
A máquina de simulação possuía características suficientes para representar os
trechos de múltiplas faixas, mas foi necessário alterar algumas classes que possuía
problemas no desenho da interface gráfica. Essas alterações foram feitas, sobretudo,
nas classes do pacote br.cefetmg.lsi.gissim.simulation.network.
Para mostrar a criação da área de simulação com número de faixas diferentes em
vários trechos, foi criada uma pequena região de exemplo, que pode ser observada
na Figura 35.
Figura 35: Exemplo de uma microrregião desenhada no OpenJUMP
Quando a área de simulação é criada para essa região, o simulador cria a interface
gráfica de simulação utilizando os atributos oriundos do OpenJUMP. A Figura 36 ilustra
a interface gráfica criada para a região de exemplo. Nela, observa-se que a avenida
principal de mão dupla possui três faixas em cada mão, enquanto as outras ruas que
a cruzam possuem uma e duas faixas, respectivamente.
4.3.5.4
Mudança de faixas
Após a implementação do modelo multifaixas no simulador GISSIM, tornou-se fundamental atribuir aos veículos o comportamento de mudança de faixas. Esse tipo de
comportamento é bem conhecido na área de simulação de tráfego e tem sido estudado
em vários trabalhos da literatura. Nesse contexto, foi necessário fazer uma pesquisa
sobre os principais modelos existentes e qual seria aplicável ao simulador GISSIM.
4.3 Simulador GISSIM
77
Figura 36: Região de exemplo desenhada na interface gráfica de simulação
Durante as pesquisas realizadas, o trabalho de Gipps (1986) mostrou-se eficiente
em simuladores semelhantes e é adotado aqui como base na implementação do modelo de mudança de faixas. Posto que Casas et al. (2010) descreveram aquele modelo
e a maneira como foi aplicado ao simulador AIMSUN de um modo simples e bem eficiente, este último é utilizado como referência nesse estudo.
No simulador GISSIM, durante o trajeto percorrido por um veículo na simulação, a
posição dele era atualizada de acordo com o modelo Car Following. No entanto, com
a necessidade da mudança de faixas, agora essa atualização será feita utilizando os
modelos Car Following e Lane Changing. Eles fornecem diretrizes dos movimentos
de veículos utilizando formulações matemáticas que modelam o comportamento de
acordo com o ambiente em que eles estão, como, por exemplo, observando detalhes
dos veículos próximos, de semáforos, de placas de sinalização, etc.
Para aplicar os dois modelos, é necessário dividir o tempo total de simulação em
pequenos intervalos de tempo, chamados de etapas de simulação. Depois, em cada
etapa, cada veículo é atualizado utilizando o procedimento de movimento veicular (Algoritmo 8). Neste algoritmo, observa-se que em uma etapa, o veículo pode mudar de
faixas, dependendo de sua necessidade, ou seguir em frente, observando os obstáculos. Além disso, nota-se que os dois modelos nunca são executados em conjunto em
uma mesma etapa de simulação.
Como o modelo Car Following já foi definido por Neto e Almeida (2009), agora é
necessário definir o modelo Lane Changing, observando os aspectos propostos por
Casas et al. (2010). Esse processo foi modelado como uma tomada de decisão, que
analisa três aspectos:
4.3 Simulador GISSIM
78
Algoritmo 8 Pseudo-código do movimento veicular. Adaptado de Casas et al. (2010)
enquanto não termina simulação faça
para cada veículo faça
se (realiza mudança de faixa) então
Aplica modelo Lane Changing
senão
Aplica modelo Car Following
fim se
fim para
fim enquanto
1. Necessidade de mudar de faixa, como, por exemplo, para realizar futuras conversões à esquerda ou à direita;
2. Benefícios da mudança de faixa para melhorar a velocidade atual do veículo;
3. Viabilidade para mudar de faixa, observando a posição do veículo na rede e o
ambiente ao seu redor.
Baseado nesses três aspectos, o modelo está simplificado no Algoritmo 9. A mudança de faixas será realizada somente quando for necessário (condição 1) e possível
(condição 3). No entanto, caso essa primeira sentença não seja satisfeita, a mudança
será realizada caso seja benéfica (condição 2) e possível (condição 3).
Algoritmo 9 Pseudo-código do modelo Lane Changing. Adaptado de Casas et al.
(2010)
se (é necessário mudar de faixa e viabilidade é satisfeita) então
Aplica mudança de faixa por necessidade
senão se (é benéfico mudar de faixa e viabilidade é satisfeita) então
Aplica mudança de faixa por benefício
fim se
Para conseguir uma representação mais precisa do comportamento dos motoristas no processo de decisão para mudança de faixas, três diferentes zonas são definidas por trecho. Cada uma dessas zonas correspondem a uma motivação diferente.
Essas zonas são caracterizadas pela distância até o fim do trecho. Isso é ilustrado na
Figura 37.
Para verificar a necessidade de mudar de faixa, inicialmente, verifica-se se o veículo está na zona 2 ou 3. Depois disso, verifica-se qual a direção da próxima conversão: adiante, à esquerda ou à direita. Se o veículo seguir adiante na próxima junção,
é necessário mudar de faixa caso o número da faixa atual for maior que o número de
4.3 Simulador GISSIM
79
Figura 37: Zonas do modelo Lane Changing. Adaptado de Casas et al. (2010)
faixas do próximo trecho. Entretanto, se a conversão for à esquerda ou à direita, o
veículo deve mudar de faixa para realizar a conversão.
Enquanto isso, para verificar o benefício de mudar de faixa, inicialmente, verificase se o veículo está na zona 1 ou 2. Em seguida, o benefício é constatado comparando
a situação atual com as faixas à esquerda e à direita. Caso a velocidade atual seja
menor que a velocidade média de alguma das faixas ao lado, o benefício é constatado
e o veículo deve mudar de faixa.
Para verificar se é possível realizar a mudança de faixa utiliza-se o procedimento
descrito no Algoritmo 10.
Algoritmo 10 Pseudo-código da viabilidade de mudança de faixa. Adaptado de Casas
et al. (2010)
1: distância = distância entre o início da faixa de origem e a posição atual + distância
percorrida na velocidade atual
2: adiciona temporariamente o veículo na faixa de destino na distância calculada
3: para (cada veículo v na faixa de destino) faça
4:
distância do veículo v = distância entre o início da faixa de destino e a posição
de v + distância percorrida do veículo v na velocidade atual
5:
se (distância do veículo v não obedecer distância de segurança) então
6:
retorna false;
7:
fim se
8: fim para
9: retorna true;
Esse procedimento verifica se é possível mudar de faixa, observando se os veículos da faixa de destino obedecem à distância de segurança. Sendo assim, depois
de verificar a necessidade ou o benefício da mudança de faixas e, a viabilidade comprovada, pode-se realizar a mudança. Para isso, utiliza-se o procedimento descrito no
Algoritmo 11.
O procedimento realiza a mudança, adicionando o veículo na faixa de destino, na
mesma posição calculada.
4.3 Simulador GISSIM
80
Algoritmo 11 Pseudo-código da mudança de faixa. Adaptado de Casas et al. (2010)
1: distância = distância entre o início da faixa e a posição atual
2: próxima distância = distância + distância percorrida na velocidade atual
3: adiciona veículo na próxima faixa na distância calculada
4.3.5.5
Conversões
Nesse momento do trabalho, a mudança de faixas era feita observando somente o
trecho atual que o veículo está percorrendo, ou seja, até a próxima conversão. Entretanto, essa abordagem não é segura em trechos curtos ou de tráfego pesado, já que,
os veículos podem não conseguir realizar a mudança de faixa desejada e, com isso,
perder a próxima conversão.
A solução desse problema foi criar uma estrutura de dados que possibilite o veículo
conhecer previamente um conjunto de suas próximas conversões. Sendo assim, o
veículo pode fazer a mudança de faixa em tempo de convergir com sucesso.
Para implementar essa característica, foi necessário modificar a classe Vehicle,
localizada no pacote br.cefetmg.lsi.gissim.simulation.vehicle. Essa classe representa
a entidade veículo e, por isso, contém as características de um veículo, como, por
exemplo, id, velocidade máxima, comprimento, largura, cor, aceleração, etc. Nessa
classe, uma lista chamada route foi adicionada e contém os três próximos trechos em
que o veículo percorrerá.
Portanto, quando um veículo entra na simulação, define-se aleatoriamente os três
próximos trechos que ele vai percorrer, como na Figura 38. Entretanto, como o simulador é estocástico, não se sabe todo o trajeto que o veículo percorrerá no total e, por
isso, a dúvida sobre quais outros trechos serão escolhidos.
Figura 38: Lista dos próximos trechos a percorrer quando o veículo entra na rede
Depois disso, a cada nova conversão, o primeiro trecho da lista é excluído (último
4.3 Simulador GISSIM
81
trecho percorrido) e um novo trecho é selecionado e adicionado à lista. Essa seleção é feita baseada em na matriz origem-destino (OD). A Figura 39 exemplifica esse
processo.
Figura 39: Novo trecho selecionado pela matriz OD é adicionado à lista
Essa abordagem solucionou o problema e, com isso, os veículos têm um conhecimento prévio dos próximos trechos a percorrer, possibilitando a mudança de faixas
para realizar a conversão corretamente.
4.3.5.6
Pontos de controle
Geralmente, semáforos são instalados no fim dos trechos, pertecendo assim, a um
determinado cruzamento. Entretanto, em alguns casos encontrados no mundo real,
os semáforos são instalados em diferentes posições. A Figura 40 mostra um exemplo
extraído da cidade de Belo Horizonte, em que a Praça Sete de Setembro, cruzamento
entre a Av. Amazonas e a Av. Afonso Pena, possui um semáforo instalado no início do
trecho da Av. Afonso Pena (destacado pelo quadrado).
Nas condições encontradas no simulador GISSIM, quando uma junção era definida
do tipo cruzamento semaforizado, os semáforos eram configurados automaticamente
no fim dos trechos que se cruzavam. Sendo assim, não seria possível configurar
um semáforo no início ou meio de um trecho. Por isso, foi necessário implementar a
configuração dos semáforos de um modo diferente.
Utilizando a estrutura existente no simulador, foi definido que todo semáforo será
configurado como um ponto de controle, ou seja, quando deseja-se configurar um
semáforo em algum ponto do trecho, deve-se adicionar um ponto de controle, que, por
sua vez, deve ser configurado como semaforizado. Consequentemente, o conjunto
de semáforos pertencentes ao mesmo ciclo devem ser configurados no mesmo grupo
4.3 Simulador GISSIM
82
Figura 40: Exemplo de cruzamento com semáforo no início de um trecho. Adaptado
de Google Maps
semafórico.
Figura 41: Semáforo configurado como ponto de controle semaforizado
Na Figura 41, nota-se que foram adicionados pontos de controle na localização
dos semáforos. Depois de adicionar os pontos de controle, é necessário definir o
tipo da junção: controle ou semaforizado. Para exemplificar, será usado o semáforo
citado no exemplo anterior, que está destacado no quadrado vermelho. Por fim, basta
configurar o ponto de controle como semaforizado e ele será usado como semáforo
na simulação.
4.3 Simulador GISSIM
4.3.5.7
83
Defasagem
Quando a programação de múltiplos semáforos é feita simultaneamente, em contraponto à configuração de um semáforo isolado, a sincronização entre interseções
por meio de defasagens deve ser considerada. Com esse atributo, é possível fazer
com que uma fila de veículos siga durante um período de tempo em vários semáforos
abertos seguidamente. Isso é utilizado principalmente em avenidas principais.
Para implementar a defasagem no simulador GISSIM, a geração dos eventos dos
semáforos foi modificada. Primeiramente, o usuário tem que informar o valor de defasagem para cada ciclo. Depois disso, a geração de eventos semafóricos por meio da
classe Cycle é feita iniciando a partir do instante de defasagem até completar o ciclo
novamente.
4.3.5.8
Interface gráfica de simulação
Finalmente, a tela de simulação foi reformulada para adicionar algumas funcionalidades, deixando o simulador GISSIM mais elaborado. A Figura 42 mostra a tela de
simulação.
Figura 42: Tela de simulação
Inicialmente, tem-se o menu no canto superior da tela com as configurações de
4.3 Simulador GISSIM
84
entidades. No canto superior à esquerda, alguns campos de configuração: plano (define qual plano semafórico será usado), tempo de simulação (quantas etapas serão
simuladas), início (hora de início), término (hora de término). Esses campos devem
ser preenchidos para configurar a simulação. Além disso, no canto inferior esquerdo
existem outros atributos de configuração. Já no lado direito da tela de simulação, um
painel contém informações sobre a simulação, que são atualizadas a cada instante.
Por fim, no canto inferior, alguns controles podem ser visualizados, tais como iniciar,
executar uma etapa somente, pausar e parar. Ademais, é possível aumentar ou diminuir a velocidade da simulação usando uma barra localizada à direita.
85
5
EXPERIMENTOS
Para validar a técnica proposta neste trabalho, que inclui o uso de conceitos apresentados em conjunto com algoritmos multiobjetivo em um sistema de informação
geográfica (SIG), foi necessário realizar experimentos em regiões reais com dados de
tráfego coletados em campo, de modo que, os resultados sejam mais próximos da realidade. Para tanto, foram utilizados dados fornecidos pela BHTRANS, empresa que
gerencia o tráfego em Belo Horizonte (MG).
A BHTRANS forneceu dados do hipercentro de Belo Horizonte, região mais importante da capital, que tem apresentado um volume grande e crescente de tráfego. Os
dados estão divididos em duas categorias:
1. Contagem volumétrica: é a medida de fluxo geralmente utilizada nos simuladores, significa o número de veículos que percorrem cada trecho em uma hora
(VPH);
2. Planos semafóricos: são utilizados para definir as configurações de semáforos
da região: movimentos, ciclo, fases, estágios, intervalos de tempo, defasagens,
etc.
Os dados foram coletados com instrumentos da engenharia de tráfego durante o
período entre 01/01/2011 e 31/07/2011, e são usados por conter informações confiáveis que correspondem a realidade da região escolhida. Como a região do hipercentro
de Belo Horizonte não possui características de uma microrregião devido ao seu tamanho, foi necessário escolher sub-regiões para realizar os experimentos. Nesse
contexto, verificando a importância de trechos que possuíam informações suficientes
para realizar os experimentos, duas microrregiões do hipercentro foram escolhidas:
Praça Sete - Raul Soares (Via Arterial) e Praça Raul Soares (Rede).
As microrregiões foram desenhadas no SIG OpenJUMP conforme foi descrito na
Subseção 4.1.2, por meio do sistema de coordenadas Universal Transversal de Mer-
5 EXPERIMENTOS
86
cator (UTM). O simulador GISSIM utiliza essas coordenadas para calcular a distância
percorrida pelos veículos.
Para verificar o comportamento dos algoritmos em situações diferentes e verificar
a qualidade dos resultados para cada uma dessas situações, os experimentos realizados nos dois cenários também são realizados em dois horários diferentes. Nesse
contexto, após a observação dos dados de volume, dois intervalos de tempo foram
escolhidos: 7 às 8 horas e 17 às 18 horas. Para os padrões de tráfego, esses dois
horários são considerados críticos, devido ao grau de saturação das vias.
Após definir os cenários dos experimentos e os intervalos de tempo, foram comparados planos semafóricos advindos de cinco abordagens: (1) BHTRANS, (2) GAFX11 - GA mono-objetivo otimizando Fx1, (3) GA-FX21 - GA mono-objetivo otimizando
Fx2, (4) NSGA21 e (5) MBVL-NSGA2. Por fim, foi feita uma análise das técnicas de
otimização e uma comparação estatística entre as duas técnicas multiobjetivo. Os
experimentos estão descritos na Tabela 2.
Tabela 2: Experimentos
Cenário
Período
Algoritmos
BHTRANS
GA-FX1
7h às 8h
GA-FX2
Praça Sete - Raul Soares
NSGA2
(Via Arterial)
MBVL-NSGA2
BHTRANS
GA-FX1
17h às 18h
GA-FX2
NSGA2
MBVL-NSGA2
BHTRANS
GA-FX1
7h às 8h
GA-FX2
NSGA2
Raul Soares (Rede)
MBVL-NSGA2
BHTRANS
GA-FX1
17h às 18h
GA-FX2
NSGA2
MBVL-NSGA2
Os resultados são comparados para verificar as vantagens e desvantagens de
1
GA-FX1, GA-FX2 e NSGA2 utilizam seleção por torneio binário, cruzamento uniforme e mutação
por inversão (flip mutation), ao contrário do MBVL-NSGA2 que usa operadores adaptativos
5.1 Parâmetros
87
cada implementação. Como a natureza dos algoritmos utilizados aqui é estocástica,
os experimentos foram executados por 20 vezes para avaliar estatisticamente os resultados.
Nas próximas subseções, os parâmetros e o método de comparação estatística
são descritos. Depois os experimentos são abordados, juntamente com resultados e
análises.
5.1
Parâmetros
Várias combinações de parâmetros do algoritmo NSGA2 foram testadas durante
os experimentos. A Tabela 3 descreve a configuração responsável pelos melhores
resultados obtidos. Por isso, ela foi adotada em todos os experimentos.
Tabela 3: Parâmetros dos algoritmos genéticos
Parâmetro
Valor
Tamanho da População
50 indivíduos
Número de Gerações
100
85%
Taxa de Cruzamento
Taxa de Mutação
3%
Cretério de Parada
número de gerações
Os parâmetros acima foram obtidos a partir de uma observação empírica das funções. Por exemplo, para definir o número de gerações, testes foram executados com
50, 100 e 200. O comportamento utilizando os parâmetros 50 e 200 foi ruim, porque o
primeiro valor não garante uma convergência completa do algoritmo, enquanto que, o
segundo valor excede as gerações em que o algoritmo fica estável e, com isso, dispende várias horas avaliando soluções sem melhorar o resultado final. Do mesmo
modo, constatou-se também que a variação do tamanho da população não era sinônimo de melhores resultados. Pelo contrário, muitas soluções repetidas acabavam
sendo geradas e avaliadas desnecessariamente.
Foi necessário configurar alguns parâmetros da programação semafórica, que estão apresentados na Tabela 4.
Inicialmente, o número de etapas de simulação é definido. Esse valor é utilizado
na avaliação dos indivíduos, já que corresponde ao tempo em que o trânsito é simulado pelo GISSIM. O valor de 7200 é um valor em que a rede de tráfego consegue
5.2 Metodologia de Comparação Estatística
88
Tabela 4: Parâmetros do GISSIM-TL
Parâmetro
Valor
Etapas de Simulação
7200 (2 horas)
Tempo Mínimo de Estágio 25 segundos
Tempo Máximo de Estágio tempo de ciclo - 25 segundos
3 segundos
Tempo de Amarelo
estabilizar-se, retornando resultados confiáveis. Esse parâmetro corresponde a 2 horas reais de trânsito.
Os tempos mínimo e máximo de estágio correspondem ao domínio das variáveis
de decisão. Segundo CONTRAN (2012), os tempos de estágio não podem ser demasiado curtos, devido a insegurança gerada. Ademais, alguns manuais dizem que o
tempo de estágio não deve ser menor que 20 segundos. Por isso, os valores configurados tentam aliviar isso. O tempo de amarelo foi escolhido de acordo com os planos
semafóricos utilizados pela BHTRANS.
5.2
Metodologia de Comparação Estatística
Conforme explicado anteriormente, as execuções dos algoritmos produzem resultados diferentes a cada execução, já que são de natureza estocástica. Sendo assim,
para comparar o desempenho dos algoritmos é necessário aplicar uma metodologia
estatística. Neste trabalho, aplica-se uma metodologia que utiliza os indicadores de
hipervolume dos conjuntos de soluções não dominadas, para comparar os algoritmos
NSGA2 e MBVL-NSGA2 em cada um dos experimentos. Nesse contexto, 20 amostras
de hipervolume de cada algoritmo são utilizadas para obter o p-valor, calculado a partir
do teste T de Welch, para realizar a comparação. As próximas subseções descrevem
as três etapas necessárias para fazer a comparação.
5.2.1
Cálculo do Hipervolume
O indicador de hipervolume (ZITZLER, 1999) calcula a área desde a fronteira de
soluções não dominadas a um ponto de referência definido. Essa medida de desempenho indica que, quanto maior for a área que as soluções dominam, melhor será o
conjunto obtido pelo algoritmo. É uma medida de desempenho bastante utilizada na
literatura, necessitando apenas do conhecimento de um único ponto de referência.
5.2 Metodologia de Comparação Estatística
89
Esse ponto deve ser dominado por todas as fronteiras encontradas pelos algoritmos.
A Figura 43 ilustra esse cálculo.
Figura 43: Exemplo de cálculo do hipervolume para um conjunto de soluções não
dominadas em um problema de minimização de f1 e f2
A partir do conjunto de soluções não dominadas y1, y2, y3 e y4, escolhe-se um
ponto de referência e a área é calculada. Esse ponto de referência deve ser um ponto
dominado por todas as soluções das amostras e pode ser escolhido aleatoriamente.
Essa medida estima uma qualidade para as fronteiras geradas. O ponto de referência
utilizado neste trabalho é F x1 = 24 e F x2 = 190. Esse ponto foi escolhido por ser
dominado por todas as soluções encontradas nos experimentos.
5.2.2
Método Bootstrap
O método Bootstrap (EFRON; TIBSHIRANI, 1993) é um método de reamostragem
baseado na construção de subamostras a partir de um conjunto de dados iniciais,
para estimar a distribuição de probabilidade. O Algoritmo 12 mostra o procedimento
utilizado neste trabalho para calcular a média e o desvio padrão de uma distribuição
amostral.
Esse procedimento foi usado neste trabalho para calcular a média e desvio de n
amostras de hipervolume para N algoritmos. Depois de executar o método Boots-
5.2 Metodologia de Comparação Estatística
90
Algoritmo 12 Pseudo-código do método Bootstrap
1: entrada amostra;
2: N algs = 2; // Número de algoritmos
3: n = 20; // Número de elementos da amostra
4: bootstraps = 10000; // Iterações do método bootstrap
5: para (alg = 1..N algs) faça
6:
para (i = 1..bootstraps) faça
7:
reamostra = RAN DOM _V ET (amostra[alg]); // Reamostra com n elementos
aleatórios
8:
amostraBS[alg, i] = M EDIA(reamostra); // Média dos elementos de reamostra
9:
fim para
10:
media[alg] = M EDIA(amostraBS[alg]); // Média da amostra do bootstrap
11:
desvio[alg] = DESV IO(amostraBS[alg]); // Desvio padrão da amostra do bootstrap
12:
saída media[1..N ], desvio[1..N ];
13: fim para
trap e obter a média e desvio padrão para os algoritmos NSGA2 e MBVL-NSGA2,
basta executar o teste T de Welch para obter o p-valor e fazer a comparação entre os
métodos.
5.2.3
Teste T de Welch
O teste T de Welch (WELCH, 1947) é uma adaptação do teste T de Student para
uso com duas amostras com variâncias desiguais. Sendo assim, para as amostras de
hipervolume dos algoritmos NSGA2 e MBVL-NSGA2, o teste define a estatística (t) e
o número de graus de liberdade (v) pela equações (5.1) e (5.2), respectivamente,
X1 − X2
,
t= q 2
s1
s22
+ N2
N1
s2
v=
s22 2
)
N2
,
s41
s42
+
2
2
N1 (N1 −1)
N2 (N2 −1)
(5.1)
( N11 +
onde:
X1 é a média do primeiro algoritmo;
X2 é a média do segundo algoritmo;
(5.2)
5.3 Praça Sete - Raul Soares (Via Arterial)
91
s1 é a variância da amostra do primeiro algoritmo;
s2 é a variância da amostra do segundo algoritmo;
N1 e N2 é o número de elementos das amostras.
Por fim, deve-se calcular o p-valor e testar as hipóteses da Equação (5.3),
H0 : µN SGA2 = µM BV L_N SGA2
H1 : µN SGA2 6= µM BV L_N SGA2
(5.3)
Considerando o teste bilateral e escolhendo o nível de significância igual a 0, 05,
é possível utilizar o p-valor para comparar as amostras de NSGA2 e MBVL-NSGA2,
bastando verificar as seguintes condições:
• Se o p-valor estiver no intervalo entre 0,025 e 0,975, a hipótese H0 é aceita, isto
é, não existe evidência estatística da diferença entre os métodos;
• Se o p-valor for menor que 0, 025 então a hipótese H0 é rejeitada, isto é, a média
do algoritmo 1 é menor que a média do algoritmo 2;
• Se o p-valor for maior que 0, 975 então a hipótese H0 é rejeitada, isto é, a média
do algoritmo 1 é maior que a média do algoritmo 2.
Nesse caso, trata-se de amostras de hipervolume e, por isso, quanto maior a média
de um algoritmo melhor ele é, se comparado a um algoritmo com média menor.
5.3
Praça Sete - Raul Soares (Via Arterial)
No primeiro cenário, o experimento é realizado em um trecho da Av. Amazonas,
que se localiza em uma região importante de Belo Horizonte, já que é uma via que conecta a Praça Raul Soares à Praça Sete. Na literatura, esse tipo de região é chamada
de via arterial. A Figura 44 ilustra a região no Google Maps. Embora a região em torno
da avenida seja dada, os trechos utilizados no experimento estão destacados.
Utilizando as informações do Google Maps e da BHTRANS, essa microrregião foi
desenhada no OpenJUMP, como mostra o screenshot na Figura 45. Nela é possível
observar os trechos desenhados na cor verde, os semáforos estão destacados em
5.3 Praça Sete - Raul Soares (Via Arterial)
92
Figura 44: Via arterial ligando a Praça Sete e a Raul Soares. Adaptado de Google
Maps
círculos também verdes e os pontos de entrada/saída da rede estão representados
em triângulos vermelhos.
Figura 45: Via arterial ligando a Praça Sete e a Raul Soares desenhada no OpenJUMP
Depois de desenhar a região no OpenJUMP, verifica-se que a microrregião possui
72 trechos, incluindo os pequenos trechos que ligam as junções de controle semaforizadas aos cruzamentos; 23 junções de controle, representando as junções semafo-
5.3 Praça Sete - Raul Soares (Via Arterial)
93
rizadas; 20 junções de entrada/saída, utilizados para a geração/coleta de veículos da
rede.
Por fim, a configuração dos grupos semafóricos (ciclos, fases, estágios, defasagens), entrada de veículos e volume de entrada foi feita. A Figura 46 ilustra a microrregião desenhada pelo simulador GISSIM, em que os quatro grupos semafóricos estão
destacados em círculos brancos (grupos 1, 2, 3 e 4) e as junções de entrada estão
destacadas em quadrados brancos (junções 43, 45, 33, 64, 65, 26 e 31).
Figura 46: Via arterial ligando a Praça Sete e a Raul Soares no GISSIM-TL
Os grupos semafóricos foram configurados de acordo com as definições da BHTRANS. Em seguida, os algoritmos de otimização foram executados em dois horários
diferentes, de modo a obter o melhor desempenho para as funções de avaliação em
cada horário.
Para realizar os experimentos, foi necessário organizar os dados volumétricos disponibilizados pela BHTRANS para informar ao simulador o número de veículos que
entram na rede e o volume de conversão para cada interseção. A Tabela 5 apresenta
o volume de entrada na rede a cada hora (VPH) para os intervalos de 7 às 8 horas e
de 17 às 18 horas.
Além do número de veículos que entram na rede a cada hora, é necessário configurar o volume para cada conversão. Todas as conversões foram configuradas de
acordo com os dados fornecidos pela BHTRANS.
5.3 Praça Sete - Raul Soares (Via Arterial)
94
Tabela 5: Entrada de veículos da Praça Sete - Raul Soares (Via Arterial)
Junção Descrição
VPH (7-8hs) VPH (17-18hs)
64
Av. Paraná
1370
1074
Av. Amazonas -> Praça Raul Soares
1248
1047
31
43
Av. Amazonas -> Praça Sete
1084
1154
Rua São Paulo
1069
1199
26
45
Rua Santa Catarina
700
600
Rua Curitiba
523
402
65
33
Rua Padre Belchior
207
297
5.3.1
Resultados
Nessa subseção, são apresentados os resultados para a Praça Sete - Raul Soares
(Via Arterial) nos horários de 7 às 8 horas e 17 às 18 horas.
5.3.1.1
7 às 8 horas
Após configurar a entrada de veículos e os volumes no intervalo de 7 às 8 horas,
os algoritmos de otimização foram executados na região. A Figura 47 apresenta os
resultados obtidos na região durante o intervalo de tempo.
Figura 47: Resultado para Praça Sete - Raul Soares (Via Arterial) 7-8h
Verifica-se que cinco resultados são apresentados: BHTRANS, GA-FX1, GA-FX2,
5.3 Praça Sete - Raul Soares (Via Arterial)
95
NSGA2 e MBVL-NSGA2. O resultado do plano BHTRANS é a média das simulações
no GISSIM; os resultados dos algoritmos GA-FX1 e GA-FX2 correspondem a média
das execuções; e os conjuntos de soluções não dominados mostrados para o NSGA2
e MBVL-NSGA2 correspondem aqueles mais próximos da média de hipervolume. A
Tabela 6 apresenta os valores de BHTRANS, GA-FX1 e GA-FX2 para uma discussão
inicial.
Tabela 6: Resultados para Praça Sete - Raul Soares (Via Arterial) 7-8h
Técnica
Fx1 (Velocidade Média) Fx2 (Variância da Vel. Média)
BHTRANS
26,37
172,13
GA-FX1
28,80
173,53
GA-FX2
26,72
154,14
Primeiramente, os resultados obtidos pelo AG conseguem melhorar o resultado do
plano semafórico da BHTRANS. Isso pode ser observado pela melhoria nas funções
de avaliação. Em relação à função Fx1, o plano da BHTRANS obteve um resultado
de 26, 37, enquanto o algoritmo GA-FX1 obteve o resultado de 28, 80. Esse valor indica que a velocidade média dos veículos na rede foi 2, 43km/h maior em GA-FX1,
correspondendo a 9, 21% de aumento em relação à velocidade média anterior.
Analisando a função Fx2, o plano da BHTRANS obteve um resultado de 172, 13,
à medida que o algoritmo GA-FX2 conseguiu melhorar o valor da variância da velocidade velocidade média para 154, 14. Isso corresponde a um decréscimo de 10, 45% em
relação à variância anterior. Quando o valor da variância é transformado para desvio
padrão, obtém-se o resultado de 13, 11 para o plano da BHTRANS e uma melhoria
para 12, 41 pelo algoritmo GA-FX2. A melhoria no desvio padrão foi de 0, 7, correspondendo a 5, 3% em relação ao desvio padrão anterior.
As soluções encontradas pelo NSGA2 conseguem aproximar-se das encontradas
pelos algoritmos GA-FX1 e GA-FX2. Por exemplo, quando se observa a solução próxima ao extremo da função Fx2, verifica-se que ela possui o valor de Fx1=26, 80 e
Fx2=154, 12. Se comparada à solução gerada pelo GA-FX2 (Fx1=26, 72 e Fx2=154, 14),
constata-se que o NSGA2 conseguiu gerar uma solução de qualidade bem parecida.
Mas, além disso, o NSGA2 gerou outras 15 soluções eficientes. Portanto, verificase aqui a diversidade de soluções ao longo do conjunto que é obtida com o uso do
algoritmo multiobjetivo baseado em Pareto.
O algoritmo MBVL-NSGA2 tem o comportamento bem parecido ao NSGA2, ou
seja, também consegue gerar um conjunto de soluções eficientes e diversificadas.
5.3 Praça Sete - Raul Soares (Via Arterial)
96
Nesse caso, 15 soluções não dominadas foram geradas. O MBVL-NSGA2 consegue
gerar soluções bem próximas às geradas por GA-FX1 e GA-FX2, ou seja, no extremo
do conjunto, enquanto gera outras 13 soluções não dominadas diferentes. A vantagem
disso é que cabe ao especialista do problema escolher o plano semafórico desejado,
dentre as soluções propostas pelo algoritmo, para cada situação particular que se
apresente. Por exemplo, quando se quer priorizar a velocidade média, escolhe-se
uma solução com o maior valor de Fx1 e, em contrapartida, para priorizar a variância
escolhe-se uma solução com o menor valor de Fx2. Caso o objetivo seja manter um
equilíbrio entre Fx1 e Fx2, deve-se escolher um outro plano semafórico do conjunto.
São discutidas a seguir as evoluções das funções de avaliação ao longo da execução do algoritmo. A Figura 48 mostra a evolução das funções Fx1 e Fx2 ao longo
de 100 gerações para os algoritmos comparados neste trabalho. Os valores apresentados aqui correspondem a média obtida de todas as execuções dos algoritmos para
cada geração.
Figura 48: Evolução das funções para Praça Sete - Raul Soares (Via Arterial) 7-8h
Todos os algoritmos utilizados apresentaram convergência assintótica dos objetivos perseguidos, ao final de cada execução. Isso é uma indicação de que o número
de gerações usado como critério de parada foi suficiente para que eles obtivessem
soluções próximas das ótimas para cada objetivo buscado. Os algoritmos GA-FX1
e GA-FX2 conseguem uma estabilização mais rápida para as duas funções e mantêm os resultados melhores que os algoritmos multiobjetivo. Esse fator é facilmente
5.3 Praça Sete - Raul Soares (Via Arterial)
97
explicado, já que, os algoritmos mono-objetivo otimizam somente uma função cada,
facilitando a convergência e estabilização desta. No entanto, os algoritmos NSGA2 e
MBVL-NSGA2 mostraram que também conseguem convergir para boas soluções ao
longo da execução do algoritmo, estabilizando-se com o tempo. Finalmente, é notório
que a evolução de Fx1 é mais constante, ao mesmo tempo que a função Fx2 tem uma
variação maior ao longo da execução, embora essa variação seja muito pequena, em
torno de uma unidade em cada método.
5.3.1.2
17 às 18 horas
A Figura 49 mostra os resultados obtidos na região durante o intervalo de 17 às
18 horas.
Figura 49: Resultado para Praça Sete - Raul Soares (Via Arterial) 17-18h
Nesse gráfico, novamente, cinco resultados são apresentados: BHTRANS, GAFX1, GA-FX2, NSGA2 e MBVL-NSGA2. A Tabela 7 apresenta os valores de BHTRANS, GA-FX1 e GA-FX2 para uma discussão inicial.
Os resultados obtidos pelos AG conseguem melhorar o resultado do plano sema-
5.3 Praça Sete - Raul Soares (Via Arterial)
98
Tabela 7: Resultados para Praça Sete - Raul Soares (Via Arterial) 17-18h
Técnica
Fx1 (Velocidade Média) Fx2 (Variância da Vel. Média)
BHTRANS
26,60
184,68
GA-FX1
29,58
159,72
GA-FX2
27,25
146,31
fórico da BHTRANS, como no experimento anterior. Em relação à função Fx1, o plano
da BHTRANS obteve um resultado de 26, 60, enquanto o algoritmo GA-FX1 obteve o
resultado de 29, 58. Esse valor indica que a velocidade média dos veículos na rede
foi 2, 98km/h maior em GA-FX1, correspondendo a 11, 2% de aumento em relação à
velocidade média anterior.
Analisando a função Fx2, o plano da BHTRANS obteve um resultado de 184, 68,
à medida que o algoritmo GA-FX2 conseguiu melhorar o valor da função para 146, 31.
Isso corresponde a um decréscimo de 20, 78% em relação à variância anterior. Quando
o valor da variância é transformado para desvio padrão, obtém-se o resultado de 13, 58
para o plano da BHTRANS e uma melhoria para 12, 09 pelo algoritmo GA-FX2. A
melhoria no desvio padrão foi de 1, 48, correspondendo a 10, 9% em relação ao desvio
padrão anterior.
As soluções encontradas pelo NSGA2 conseguem aproximar-se das encontradas
pelos algoritmos GA-FX1 e GA-FX2. Por exemplo, quando se observa a solução próxima ao extremo da função Fx1, verifica-se que ela possui o valor de Fx1=29, 6 e
Fx2=156, 89. Se comparada a solução gerada pelo GA-FX1 (Fx1=29, 58 e Fx2=159, 72),
constata-se que o NSGA2 conseguiu gerar uma solução de qualidade bem parecida
com o GA-FX1. Além disso, o NSGA2 gerou outras 9 soluções eficientes. Portanto,
verifica-se aqui a diversidade de soluções ao longo do conjunto que é obtida com o
uso do algoritmo multiobjetivo baseado em Pareto.
O algoritmo MBVL-NSGA2 tem o comportamento similar ao NSGA2, ou seja, também consegue gerar um conjunto de soluções eficientes e diversificadas. Nesse caso,
15 soluções não dominadas foram geradas. O MBVL-NSGA2 consegue gerar soluções próximas às produzidas por GA-FX1 e GA-FX2, ou seja, no extremo do conjunto,
enquanto gera outras soluções não dominadas diferentes. A vantagem disso, novamente, é que cabe ao especialista no problema escolher o plano semafórico desejado,
dentre as soluções propostas pelo algoritmo.
A Figura 50 apresenta as evoluções das funções Fx1 e Fx2 ao longo da execução
dos algoritmos.
5.3 Praça Sete - Raul Soares (Via Arterial)
99
Figura 50: Evolução das funções para Praça Sete - Raul Soares (Via Arterial) 17-18h
Todos os algoritmos utilizados apresentaram convergência assintótica dos objetivos perseguidos, ao final de cada execução. Isto é uma indicação de que o número
de gerações usado como critério de parada foi suficiente para que eles obtivessem
soluções próximas das ótimas para cada objetivo buscado. Os algoritmos GA-FX1
e GA-FX2 conseguem uma estabilização mais rápida para as duas funções e mantêm os resultados melhores que os algoritmos multiobjetivo. Essa característica foi
apresentada no experimento anterior.
Os algoritmos NSGA2 e MBVL-NSGA2 mostraram que também conseguem convergir para boas soluções ao longo da execução do algoritmo, estabilizando-se com o
tempo. Nesse caso, os resultados são constantes durante toda a execução para todos
os algoritmos. Ademais, os algoritmos multiobjetivos conseguiram obter resultados
bem semelhantes.
5.3.2
Comparação Estatística
Os resultados dos algoritmos multiobjetivo NSGA2 e MBVL-NSGA2 foram comparados para definir o mais eficiente para essa região. Para isso, utilizou-se o método
descrito na Seção 5.2. Aquele método baseia-se nos indicadores de hipervolume para
comparar a eficiência dos dois algoritmos. Sendo assim, foi necessário calcular o conjunto de indicadores de hipervolume para as execuções dos algoritmos.
5.3 Praça Sete - Raul Soares (Via Arterial)
100
A Figura 51 exibe dois boxplots (um para cada intervalo de tempo), utilizando o
conjunto de valores de hipervolume obtidos durante as execuções.
Figura 51: Boxplots dos indicadores de hipervolume da Praça Sete - Raul Soares (Via
Arterial)
Na figura, como é usado nos diagramas de caixa, a linha central indica a mediana
das amostras, as caixas comprimem os dois quartis médios das amostras, os traços
horizontais extremos abaixo e acima indicam o valor mínimo e máximo não discrepantes da amostra e os valores discrepantes estão representados com o símbolo ‘+’.
Seja a amostra os indicadores de hipervolume, faz-se uma estimativa da distribuição usando o método bootstrap, como mostra a Figura 52.
Por fim, o teste T de Welch foi aplicado para calcular o p-valor e comparar as
médias geradas pelo método bootstrap. A Tabela 8 mostra os valores encontrados
para a distribuição da Figura 52.
Tabela 8: Valor-p encontrado para Praça Sete - Raul Soares (Via Arterial)
Experimento
p-valor
(a) Praça Sete - Raul Soares (Via Arterial) 7-8h
0, 15037
(b) Praça Sete - Raul Soares (Via Arterial) 17-18h 0, 23396
Nos dois experimentos, o p-valor está no intervalo entre 0, 025 e 0, 975. Por isso,
pode-se afirmar que não existe evidência estatística da diferença entre os métodos
aplicados nessa região.
5.4 Praça Raul Soares (Rede)
101
Figura 52: Distribuição bootstrap na Praça Sete - Raul Soares (Via Arterial)
5.4
Praça Raul Soares (Rede)
No segundo cenário, o experimento foi realizado na região da Praça Raul Soares,
que também é uma região importante de Belo Horizonte, já que conecta o fluxo da Av.
Amazonas à Praça Sete (e vice-versa), o fluxo de entrada/saída do Viaduto Castelo
Branco, o fluxo da Av. Bias Fortes em direção ao Lourdes e Savassi e o fluxo da
Av. Augusto de Lima em direção à Afonso Pena. Na literatura, esse tipo de região é
considerado como uma rede semafórica. A Figura 53 ilustra a região no Google Maps.
Na figura, embora a região em torno da avenida seja dada, os trechos utilizados no
experimento estão destacados.
Utilizando as informações do Google Maps e da BHTRANS, essa microrregião foi
desenhada no OpenJUMP, como apresenta a Figura 54. Nela é possível observar os
trechos desenhados na cor verde, os semáforos estão destacados em círculos também verdes e os pontos de entrada/saída da rede estão representados em triângulos
vermelhos.
Depois de desenhar a região no OpenJUMP, verifica-se que a mesma possui 282
trechos, incluindo os pequenos trechos que ligam as junções de controle semaforizadas aos cruzamentos; 100 junções de controle, representando as junções semaforizadas; 38 junções de entrada/saída, utilizados para a geração/coleta de veículos da
rede.
5.4 Praça Raul Soares (Rede)
102
Figura 53: Praça Raul Soares. Extraído de Google Maps
Figura 54: Praça Raul Soares desenhada no OpenJUMP
Por fim, a configuração dos grupos semafóricos (ciclos, fases, estágios, defasagens), entrada de veículos e volume de entrada foi feita. A Figura 55 ilustra a microrregião desenhada pelo simulador GISSIM, em que os quatro grupos semafóricos estão
5.4 Praça Raul Soares (Rede)
103
destacados em círculos brancos (grupos 1 a 36) e as junções de entrada de veículos
estão destacadas em quadrados brancos (junções 110, 182, 132, 175, 75, 169, 225,
201, 166, 135, 195, 93, 82, 62, 199, 22, 108, 183).
Figura 55: Praça Raul Soares no simulador GISSIM
Os grupos semafóricos foram configurados de acordo com as definições da BHTRANS e, agora, os algoritmos de otimização serão executados em dois horários
diferentes, de modo a obter o melhor desempenho para as funções de avaliação em
cada horário.
Para realizar os experimentos, foi necessário organizar os dados volumétricos disponibilizados pela BHTRANS, para informar ao simulador o número de veículos que
entram na rede e o volume de conversão para cada interseção. A Tabela 9 apresenta
o volume de entrada na rede a cada hora (VPH) no intervalo de 7 às 8 horas e 17 às
18 horas.
Além do número de veículos que entram na rede a cada hora, é necessário configurar o volume para cada conversão. Todas as conversões foram configuradas de
acordo com os dados fornecidos pela BHTRANS.
5.4 Praça Raul Soares (Rede)
Junção
110
62
166
108
182
195
75
132
201
22
199
93
135
225
169
82
175
5.4.1
104
Tabela 9: Entrada de veículos da Praça Raul Soares (Rede)
Descrição
VPH (7-8hs) VPH (17-18hs)
Av. Amazonas -> Centro
1768
1682
Rua Rio Grande do Sul
226
220
Av. Olegário Maciel -> Assembléia
500
596
Rua Santa Catarina
100
100
Av. Bias Fortes -> Savassi
1470
1490
Av. Augusto de Lima -> Pça Afonso Arinos
300
360
Rua Padre Belchior -> Lourdes
768
608
Av. Amazonas -> Praça da Estação
1185
1285
Rua Curitiba
523
500
Av. Paraná - Pça da Rodoviária
173
300
Rua dos Guaranis
222
220
Av. Olegário Maciel -> Rodoviária
243
277
Rua Rio Grande do Sul
500
550
Av. Bias Fortes -> Elevado
600
720
Rua dos Tupis
639
499
Av. Augusto de Lima -> Barro Preto
232
652
Rua dos Timbiras
1029
899
Resultados
Nessa subseção, são apresentados os resultados para os períodos de tempo: 7
às 8 horas e 17 às 18 horas.
5.4.1.1
7 às 8 horas
Após configurar os volumes no intervalo de 7 às 8 horas, os algoritmos foram
executados na região. A Figura 56 mostra os resultados obtidos na região para o
horário em questão.
Cinco resultados são mostrados: BHTRANS, GA-FX1, GA-FX2, NSGA2 e MBVLNSGA2. Na Tabela 10, os resultados são descritos para melhorar a visualização.
Tabela 10: Resultados para a região Praça Raul Soares (Rede) 7-8h
Técnica
Fx1 (Velocidade Média) Fx2 (Variância da Vel. Média)
BHTRANS
24,18
179,56
GA-FX1
29,31
165,42
GA-FX2
24,65
143,91
Os resultados obtidos pelo AG conseguem melhorar o resultado do plano semafórico da BHTRANS, de acordo com a melhoria nas funções de avaliação. Em relação
5.4 Praça Raul Soares (Rede)
105
Figura 56: Resultado para a região Praça Raul Soares (Rede) 7-8h
à função Fx1, o plano da BHTRANS obteve um resultado de 24, 18, enquanto o algoritmo GA-FX1 obteve o resultado de 29, 31. Esse valor indica que a velocidade média
dos veículos na rede foi 5, 13km/h maior, correspondendo a 21, 22% de aumento em
relação à velocidade média anterior.
Analisando a função Fx2, o plano da BHTRANS obteve um resultado de 179, 56,
à medida que o algoritmo GA-FX2 conseguiu melhorar o valor da função para 143, 91.
Isso corresponde a um decréscimo de 19, 85% em relação à variância anterior. Quando
o valor da variância é transformado para desvio padrão, tem-se o resultado de 13, 40
para o plano da BHTRANS e uma melhoria para 11, 99 pelo algoritmo GA-FX2. A
melhoria no desvio padrão foi de 1, 41, correspondendo a 10, 52% em relação ao desvio
padrão anterior.
As soluções encontradas pelo NSGA2 conseguem se aproximar das encontradas
pelos algoritmos GA-FX1 e GA-FX2. Por exemplo, quando se observa a solução ao
extremo da função FX1 gerada pelo NSGA2, verifica-se que ela possui o valor de
Fx1=29, 6 e Fx2=156, 89. Se comparada a solução gerada pelo GA-FX1 (Fx1=29, 58 e
Fx2=159, 72), constata-se que o NSGA2 conseguiu gerar uma solução de qualidade
bem parecida. Além disso, o NSGA2 gerou outras 9 soluções eficientes. Portanto, há
diversidade de soluções ao longo do conjunto.
O algoritmo MBVL-NSGA2 comportou-se melhor que o NSGA2, inclusive gerando
5.4 Praça Raul Soares (Rede)
106
conjuntos com indicadores de hipervolume mais altos. Para ele, 10 soluções não dominadas foram geradas. O MBVL-NSGA2 consegue gerar soluções similares às geradas
por GA-FX1 e GA-FX2, ou seja, no extremo do conjunto.
São discutidas a seguir as evoluções das funções de avaliação ao longo da execução do algoritmo. A Figura 57 mostra a evolução das funções Fx1 e Fx2 ao longo
de 100 gerações para os algoritmos comparados neste trabalho. Como nos casos anteriores, os valores dados correspondem à média obtida de todas as execuções dos
algoritmos para cada geração.
Figura 57: Evolução das funções para Praça Raul Soares (Rede) 7-8h
Todos os algoritmos utilizados apresentaram convergência assintótica dos objetivos perseguidos, ao final de cada execução. Isto é uma indicação de que o número de
gerações usado como critério de parada foi suficiente para que eles obtivessem boas
soluções. O comportamento dos algoritmos GA-FX1 e GA-FX2, NSGA2 e MBVLNSGA2 em relação ao tempo de estabilização é similar ao descrito na Seção 5.3.
5.4.1.2
17 às 18 horas
Após configurar os volumes no intervalo de 17 às 18 horas, os algoritmos foram
executados na região da Praça Raul Soares. A Figura 58 mostra os resultados obtidos
para o horário em questão.
Cinco resultados são mostrados: BHTRANS, GA-FX1, GA-FX2, NSGA2 e MBVL-
5.4 Praça Raul Soares (Rede)
107
Figura 58: Resultado para a região Praça Raul Soares (Rede) 17-18h
NSGA2. Na Tabela 11, os resultados são descritos para melhorar a visualização.
Tabela 11: Resultados para a região Praça Raul Soares (Rede) 17-18h
Técnica
Fx1 (Velocidade Média) Fx2 (Variância da Vel. Média)
BHTRANS
25,95
187,14
GA-FX1
29,99
172,30
GA-FX2
27,88
158,66
Os resultados obtidos pelo AG conseguem melhorar o resultado do plano semafórico da BHTRANS, de acordo com a melhoria nas funções de avaliação. Em relação
à função Fx1, o plano da BHTRANS obteve um resultado de 25, 95, enquanto o algoritmo GA-FX1 obteve o resultado de 29, 99. Esse valor indica que a velocidade média
dos veículos na rede foi 4, 04km/h maior, correspondendo a 15, 57% de aumento em
relação à velocidade média anterior.
Analisando a função Fx2, o plano da BHTRANS obteve um resultado de 187, 14,
à medida que o algoritmo GA-FX2 conseguiu melhorar o valor da função para 158, 66.
Isso corresponde a um decréscimo de 15, 22% em relação à variância anterior. Quando
o valor da variância é transformado para desvio padrão, tem-se o resultado de 13, 67
para o plano da BHTRANS e uma melhoria para 12, 59 pelo algoritmo GA-FX2. A
melhoria no desvio padrão foi de 1, 08, correspondendo a 7, 9% em relação ao desvio
padrão anterior.
Novamente, o algoritmo MBVL-NSGA2 comportou-se melhor que o NSGA2, ge-
5.4 Praça Raul Soares (Rede)
108
rando conjuntos com indicadores de hipervolume mais altos. Excepcionalmente neste
experimento obtiveram resultados melhores do que o GA-FX2, em média.
A Figura 59 mostra a evolução das funções Fx1 e Fx2 ao longo de 100 gerações
para os algoritmos comparados neste trabalho. Os valores dados para cada função
aqui correspondem à média obtida de todas as execuções dos algoritmos para cada
geração.
Figura 59: Evolução das funções para Praça Raul Soares (Rede) 17-18h
5.4.2
Comparação Estatística
Nesta subseção, os algoritmos multiobjetivo NSGA2 e MBVL-NSGA2 são comparados e é indicado o mais eficiente para a microrregião em análise. Para isso, utiliza-se
o método descrito na Seção 5.2.
A Figura 60 exibe dois boxplots (um para cada intervalo de tempo), utilizando o
conjunto de valores de hipervolume obtidos durante as execuções.
A estimativa da distribuição usando o método bootstrap, com base nos indicadores
de hipervolume é apresentada na Figura 61.
Por fim, o teste T de Welch foi aplicado para calcular o p-valor e comparar as
médias geradas pelo método bootstrap. A Tabela 12 mostra os valores encontrados
para a distribuição da Figura 61.
5.4 Praça Raul Soares (Rede)
109
Figura 60: Boxplots dos indicadores de hipervolume da Praça Raul Soares (Rede)
Figura 61: Distribuição bootstrap na Praça Raul Soares (Rede)
Tabela 12: Valor-p encontrado para Praça Raul Soares (Rede)
Experimento
p-valor
(a) Praça Raul Soares (Rede) 7-8h
0, 01870
(b) Praça Raul Soares (Rede) 17-18h 0, 00179
Nos dois experimentos, o p-valor foi menor que 0, 025. Com isso, utilizando as
definições do p-valor, pode-se afirmar que o algoritmo NSGA2 possui a menor média de hipervolume. Portanto, pode-se afirmar que o algoritmo MBVL-NSGA2 obteve
5.5 Análise Geral dos Resultados
110
melhores resultados para esses experimentos.
5.5
Análise Geral dos Resultados
A Tabela 13 sumariza a comparação dos resultados obtidos pelos algoritmos GAFX1 e GA-FX2 em relação aos planos da BHTRANS. A coluna Fx1 representa a função “Velocidade Média” e a coluna Fx2 representa a função “Variância da Velocidade
Média”. Nessas colunas, o resultado do plano da BHTRANS é dado em valor absoluto
e o resultado dos algoritmos GA-FX1 e GA-FX2 são apresentados como ganhos ou
perdas percentuais com base nos valores médios dos experimentos.
Tabela 13: Resumo dos resultados de GA-FX1 e GA-FX2
Cenário
Período
Algoritmos
Fx1
Fx2
BHTRANS
26, 37
172, 13
GA-FX1
9, 21% −0, 08%
7h às 8h
GA-FX2
0, 13% 10, 45%
Praça Sete - Raul Soares
BHTRANS
26, 60
184, 68
GA-FX1
11, 2% 13, 51%
(Via Arterial)
17h às 18h
GA-FX2
2, 44% 20, 78%
BHTRANS
24, 18
179, 56
GA-FX1
21, 22% 7, 87%
7h às 8h
GA-FX2
1, 94% 19, 85%
BHTRANS
25, 95
187, 14
Raul Soares (Rede)
GA-FX1
15, 57% 7, 92%
17h às 18h
GA-FX2
7, 43% 15, 22%
Os resultados mostraram que, para todos os valores otimizados, o AG consegue
melhorar os resultados da BHTRANS. Na região Praça Sete - Raul Soares (Via Arterial), no período de 7 às 8 horas, a proposta conseguiu aumentar a velocidade média
em 9, 21% e melhorou a variância em 10, 45%. No período de 17 às 18 horas, a velocidade média aumentou em 11, 2% e a variância diminuiu em 20, 78%. Na região Praça
Raul Soares (Rede), os resultados foram mais satisfatórios. No período de 7 às 8
horas, a proposta conseguiu aumentar a velocidade média em 21, 22% e melhorou a
variância em 19, 85%. No período de 17 às 18 horas, a velocidade média aumentou
em 15, 57% e a variância diminuiu em 15, 22%.
Na via arterial com quatro cruzamentos, o ganho superou os 10%. Em uma região
pequena, o ganho da abordagem é satisfatório. Em contrapartirda, no período de 17
às 18 horas, o ganho foi maior que no horário de 7 às 8 horas, chegando a mais de
5.5 Análise Geral dos Resultados
111
20%. A partir de observações, pode-se dizer que o ganho do AG foi maior quando o
número de variáveis aumentou.
A melhoria obtida por esses métodos é considerável, se observada a condição do
trânsito no cenário nacional. Um relatório criado pela CET/SP (CET-SP, 2010), mostrou
que a velocidade média na cidade de São Paulo caiu 33% em 11 anos. Obviamente
essa situação não é particular daquela cidade, pois hoje se vê o caos no trânsito das
cidades brasileiras. Embora a BHTRANS não divulgue indicadores de velocidade média em seu portal eletrônico, é aceitável imaginar que o comportamento seja parecido.
Portanto, uma melhoria de 20% nos experimentos pode ser considerada satisfatória,
pois é capaz de atrasar em alguns anos (entre 6 e 7 anos) o impacto do aumento do
tráfego sobre a qualidade dos deslocamentos médios da população na rede viária.
Após verificar a melhoria obtida em cada função pelo AG, é necessário analisar
os algoritmos multiobjetivo. Primeiramente, é interessante destacar que os algoritmos
NSGA2 e MBVL-NSGA2 conseguiram gerar conjuntos de soluções não dominadas
em todas as execuções. Entretanto, não é viável mostrar todos os conjuntos gerados,
mas, mesmo assim, é possível fazer algumas análises a partir dos conjuntos das
figuras 47, 49, 56 e 58.
Deve-se observar, primeiramente, o caráter multiobjetivo da formulação proposta
para o problema neste trabalho. Para tanto, verifica-se que as duas funções não são
correlacionadas, já que o aumento da velocidade média não implica na diminuição da
variância da velocidade média (e vice-versa). Com isso, é possível visualizar os conjuntos de soluções não dominadas, em que as soluções são eficientes e diversificadas,
indicando a característica de diversidade dos algoritmos multiobjetivo.
Para comparar os resultados dos algoritmos multiobjetivo NSGA2 e MBVL-NSGA2,
foi implementada uma metodologia de comparação estatística para calcular o p-valor
baseada nos indicadores de hipervolume. A Tabela 14 exibe os resultados de média
do hipervolume e o p-valor para os algoritmos.
Tabela 14: Resumo dos resultados de NSGA2 e MBVL-NSGA2
NSGA2
MBVL-NSGA2
Cenário
Período
Hipervolume Hipervolume
Praça Sete - Raul Soares
7h às 8h
146, 28
148, 42
(Via Arterial)
17h às 18h
222, 82
223, 97
7h às 8h
210, 28
220, 21
Raul Soares (Rede)
17h às 18h
195, 51
203, 25
p-valor
0, 15037
0, 23396
0, 01870
0, 00179
5.5 Análise Geral dos Resultados
112
Nota-se que o algoritmo MBVL-NSGA2 obteve uma melhor média de hipervolume
em todos os experimentos. Entretanto, a comparação entre os métodos não é feita
pelas médias, e sim pelo p-valor para aumentar a confiabilidade dos resultados. No
cenário ’Praça Sete - Raul Soares (Via Arterial)’, embora as médias tenham sido maiores, não existe nenhuma evidência estatística que defina que o algoritmo MBVLNSGA2 seja melhor que o método NSGA2. No cenário ’Praça Raul Soares (Rede)’,
as médias de NSGA2 são menores nos dois experimentos. Além disso, o p-valor indica estatisticamente que o algoritmo MBVL-NSGA2 é melhor que o método NSGA2
nesses experimentos.
Observando o comportamento dos algoritmos nos experimentos, primeiramente
nota-se que as soluções da via arterial possuem somente 4 variáveis, enquanto as soluções da rede possuem 28 variáveis. Com isso, o espaço de busca dos algoritmos é
muito maior no segundo cenário. A partir desse aspecto, pode-se dizer que o algoritmo
NSGA2 consegue explorar o espaço de busca do primeiro cenário tão bem quanto o
MBVL-NSGA2, não necessitando de estratégias para melhorar a busca. Por isso, os
dois algoritmos não apresentaram diferenças. Entretanto, como o espaço de busca
do segundo cenário é maior, o NSGA2 não consegue explorar tão bem o espaço de
busca quanto o MBVL-NSGA2. Isso porque o MBVL-NSGA2 possui um esquema que
inibe a revisitação de soluções, e um esquema de exploração de vizinhanças mais
bem elaborado. Ademais, ao longo da execução, quando as vizinhanças são bem
exploradas, a aleatoriedade do algoritmo vai aumentando, de acordo com o atributo
de profundidade. Por isso, o algoritmo MBVL-NSGA2 foi melhor que o NSGA2 para a
região em rede. Possivelmente, um operador de busca local melhoraria os resultados
da proposta.
Deve-se considerar também outro ponto nos resultados. Pela otimização da velocidade média e variância da velocidade média, o número de veículos deixando a
rede foi maior que os planos usados atualmente. Isso foi observado por meio dos
experimentos, verificando a razão entre veículos coletados e veículos gerados. Essa
característica indica que a vazão da rede é maior, pois o fluxo foi consequentemente
otimizado.
Por fim, a média do tempo de execução dos algoritmos na via arterial é de 2:24hs,
mas na região em rede a média de execução é de 8hs. Contudo, o tempo de execução
na região em rede é muito variável. Em momentos que o plano semafórico é eficiente,
a avaliação do indivíduo é rápida, mas caso o plano semafórico seja mal configurado,
5.5 Análise Geral dos Resultados
113
muitos veículos ficam “presos” na rede durante as etapas de simulação, causando
lentidão. A causa disso é que, quanto mais veículos ficam na rede, mais entidades
são atualizadas a cada etapa da simulação. O tempo de execução não é tão crítico
para programação semafórica de tempo fixo, porque os planos são calculados a partir
de dados do passado para serem usados no futuro. Mas, mesmo assim, é desejável
que esse tempo seja menor.
114
6
CONCLUSÕES
Esta dissertação apresentou um estudo sobre o problema de programação semafórica de tempo fixo em redes urbanas. Inicialmente, a proposta era estender a
modelagem de Oliveira e Almeida (2010), introduzindo a avaliação de múltiplas funções objetivo simultaneamente. Entretanto, viu-se que a proposta daqueles autores
apresentava problemas quando aplicada a redes maiores, além de não tratar a programação semafórica de tempo fixo. Por isso, foi necessário modificar a modelagem
dos planos semafóricos, assim como modificar o simulador em vários pontos. As modificações realizadas trouxeram um avanço para o tratamento do problema no software
GISSIM-TL, dando mais possibilidades de aplicação em ambientes reais.
Logo após realizar as modificações na modelagem, foi necessário encontrar uma
combinação de funções objetivo que respeitasse os fundamentos da otimização multiobjetivo e que otimizasse os planos semafóricos. Após testar combinações de funções, tal como maximizar o número de veículos deixando a rede e minimizar o tempo
de trânsito (COSTA; ALMEIDA; CALDEIRA, 2011), definiu-se uma combinação que alcançou os melhores resultados em experimentos: maximizar a velocidade média e minimizar a variância da velocidade média. A primeira função está relacionada a uma
melhoria no fluxo; em contrapartida, a segunda função permite diminuir a variação de
velocidades, de modo a equilibrar a rede.
Para otimizar essa combinação de funções, foi implementado o algoritmo evolucionário multiobjetivo NSGA 2. Os resultados iniciais foram satisfatórios e é possível
verificar os ganhos da abordagem multiobjetivo. Contudo, para melhorar a abordagem
do problema, decidiu-se implementar conceitos de memória e vizinhança adaptativa
no algoritmo. Para tanto, o trabalho de Carrano, Moreira e Takahashi (2011) foi usado
como referência, já que foi aplicado com sucesso em outro problema. Aquela proposta inclui uma memória no NSGA 2, para que evite a revisitação de soluções. Essa
é uma característica desejável, pois o processo de avaliação de soluções no simulador
GISSIM é lento. Com isso, evita-se o gasto desnecessário de tempo com avaliações.
6 CONCLUSÕES
115
Além disso, a proposta inclui operadores adaptativos que melhoram a qualidade das
soluções geradas, pelo fato de explorar mais eficientemente a vizinhança da solução.
O algoritmo chamado MBVL-NSGA2 foi integrado ao plugin GISSIM-TL acoplado ao
OpenJUMP (OLIVEIRA; ALMEIDA, 2010).
Para validar a proposta, dois cenários de microrregiões reais foram escolhidos na
cidade de Belo Horizonte (MG). A primeira é uma via arterial, que liga a Praça Sete
à Praça Raul Soares, enquanto que a segunda é uma rede semafórica localizada
na Praça Raul Soares. Para observar o comportamento dos algoritmos em diferentes situações, foram realizados experimentos em dois intervalos de tempo diferentes
para cada região: 7 às 8 horas e 17 às 18 horas. Os cenários foram desenhados no
OpenJUMP e configurados com dados reais fornecidos pela BHTRANS. Após definir
os cenários dos experimentos e os intervalos de tempo, foram comparados cinco tipos de planos semafóricos: (1) BHTRANS, (2) GA-FX1, (3) GA-FX2, (4) NSGA2 e (5)
MBVL-NSGA2.
Com base nos resultados dos experimentos realizados, várias análises e observações foram feitas e apresentadas no Capítulo 5. Todos os quatro algoritmos de
otimização geram planos semafóricos melhores que os da BHTRANS. As técnicas
mono-objetivo são sempre superiores, mesmo que ligeiramente, nas funções que elas
otimizam. Os dois algoritmos multiobjetivo conseguem gerar soluções de qualidade
parecida com os algoritmos mono-objetivo, mas, além disso, eles geram um conjunto
diversificado de soluções, cabendo ao engenheiro de tráfego escolher o plano mais
adequado de acordo com sua necessidade. No cenário de via arterial, os algoritmos
NSGA2 e MBVL-NSGA2 não possuem diferenças estatísticas que mostrem se uma
técnica é melhor do que a outra; mas, no cenário de rede, o algoritmo MBVL-NSGA2
foi melhor. Por isso verifica-se que a proposta deste trabalho conseguiu gerar resultados satisfatórios para o problema de programação semafórica de tempo fixo em redes.
Por outro lado, os objetivos específicos foram alcançados:
• Extensão da modelagem proposta por Oliveira e Almeida (2010), introduzindo a
avaliação simultânea de múltiplos objetivos: foi refeita a modelagem proposta e
criado um novo pacote de classes que atendem as novas especificações, conforme foi discutido no Capítulo 3;
• Implementação da técnica evolucionária multiobjetivo NSGA 2 aplicada ao problema em questão: essa técnica foi implementada em linguagem Java o algo-
6.1 Contribuições do Trabalho
116
ritmo discutido na Seção 3.3;
• Adição de conceitos sobre memória e vizinhança adaptativa à técnica implementada, baseado no trabalho de Carrano, Moreira e Takahashi (2011): tais conceitos foram implementados no algoritmo MBVL-NSGA2 discutido na Seção 4.2;
• Integração da técnica desenvolvida ao plugin GISSIM-TL (acoplada ao OpenJUMP) desenvolvido por Oliveira e Almeida (2010): os algoritmos NSGA2 e
MBVL-NSGA2 foram integrados no módulo GISSIM-TL conforme discutido no
Capítulo 4; e
• Validação da modelagem e a técnica com a execução de experimentos práticos em microrregiões de interesse, com utilização de dados reais da cidade de
Belo Horizonte, MG: os experimentos e as análises apresentados ao longo do
Capítulo 5 mostraram a execução desta validação.
Por conseguinte, conclui-se que utilizando a metodologia proposta neste trabalho
foi possível cumprir o objetivo geral: realizar a programação semafórica por meio de
algoritmos evolucionários multiobjetivo, a fim de contribuir com o gerenciamento do
tráfego nas cidades.
6.1
Contribuições do Trabalho
Este trabalho trouxe algumas contribuições importantes à área de programação
semafórica:
• O problema foi abordado com duas funções objetivo: maximizar velocidade média e minimizar variância da velocidade média. A primeira função foi usada anteriormente em alguns trabalhos da literatura, mas a segunda função não foi
encontrada na literatura até o momento. A proposta dessa função abre um novo
caminho para a pesquisa na área;
• O algoritmo MBVL-NSGA2, proposto por Carrano, Moreira e Takahashi (2011),
foi aplicado com sucesso a um problema prático de otimização com um alto custo
de avaliação. O método de comparação estatística mostrou que os resultados
deste algoritmo para a rede semafórica superaram os resultados do algoritmo
NSGA 2 puro;
6.2 Publicações
117
• Duas microrregiões ainda não estudadas na literatura acadêmica nos últimos
anos foram modeladas (Praça Sete - Raul Soares (Via Arterial) e Praça Raul
Soares (Rede)), utilizando dados reais do tráfego de Belo Horizonte (MG);
• Desenvolvimento e validação do uso de um framework de otimização criado para
auxiliar a implementação de novos problemas, novas técnicas de otimização e
operadores genéticos, de acordo com a necessidade. O framework desenvolvido
em Java usa conceitos de orientação a objetos que facilitam a extensão; e
• A técnica apresentada e validada neste trabalho é de baixo custo de implantação,
e aproveita os equipamentos já utilizados de programação semafórica de tempo
fixo. Ela se mostrou também eficiente em aplicações do mundo real.
É provável que os bons resultados obtidos neste trabalho sejam reproduzidos em
outros cenários com características semelhantes. Embora o método tenha sido aplicado em duas regiões de Belo Horizonte (MG), ele foi projetado para ser facilmente
estendido e adotado para outras regiões. Espera-se que essas contribuições com o
problema de programação semafórica e com a área de engenharia de tráfego estimulem a aplicação de algoritmos evolucionários multiobjetivo para realizar a programação
semafórica. Além disso, espera-se que os governos municipais atentem para tais propostas de baixo custo que têm contribuído para mitigar um problema que se agrava a
cada dia em todas as cidades.
6.2
Publicações
Os seguintes trabalhos originados nesta dissertação foram publicados e apresentados em conferências:
1. COSTA, B. C.; ALMEIDA, P. E. M. Geração de Tempos Semafóricos em SIG
Convencionais Utilizando Abordagem Multiobjetivo. In: 18o Congresso Brasileiro
de Transporte e Trânsito (CBTT). Rio de Janeiro: Anais do CBTT, 2011.
2. COSTA, B. C.; ALMEIDA, P. E. M.; CALDEIRA, E. Traffic Lights Timing Inside
Microregion Simulator Using Multiobjective Optimization. In: Proceedings of the
2011 IEEE Congress on Evolutionary Computation. New Orleans, USA: IEEE,
2011.
6.3 Trabalhos Futuros
118
3. COSTA, B. C.; ALMEIDA, P. E. M.; CARRANO, E. G. Programação Semafórica
em Microrregiões Utilizando Otimização Multiobjetivo e Simulação Microscópica.
In: 17o Congresso Panamericano de Engenharia de Trânsito, Transporte e Logística (PANAM). Santiago, Chile: Anais do PANAM, 2012.
6.3
Trabalhos Futuros
As pesquisas na área de engenharia de tráfego têm muito a evoluir, sobretudo,
com as diversas inovações computacionais atuais. Neste aspecto, durante a execução deste trabalho, algumas melhorias e inovações foram identificadas, as quais não
puderam ser implementadas por não estar efetivamente dentro do escopo do trabalho
proposto.
Em relação à programação semafórica no GISSIM-TL, propõe-se:
• Testar outras funções objetivo para avaliar os planos semafóricos. Dentre as
funções mais utilizadas, estão o número de paradas, a média de atrasos, e o
tamanho da fila de veículos;
• Usar um método para otimizar as defasagens do plano semafórico, assim como
as sequências dos estágios dos ciclos em cada grupo semafórico desse plano;
• Realizar a programação de múltiplas microrregiões conjuntamente para obter os
resultados para uma região inteira;
• Aplicar outros operadores para as técnicas de inteligência computacional utilizadas para a geração de tempos;
• Construir um operador de busca local para melhorar os resultados;
• Procurar outros problemas existentes na literatura e aplicar a técnica MBVLNSGA2 para comparar os resultados;
• Testar outros algoritmos evolucionários multiobjetivo e compará-los a essa proposta;
• Testar essa abordagem em outras microrregiões, como em interseções isoladas
para verificar o comportamento do MBVL-NSGA2 se comparado a outros métodos; e
6.3 Trabalhos Futuros
119
• 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;
Em relação ao simulador GISSIM, propõe-se:
• Adicionar veículos diferentes à simulação, como, por exemplo, ônibus, caminhões, motocicletas;
• O fato do simulador microscópico gastar muito tempo na simulação quando se
tem uma área grande é um problema grande. Deve-se testar outros tipos de
modelagem para a simulação, como, por exemplo, criar um simulador em um
ambiente distribuído, em que cada entidade (junções e veículos) sejam tratadas
separadamente por diferentes núcleos de processamento do sistema; e
• Validar o simulador GISSIM, comparando os resultados gerados com outros simuladores microscópicos existentes.
120
Referências
ABRAHAM, A.; JAIN, L. Evolutionary Multiobjective Optimization. In:
.
Evolutionary Multiobjective Optimization: Theorical Advances and Applications. 1 ed.
USA: Springer, 2005. p. 1–6.
ALLSOP, R.; CHARLESWORTH, J. Traffic in a Signal-Controlled road Network - An
Example of Different Signal Timings Including Different Routing. Traffic Engineering
and Control, v. 18, n. Analytic, 1977.
ALVAREZ, I.; POZNYAK, A.; MALO, A. Urban traffic control problem via a game theory
application. In: 46th IEEE Conference on Decision and Control. New Orleans: IEEE
Control Systems Society, 2007. p. 2957–2961.
AZIMIRAD, E.; PARIZ, N.; SISTANI, M.-B. N. A Novel Fuzzy Model and Control of
Single Intersection at Urban Traffic Network. IEEE Systems Journal, v. 4, n. 1, p.
107–111, 2010.
BASKAN, O.; HALDENBILEN, S. Ant Colony Optimization Approach for Optimizing
Traffic Signal Timings. 2011.
BAZZAN, A. A Game-Theoretic Approach to Distributed Control of Traffic Signals.
In: Proceedings of the First International Conference on Multiagent Systems. San
Francisco: AAAI Press, 1995. p. 439.
BAZZAN, A. L. C. A Distributed Approach for Coordination of Traffic Signal Agents.
Autonomous Agents and Multi-Agent Systems, v. 10, n. 2, p. 131–164, 2005.
BHTRANS. Sistema de Informações da Mobilidade Urbana de Belo Horizonte. Belo
Horizonte, 2011.
BINGHAM, E. Reinforcement learning in neurofuzzy traffic signal control. European
Journal of Operational Research, Elsevier, v. 131, n. 2, p. 232–241, 2001.
BONNESON, J.; SUNKARI, S.; PRATT, M. Traffic Signal Operations Handbook.
Texas: Texas Department of Transportation, 2009.
CARRANO, E.; MOREIRA, L.; TAKAHASHI, R. A New Memory Based Variable-Length
Encoding Genetic Algorithm for Multiobjective Optimization. In: TAKAHASHI, R. et
al. (Ed.). Evolutionary Multi-Criterion Optimization. Berlin: Springer, 2011, (Lecture
Notes in Computer Science, v. 6576). p. 328–342.
CASAS, J. et al. Traffic Simulation with Aimsun. In: BARCELÓ, J. (Ed.). Fundamentals
of Traffic Simulation. New York: Springer, 2010, (International Series in Operations
Research & Management Science, v. 145). p. 173–232.
Referências
121
CERVANTES, S. G. et al. ATEFI - A Descentralized Fix Time Algorithm for Signal
Control. Semina : Exact and Technologies Science, v. 30, n. 1, p. 41–50, 2009. ISSN
16765451.
CET-SP. Portaria 061/2010 do Departamento de Operação do Sistema Viário (São
Paulo). maio 2010.
CEYLAN, H.; BELL, M. Traffic signal timing optimisation based on genetic algorithm
approach, including drivers’ routing. Transportation Research Part B: Methodological,
Elsevier, v. 38, n. 4, p. 329–342, 2004.
CHENG, S.; EPELMAN, M.; SMITH, R. CoSIGN: A Parallel Algorithm for Coordinated
Traffic Signal Control. IEEE Transactions on Intelligent Transportation Systems, v. 7,
n. 4, p. 551–564, 2006.
CHIU, S. Adaptive Traffic Signal Control Using Fuzzy Logic. In: Proceedings on the
Second IEEE International Conference on Fuzzy Systems. San Francisco, California:
IEEE, 1993. v. 2, p. 1371–1376.
CHOU, C.-H.; TENG, J.-C. A Fuzzy Logic Controller for Traffic Junction Signals.
Information Computer Science, Elsevier Science Inc., New York, NY, v. 143, n. 1-4, p.
73–97, jun. 2002.
CHOY, M.; SRINIVASAN, D.; CHEU, R. Neural networks for continuous online learning
and control. IEEE Transactions on Neural Networks, IEEE, v. 17, n. 6, p. 1511–1531,
2006.
CHOY, M. C.; SRINIVASAN, D.; CHEU, R. L. Cooperative, hybrid agent architecture for
real-time traffic signal control. IEEE Transactions on Systems, Man, and Cybernetics,
Part A, v. 33, n. 5, p. 597–607, 2003.
COELLO, C. A. A Comprehensive Survey of Evolutionary-Based Multiobjective
Optimization Techniques. Knowledge and Information Systems, v. 1, p. 269–308,
1999.
COELLO, C. A. An Updated Suvey of Evolutionary Multiobjective Optimization
Techniques: State of the Art and Future Trends. In: IEEE Congress on Evolutionary
Computation. Washington D. C.: IEEE Service Center, 1999. v. 1, p. 3–13.
COELLO, C. A. An Updated Survey of GA-Based Multiobjective Optimization
Techniques. ACM Computing Surveys, v. 32, n. 2, p. 109–143, 2000.
COELLO, C. A. Recent Trends in Evolutionary Multiobjective Optimization. In:
Evolutionary Multiobjective Optimization: Theorical Advances and Applications.
London: Springer-Verlag, 2005. p. 7–32.
.
COELLO, C. A.; CHRISTIANSEN, A. D. Two New GA-based Methods for Multiobjective
Optimization. Civil Engineering Systems, v. 15, n. 3, p. 207–243, 1998.
COELLO, C. A.; LAMONT, G. B. An Introduction to Multi-Objective Evolutionary
Algorithms and Their Applications. In:
. Applications of Multi-Objective
Evolutionary Algorithms. Singapore: World Scientific, 2004. p. 1–28.
Referências
122
COELLO, C. A. C.; PULIDO, G. T. A Micro-Genetic Algorithm for Multiobjective
Optimization. In: ZITZLER, E. et al. (Ed.). First International Conference on
Evolutionary Multi-Criterion Optimization. Verlag: Springer, 2001. (Lecture Notes in
Computer Science No 1993), p. 126–140.
CONTRAN. Manual Brasileiro de Sinalização de Trânsito. Brasília: Câmara Temática
de Engenharia de Tráfego, da Sinalização e da Via (CONTRAN), 2012.
CORNE, D. W.; KNOWLES, J. D.; OATES, M. J. The Pareto Envelope-based
Selection Algorithm for Multiobjective Optimization. In: SCHOENAUER, M. et al.
(Ed.). Proceedings of the Parallel Problem Solving from Nature VI Conference. Paris,
France: Springer, 2000. (Lecture Notes in Computer Science No 1917), p. 839–848.
COSTA, B. C.; ALMEIDA, P. E. M.; CALDEIRA, E. Traffic Lights Timing Inside
Microregion Simulator Using Multiobjective Optimization. In: Proceedings of the 2011
IEEE Congress on Evolutionary Computation. New Orleans, USA: IEEE, 2011.
COSTA, B. C.; ALMEIDA, P. E. M.; CARRANO, E. G. Programação Semafórica em
Microrregioes Utilizando Otimização Multiobjetivo e Simulação Microscópica. In:
17o Congresso Panamericano de Engenharia de Trânsito, Transporte e Logística
(PANAM). Santiago, Chile: Anais do PANAM, 2012.
DACIERNO, L.; GALLO, M.; MONTELLA, B. An Ant Colony Optimisation (ACO)
Algorithm for Solving the Local Optimisation of Signal Settings (loss) Problem on
Real-Scale Networks. In: Proceedings of the 12th World Congress on Transportation
Research. Lisbon, Portugal: WCTR, 2010.
DEB, K. Solving Goal Programming Problems Using Multi-Objective Genetic
Algorithms. In: 1999 Congress on Evolutionary Computation. Piscataway: IEEE
Service Center, 1999. p. 77–84.
.
DEB, K. Introduction to Evolutionary Multiobjective Optimization. In:
Multiobjective Optimization. Interactive and Evolutionary Approaches. USA: Springer,
2008. v. 5252, p. 59–96.
DEB, K. et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGAII. IEEE
Transactions on Evolutionary Computation, v. 6, n. 2, p. 182–197, abr. 2002.
DENATRAN. Manual de Semáforos. 2 ed. Brasília: Departamento Nacional de
Trânsito, 1984.
DOWNIE, A. The World’s Worst Traffic Jams. abr. 2008. Time Magazine - Postcard
from São Paulo.
EFRON, B.; TIBSHIRANI, R. J. An Introduction to the Bootstrap. London: Chapman e
Hall, 1993.
ERICKSON, M.; MAYER, A.; HORN, J. The Niched Pareto Genetic Algorithm 2
Applied to the Design of Groundwater Remediation Systems. In: ZITZLER, E. et al.
(Ed.). First International Conference on Evolutionary Multi-Criterion Optimization.
Verlag: Springer, 2001. (Lecture Notes in Computer Science No 1993), p. 681–695.
Referências
123
FITZPATRICK, K.; WOOLDRIDGE, M.; BLASCHKE, J. Urban Intersection Design
Guide: Volume I - Guidelines. Texas: Texas Transportation Institute, 2005.
FONSECA, C. M.; FLEMING, P. J. Genetic Algorithms for Multiobjective Optimization:
Formulation, Discussion and Generalization. In: Proceedings of the Fifth International
Conference. San Mateo: Morgan Kaufmann Publishers, 1993. p. 416–423.
FOY, M. D.; BENEKOHAL, R. F.; GOLDBERG, D. E. Signal Timing Determination
Using Genetic Algorithms. Transportation Research Record - Highway Operations,
Capacity, and Traffic Control, n. 1365, p. 108–115, 1992.
GIPPS, P. A model for the structure of lane-changing decisions. Transportation
Research Part B: Methodological, v. 20, n. 5, p. 403–414, 1986.
GOKULAN, B. P.; SRINIVASAN, D. Distributed Geometric Fuzzy Multiagent Urban
Traffic Signal Control. IEEE Transactions on Intelligent Transportation Systems, v. 11,
n. 3, p. 714–727, 2010.
GOLDBERG, D. E. Genetic Algorithms in Search, Optimization and Machine
Learning. Reading, MA: Addison-Wesley Publishing Company, 1989.
GUBERINIC, S.; SENBORN, G.; LAZIC, B. Optimal Traffic Control - Urban
Intersections. 1 ed. London: CRC Press, 2008. ISBN 9781420062687.
GUOJIANG, S.; YOUXIAN, S. Fuzzy neural network control technique and its
application in a complex intersection. In: International Conference on Neural
Networks and Brain. China: IEEE, 2005. v. 2, p. 970–974.
HADI, M.; WALLACE, C. Hybrid genetic algorithm to optimize signal phasing and
timing. Transportation Research Record, TRB, Washington, DC, n. 1421, p. 104–112,
1993.
HAJELA, P.; LIN, C. Y. Genetic Search Strategies in Multicriterion Optimal Design.
Structural Optimization, v. 4, p. 99–107, 1992.
HE, J.; HOU, Z. Ant colony algorithm for traffic signal timing optimization. Advances in
Engineering Software, Elsevier, v. 43, 2011.
HENRY, J.; FARGES, J.; GALLEGO, J. Neuro-fuzzy techniques for traffic control.
Control Engineering Practice, Elsevier, v. 6, n. 6, p. 755–761, 1998.
HONG, Y. S. et al. Estimation of optimal green time simulation using fuzzy neural
network. In: IEEE International Fuzzy Systems Conference. USA: IEEE, 1999. v. 2,
p. 761–766.
HORN, J.; NAFPLIOTIS, N.; GOLDBERG, D. E. A Niched Pareto Genetic Algorithm
for Multiobjective Optimization. In: Proceedings of the First IEEE Conference on
Evolutionary Computation. Piscataway: IEEE Service Center, 1994. v. 1, p. 82–87.
HU, H.; GAO, Y.; YANG, X. Multi-objective Optimization Method of Fixed-Time
Signal Control of Isolated Intersections. In: Proceedings of the 2010 International
Conference on Computational and Information Sciences. Washington, DC: IEEE
Computer Society, 2010. p. 1281–1284.
Referências
124
JUSTESEN, P. Multi-objective Optimization Using Evolutionary Algorithms. Denmark,
jan. 2009.
KESUR, K. Advances in genetic algorithm optimization of traffic signals. Journal of
Transportation Engineering, v. 135, p. 160, 2009.
KIM, J. A fuzzy logic control simulator for adaptive traffic management. In:
Proceedings of the Sixth IEEE International Conference on Fuzzy Systems.
Barcelona, Spain: IEEE, 1997. v. 3, p. 1519–1524.
KNOWLES, J. D.; CORNE, D. W. Approximating the Nondominated Front Using the
Pareto Archived Evolution Strategy. Evolutionary Computation, v. 8, n. 2, p. 149–172,
2000.
KOONCE, P. Traffic Signal Timing Manual. USA: U.S. Department of Transportation,
2008.
KOSONEN, I. Multi-agent fuzzy signal control based on real-time simulation .
Transportation Research Part C: Emerging Technologies, v. 11, p. 389–403, 2003.
LAMMER, S.; HELBING, D. Self-control of traffic lights and vehicle flows in urban road
networks. Journal of Statistical Mechanics: Theory and Experiment, v. 2008, p. 1–30,
abr. 2008.
LEE, J.-H.; LEE-KWANG, H. Distributed and cooperative fuzzy controllers for traffic
intersections group. IEEE Transactions on Systems, Man, and Cybernetics, Part C,
v. 29, n. 2, p. 263–271, 1999.
LO, H. K.; CHOW, A. H. F. Traffic adaptive control for oversaturated isolated
intersections. Journal of transportation engineering, v. 130, n. 466, 2004.
LÓPEZ, S. Artificial neural networks as useful tools for the optimization of the relative
offset between two consecutive sets of traffic lights. Lecture Notes in Computer
Science, v. 1607, p. 795–804, 1999.
LUNA, M. Sobre o Fluxo de Saturação - Conceituação, Aplicação, Determinação e
Variação. Dissertação (Mestrado) — Universidade Federal do Ceará, set. 2003.
MA, W.; GENG, D.; YAN, Y. Multi-Phase Fuzzy Control of Single Intersection in Traffic
System Based on Genetic Algorithm. International Journal of Innovative Computing,
Information and Control, v. 8, n. 5(A), p. 3387–3397, maio 2012.
MASTERTON, T.; TOPIWALA, D. Multi-Agent Traffic Light Optimisation and
Coordination. Thales Research and Technology, VCS081002, p. 1–13, nov. 2008.
MEMON, G. Q.; BULLEN, A. G. R. Multivariate Optimization Strategies for Real-Time
Traffic Control Signals. Journal of the Transportation Research Board, Transportation
Research Board, USA, v. 1554, p. 36–42, 1996.
MURAT, Y. S.; GEDIZLIOGLU, E. A fuzzy logic multi-phased signal control model for
isolated junctions. Transportation Research Part C: Emerging Technologies, v. 13,
n. 1, p. 19–36, 2005.
Referências
125
NETO, T. S.; ALMEIDA, P. E. M. 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, Belo Horizonte, MG, mar. 2009.
NORRIS, S. R.; CROSSLEY, W. A. Pareto-Optimal Controller Gains Generated by A
Genetic Algorithm. In: AIAA 36th Aerospace Sciences Meeting and Exhibit. Reno,
Nevada: AIAA, 1998.
ODA, T. et al. Optimization of signal control parameters using a genetic algorithm.
In: Abstracts of the Third World Congress on Intelligent Transport Systems. Orlando,
Florida: World Scientific, 1996.
OLIVEIRA, D. de; BAZZAN, A. Um Estudo de Coordenação Dinâmica de Agentes
Aplicado ao Gerenciamento de Tráfego Veicular Urbano. Dissertação (Mestrado) —
Universidade Federal do Rio Grande do Sul, 2005.
OLIVEIRA, D. de; BAZZAN, A. L. C. Traffic Lights Control with Adaptive Group
Formation Based on Swarm Intelligence. In: DORIGO, M. et al. (Ed.). ANTS
Workshop. USA: Springer, 2006. (Lecture Notes in Computer Science, v. 4150), p.
520–521.
OLIVEIRA, F. B.; ALMEIDA, P. E. M. Geração de Tempos Semafóricos Utilizando
Inteligência Computacional em SIG Convencionais. Dissertação (Mestrado) — Centro
Federal de Educação Tecnológica de Minas Gerais, 2009.
OLIVEIRA, F. B.; ALMEIDA, P. E. M. Integrating Computational Intelligence,
Microsimulation and Semaphore Regulation into Conventional GIS Software. In: .
Lisbon: WCTR, 2010. p. p. 1–18.
OSYCZKA, A. Multicriteria optimization for engineering design. In:
Optimization. USA: Academic Press, 1985. p. 193–227.
. Design
PARK, B. Development of genetic algorithm-based signal optimization program for
oversaturated intersections. Tese (Doutorado) — Texas A&M University, 1998.
PARK, B.; SCHNEEBERGER, J. D. Evaluation of Traffic Signal Timing Optimization
Methods Using a Stochastic and Microscopic Simulation Program. Charlottesville,
Virginia, nov. 2002.
PARK, B. et al. Development and Evaluation of GA-Based Time-of-Day Intervals
Optimization Program for Traffic Signal Control. Charlottesville, Virginia, dez. 2003.
PÉRIAUX, J.; SEFRIOUI, M.; MANTEL, B. GA Multiple Objective Optimization
Strategies for Electromagnetic Backscattering. In:
. Genetic Algorithms and
Evolution Strategies in Engineering and Computer Science. Recent Advances and
Industrial Applications. England: John Wiley and Sons, 1997. cap. 11, p. 225–243.
PILLAI, R.; RATHI, A. A Restricted Branch-And-Bound Approach for Generating
Maximum Bandwith Signal Timing Plans for Traffic Networks. Transportation Research
Part B: Methodological, Elsevier Science Ltd, v. 32, n. 8, p. 517–529, 1998.
PORCHE, I.; LAFORTUNE, S. A Game-theoretic Approach to Signal Coordination.
1998.
Referências
126
PUTHA, R.; QUADRIFOGLIO, L.; ZECHMAN, E. Comparing ant colony optimization
and genetic algorithm approaches for solving traffic signal coordination under
oversaturation conditions. Computer-Aided Civil and Infrastructure Engineering, Wiley
Online Library, v. 27, n. 1, p. 14–28, 2012.
RAO, S. S. Game Theory Approach for Multiobjective Structural Optimization.
Computers and Structures, v. 25, n. 1, p. 119–127, 1987.
RENFREW, D. Traffic signal control with ant colony optimization. Master’s Theses and
Project Reports, p. 190, 2009.
RENFREW, D.; YU, X.-H. Traffic Signal Control with Swarm Intelligence. In:
Proceedings of the 2009 Fifth International Conference on Natural Computation.
Washington, DC: IEEE Computer Society, 2009. v. 3, p. 79–83.
ROBERTSON, D. I. TRANSYT - A Traffic Network Study Tool. Crowthorne, 1969.
ROGERS, J. L. A Parallel Approach to Optimum Actuator Selection with a Genetic
Algorithm. In: AIAA Guidance, Navigation, and Control Conference. Denver, CO:
AIAA, 2000.
ROOZEMOND, D. A. Using intelligent agents for pro-active, real-time urban
intersection control. European Journal of Operational Research, Elsevier Science Bv,
v. 131, n. 2, p. 293–301, jun 2001.
ROUPHAIL, N. M.; PARK, B. B.; SACKS, J. Direct Signal Timing Optimization:
Strategy Development and Results. XI Pan American Conference in Traffic and
Transportation Engineering, nov. 2000.
SAITO, M.; FAN, J. Artificial neural network–based heuristic optimal traffic signal
timing. Computer-Aided Civil and Infrastructure Engineering, Wiley Online Library,
v. 15, n. 4, p. 293–307, 2000.
SAKA, A. A.; ANANDALINGAM, G.; GARBER, N. J. Traffic signal timing at isolated
intersections using simulation optimization. In: Proceedings of the 18th conference
on Winter simulation. New York: ACM, 1986. p. 795–801.
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. IEEE
Transactions on Evolutionary Computation, v. 12, n. 1, p. 25–40, fev. 2008.
SANCHEZ, J. J.; MORENO, M. J. G.; ROYO, E. R. Traffic Signal Optimization in
"La Almozara"District in Saragossa Under Congestion Conditions, Using Genetic
Algorithms, Traffic Microsimulation, and Cluster Computing. IEEE Transactions on
Intelligent Transportation Systems, v. 11, n. 1, p. 132–141, 2010.
SCHAFFER, J. D. Multiple Objective Optimization with Vector Evaluated Genetic
Algorithms. In: Proceedings of the First International Conference on Genetic
Algorithms. Hillsdale, NJ: Lawrence Erlbaum, 1985. p. 93–100.
SHAMSHIRBAND, S. S. et al. Coordination between Traffic Signals Based on
Cooperative. World Applied Sciences Journal, v. 5, n. 5, p. 525–530, 2008.
Referências
127
SHEFFI, Y.; POWELL, W. B. Optimal Signal Settings Over Transportation Networks.
Journal of Transportation Engineering, v. 109, n. 6, p. 824–839, nov. 1983.
SHEN, G.; KONG, X. Study on road network traffic coordination control technique with
bus priority. Trans. Sys. Man Cyber Part C, IEEE Press, Piscataway, NJ, USA, v. 39,
n. 3, p. 343–351, maio 2009.
SINGH, L.; TRIPATHI, S.; ARORA, H. Time Optimization for Traffic Signal Control
Using Genetic Algorithm. International Journal of Recent Trends in Engineering, v. 2,
n. 2, p. 4–6, nov 2009.
SPALL, J.; CHIN, D. Traffic-responsive signal timing for system-wide traffic control.
Transportation Research Part C: Emerging Technologies, Elsevier, v. 5, n. 3-4, p.
153–163, 1997.
SRIDHAR, J.; RAJENDRAN, C. Scheduling in Flowshop and Cellular Manufacturing
Systems with Multiple Objectives - A Genetic Algorithmic Approach. Production
Planning and Control, v. 7, n. 4, p. 374–382, 1996.
SRINIVAS, N.; DEB, K. Multiobjective function optimization using nondominated
sorting genetic algorithms. Evolutionary Computing, v. 2, n. 3, p. p. 221–248, 1995.
SRINIVASAN, D.; CHOY, M. C. Cooperative multi-agent system for coordinated traffic
signal control . IEEE Proceedings on Intelligent Transportation System, v. 153, n. 1,
mar. 2006.
SRINIVASAN, D.; CHOY, M. C.; CHEU, R. L. Neural networks for real-time traffic
signal control. IEEE Transactions on Intelligent Transportation Systems, IEEE, v. 7,
n. 3, p. 261–272, sep 2006.
SUN, D.; BENEKOHAL, R. F.; WALLER, S. T. Multiobjective Traffic Signal Timing
Optimization Using Non-dominated Sorting Genetic Algorithm. In: Proceedings of
the Intelligent Vehicles Symposium IEEE. Piscataway: IEEE Service Center, 2003. p.
198–203.
TAKAHASHI, R. H. C. Otimização Escalar e Vetorial. Belo Horizonte: Universidade
Federal de Minas Gerais: Departamento de Matemática, 2007.
TONG, G.; CUI, F.; FAN, C. Genetic Algorithm and Its Application in the Realtime
Traffic Signal Optimization Control. In: IEEE. 6th International Conference on ITS
Telecommunications Proceedings. China: ITST, 2006. p. 86–89.
TRABIA, M. B.; KASEKO, M. S.; M., A. A Two-Stage Fuzzy Logic Controller for Traffic
Signals. Transportation Research Part C: Emerging Technologies, v. 7, p. 353–367,
1999.
TRB. Highway Capacity Manual 1965. USA: Highway Research Board of the Division
of Engineering and Industrial Research, National Academy of Sciences-National
Research Council, 1965.
TRB. Highway Capacity Manual 2000. USA: Transportation Research Board, 2000.
Referências
128
TRB. National Cooperative Highway Research Program: Traffic Signal Retiming
Practices in the United States. USA: Transportation Research Board, 2010.
TURKY, A. M.; AHMAD, M. S.; YUSOFF, M. Z. M. The Use of Genetic Algorithm
for Traffic Light and Pedestrian Crossing Control. International Journal of Computer
Science and Network Security, v. 9, n. 2, p. 88–96, fev. 2009.
VENUGOPAL, V.; NARENDRAN, T. T. A Genetic Algorithm Approach to the
Machine-Component Grouping Problem with Multiple Objectives. Computers and
Industrial Engineering, v. 22, n. 4, p. 469–480, 1992.
VOGEL, A.; GOERICK, C.; SEELEN, W. Evolutionary algorithms optimizing traffic
signal operation. In: European Symposium on Intelligent Techniques. Germany:
ESIT, 2000. p. 83–91.
WEBSTER, F. V. Traffic Signal Settings. Road Research Technical Report, n. 39,
1958.
WELCH, B. L. The generalization of "Student’s"problem when several different
population variances are involved. Biometrika, v. 34, n. 1–2, p. 28–35, 1947.
WIENKE, P. B.; LUCASIS, C.; KATEMAN, G. Multicriteria Target Optimization of
Analytical Procedures Using a Genetic Algorithm. Analytical Chimica Acta, v. 265,
n. 2, p. 211–225, 1992.
WILSON, P. B.; MACLEOD, M. D. Low Implementation Cost IIR Digital Filter Design
Using Genetic Algorithms. In: IEEE Workshop on Natural Algorithms in Signal
Processing. Chelmsford, UK: IEEE, 1993. p. 4/1–4/8.
XIE, X. et al. Self-Scheduling Agents for Real-Time Traffic Signal Control. 5000
Forbes Avenue, fev. 2011.
YAN, F.; DRIDI, M.; El Moudni, A. Control of traffic lights in intersection: A new branch
and bound approach. In: 2008 International Conference on Service Systems and
Service Management. Australia: IEEE, 2008. p. 1–6.
YUEN, S. Y.; CHOW, C. K. A Genetic Algorithm That Adaptively Mutates and Never
Revisits. IEEE Transactions on Evolutionary Computation, v. 13, n. 2, p. 454–472,
abr. 2009.
ZARANDI, M. H. F.; REZAPOUR, S. A Fuzzy Signal Controler for Isolated
Intersections. Journal of Uncertain Systems, v. 3, n. 3, p. 174–182, 2009.
ZEBULUM, R. S.; PACHECO, M. A.; VELLASCO, M. A Multi-Objective Optimisation
Methodology Applied to the Synthesis of Low-Power Operational Amplifiers. In:
CHEURI, I. J.; FILHO, C. A. d. R. (Ed.). Proceedings of the XIII International
Conference in Microelectronics and Packaging. Curitiba, Brazil: SBMicro, 1998. v. 1,
p. 264–271.
ZECHMAN, E. et al. Ant Colony Optimization Algorithm for Signal Coordination of
Oversaturated Traffic Networks. Texas, 2010.
Referências
129
ZITZLER, E. Evolutionary Algorithms for Multiobjective Optimization: Methods and
Applications. Tese (Doutorado) — Swiss Federal Insttute of Technology Zurich, 1999.
ZITZLER, E.; LAUMANNS, M.; THIELE, L. SPEA2: Improving the Strength Pareto
Evolutionary Algorithm. Zurich, Gloriastrasse 35, CH-8092 Zurich, Switzerland, maio
2001.
ZITZLER, E.; THIELE, L. Multiobjective Optimization Using Evolutionary Algorithms:
A Comparative Case Study and the Strength Pareto Approach. IEEE Transactions on
Evolutionary Computation, v. 3, n. 4, p. 257–271, nov. 1999.