Algor tmos Gen eticos na Sincroniza˘c~ao de Sem aforos de ...

[Pages:21]Algor?itmos Gen?eticos na Sincroniza?ca~o de Sema?foros de Tra^nsito

Andr?e Felipe Goulart Verri Fevereiro de 2011

1

Sum?ario

1 Introdu?c~ao

3

2 Motiva?c~ao

4

2.1 Um Exemplo Simples . . . . . . . . . . . . . . . . . . . . . . . 4

2.2 Complicando . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Modelagem de Tr^ansito

7

3.1 Dire?ca~o Livre . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.2 Parando no Sem?aforos . . . . . . . . . . . . . . . . . . . . . . 8

3.3 Carro-Seguidor . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.3.1 Estabilidade . . . . . . . . . . . . . . . . . . . . . . . . 13

3.4 Unindo os modelos . . . . . . . . . . . . . . . . . . . . . . . . 15

4 Otimiza?c~ao

15

4.1 Algor?itmos Gen?eticos . . . . . . . . . . . . . . . . . . . . . . . 15

4.2 Aplicando . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

4.3 Simulac?~ao e Resultados . . . . . . . . . . . . . . . . . . . . . . 18

4.4 Conclusa~o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2

1 Introdu?c~ao

Sa~o bem conhecidas as dificuldades encontradas pela sociedade nas m?edias e grandes cidades do mundo devido a enorme concentra?ca~o de pessoas. Entre elas, um dos mais preocupantes ?e a quest~ao do deslocamento. O desenvolvimento e conveni^encia dos ve?iculos particulares fez com que a quantidade destes nas ruas crescesse num ritmo muito acelerado de modo que o planejamento log?istico na~o conseguiu acompanhar com a mesma velocidades. As cidades enta~o sofrem com a perda de tempo, dinheiro e com a polui?ca~o causada pelos inacredita?veis congestionamentos que acontecem diariamente.

Muitas pesquisas ja? foram feitas, enta~o, para se n~ao solucionar, pelo menos amenizar a situa?c~ao. O transporte pu?blico, o transporte ferrovia?rio, mesmo o planejamentos log?isticos de cidades inteiras. Este trabalho, n~ao tem preten?ca~o de solucionar o problema totalmente, ele apenas se prop~oe a estudar um pequeno modelo: a rela?ca~o de sincronia entre sem?aforos de tra^nsito.

Este estudo na~o tem a magnitude de resolver os problemas de congestionamentos, na verdade, ele ?e direcionado a melhorar um tra^nsito n~aocongestionado (ou na~o-saturado) para que este n~ao seja interrompido desnecessariamente.

Entretanto, como cada malha rodovia?ria ?e u?nica, ?e muito dif?icil (e caro) fazer ana?lises particulares para implementar uma boa sincronia em toda uma cidade (por exemplo). Por isso, este estudo propo~e-se a abordar o problema usando um m?etodo de otimiza?c~ao estat?istica, os Algor?itmos Gen?eticos. Assim, este estudo visa experimentar a performance dos Algor?itmos Gen?eticos na sincroniza?ca~o de sema?foros, utilizando modelos simples de tra?fego.

O estudo apresenta a inspira?ca~o deste estudo, mostrando alguns casos simples de sincroniza?ca~o e como estes casos podem ser rapidamente complicados. Tamb?em mostra algumas t?ecnicas de modelagem de tra?fego, e como elas podem ser aplicadas em uma simulac?~ao. Ainda, este trabalho apresenta de forma simples a id?eia por tra?s dos Algor?itmos Gen?eticos. Ao fim, temos algumas simulac?~oes de uma situa?ca~o de tr?afego, onde conclu?imos o qu~ao aplica?vel se mostraram tais t?ecnicas.

3

2 Motiva?c~ao

2.1 Um Exemplo Simples

Vamos supor uma via de ma~o u?nica que possua dois cruzamentos (Figura 1). Ambos os cruzamentos sa~o sinalizados com sema?foros e as vias secunda?rias na~o fazem a convers~ao para a via principal. Qual seria uma boa sincronia para eles? Se pensarmos apenas nos ve?iculos que esta~o trafegando pela via principal a resposta ?e bem simples: manter os sema?foros abertos o tempo todo. Mas a?i n~ao ter?iamos motivo para um sem?aforo! Logo fica claro que devemos pensar tamb?em nos ve?iculos que trafegam nas vias secunda?rias.

Figura 1: M~ao u?nica com 2 cruzamentos com sema?foros Analisando a sincronia do sem?aforo 2 em relac?~ao ao sema?foro 1, surge uma id?eia simples. Supondo que ambos os sem?aforos estejam abertos, podemos fechar o sem?aforo 2 algum tempo depois de fechar o sema?foro 1, o suficiente para que os ve?iculos que passaram pelo sema?foro 1 antes deste fechar passem tamb?em pelo sema?foro 2, garantindo que nenhum ve?iculo ira? parar em ambos os sema?foros. Sabendos que nenhum outro ve?iculo passar?a pelo sema?foro 2 at?e que o sem?aforo 1 abra novamente, o sema?foro 2 pode manter-se fechado at?e o sema?foro 1 abrir. Este "algum tempo depois" dependeria principalmente da velocidade m?edia dos carros e da dista^ncia entre os dois sem?aforos. Mesmo assim, ainda ha? o problema de quanto tempo deixar aberto, e

4

quanto tempo deixar fechado cada um dos sem?aforos, o que poderia impedir a suposi?ca~o de que em algum momento ambos os sema?foros estariam abertos.

2.2 Complicando

A situa?ca~o acima parece ter sido resolvida facilmente, usando apenas um pouco de racioc?inio lo?gico, entretanto ?e facil complicar o problema com pequenas modifica?co~es. Se a via principal for uma via de ma~o dupla (Figura 2), a id?eia de abrir os sem?aforos em ordem torna-se inu?til, pois os ve?iculos no sentido contr?ario `a sincroniza?ca~o passara~o em ambos os sema?foros fechados. Ainda, se as vias secunda?rias puderem fazer a conversa~o para entrar na via principal (Figura 3), a hip?otese de que nenhum ve?iculo passar?a pelo sema?foro 2 ap?os o fechamento do sema?foro 1 torna-se falsa. Isso ainda numa situa?ca~o que envolvem apenas uma via principal e dois sema?foros.

Figura 2: M~ao dupla com 2 cruzamentos com sem?aforos Agora vamos supor uma pequena malha via?ria (Figura 4) com quatro vias, quatro cruzamentos, todos sinalizados por sema?foros. Todas as vias possuem duas m~aos, mas elas na~o fazem conversa~o. Note que usando o racioc?inio anterior em que a sincronia de abertura de um sema?foro depende de outro sema?foro como refer^encia, vemos que os quatro sema?foros da nossa malha sa~o todos dependentes entre si. A situa?ca~o complica-se muito mais se adicionarmos a possibilidade de convers~ao, quando come?camos a notar a necessidade de dar maior ou menor import^ancia para algumas trajet?orias em fun?ca~o de outras.

5

Figura 3: M~ao dupla com 2 cruzamentos com sem?aforos

Figura 4: Quatro cruzamentos interligados Notamos como o problema pode ficar consideravelmente complexo para resolver por l?ogica. Assim, este trabalho foi motivado a tentar uma t?ecnica diferente, usando algor?itmos de otimizac?~ao estat?isticos, para chegar em solu?co~es aplica?veis.

6

3 Modelagem de Tr^ansito

Para fazer a otimiza?c~ao do problema, ?e necessa?rio usar um modelo que represente o sistema. Diversos modelos foram criados e s~ao utilizados atualmente e est~ao espalhados pela bibliografia existente sobre o assunto. O livro "Traffic Flow Theories"[1] reu?ne os principais modelos usados atualmente, mostrando suas caracter?isticas e comentando as vantagens e desvantagens de se utilizar cada um deles.

Como a inten?ca~o desse trabalho ?e apenas experimentar a performance dos algor?itmos gen?eticos na sincroniza?ca~o de sem?aforos, sera~o usados modelos simples de tra?fego. O estudo envolver?a a rea?ca~o de ve?iculos com rela?ca~o a sinaliza?ca~o semafo?rica e outros ve?iculos. Excluindo situac?~oes mais complicadas como convers~oes, mudanc?as na velocidade m?axima (entre outras sinaliza?co~es), acidentes, interdi?co~es; diferen?ca de mobilidade entre ve?iculos devido a peso e tamanho (motocicletas, carros e caminh~oes, por exemplo); elementos que afetam o tempo de rea?ca~o dos motoristas como visibilidade, idade e sexo. O estudo sup~oe enta~o uma homogeneidade do tr^ansito.

3.1 Dire?c~ao Livre

Dire?ca~o livre ?e o que chamaremos situa?c~ao onde estudamos o comportamento de um u?nico ve?iculo numa via, dado apenas um limite de velocidade ma?ximo. Supondo tamb?em que cada ve?iculo seja respeitoso quanto `as leis de tra^nsito e saiba exatamente a que velocidade se encontra, ou seja, excluindo os erros de medi?ca~o do ve?iculo e a aproximac?~ao do mostrador.

Assim consideramos que o motorista que parte de qualquer velocidade abaixo da m?axima acelera de modo "na~o apressado", ou seja, ele n~ao realiza acelera?c~oes ou desacelera?c~oes bruscas, at?e atingir a velocidade m?axima e seguira? assim indefinidamente. Segundo o ITE (Institute of Transportation Engineers)[2], essa acelera?ca~o ?e de aproximadamente 1m/s2, ou seja, a velocidade do ve?iculo varia em (3, 6km/h) a cada segundo. Essa suposi?c~ao ?e uma aproxima?ca~o ao comportamento da acelera?c~ao dos ve?iculos, pois ela na realidade n~ao ?e uniforme.

Assim, a velocidade do ve?iculo V em func?~ao do tempo, em m/s, ser?a dada por:

7

V = V0 + t, se V < Vmax V = Vmax , se V = Vmax onde: V0 ?e a velocidade inicial do ve?iculo (em m/s) Vmax ?e o limite de velocidade ma?ximo (em m/s) t ?e o tempo (em s)

Note que como estamos supondo que o motorista ?e respeitoso a`s leis de tra^nsito, nunca teremos V0 > Vmax e n~ao existe o caso V > Vmax.

3.2 Parando no Sem?aforos

A rea?c~ao dos motoristas quanto a sinaliza?ca~o semafo?rica ja? apresenta uma complica?ca~o: a sinaliza?ca~o ?e vari?avel em rela?ca~o ao tempo. Portanto a resposta na~o depende apenas de qual ?e a sinaliza?ca~o, mas em que posi?c~ao o ve?iculo se encontra no momento de uma mudanc?a desta. Assim, para melhor representar as situa?c~oes, dividiremos o modelo de acordo com a reac?~ao do motorista:

Sema?foro Aberto: O caso mais simples de todos por n~ao oferecer obstru?ca~o. O ve?iculo mant?em seu movimento normal padra~o.

Sema?foro Fechado: Quando o motorista se depara com esse cena?rio, ele analisa a dista^ncia que se encontra do sema?foro, bem como a sua capacidade de frear, baseado em experi^encias passadas e seu pr?oprio senso de in?ercia. No nosso modelo, o motorista calcula a partir de que ponto ele deve come?car a frear de modo "na~o apressado" para parar totalmente a tempo. Este ponto ?e representado na Figura 5 (Linhas de Refer^encias) como "Linha 1".

Mudan?ca Aberto Fechado: Nesta situac?~ao, se o ve?iculo estiver antes da Linha 1, o motorista age como no caso acima. Entretanto, se ja? estiver depois desde ponto, ele dever?a desacelerar mais bruscamente ou na~o conseguira? frear a tempo. O motorista calcula o quanto deve frear o ve?iculo e responde de acordo. Entretanto, ha? um outro ponto a partir do qual o motorista n~ao mais consegue parar antes do sema?foro, ou a desacelerac?~ao ser?a t~ao brusca de podera? criar uma situa?ca~o de risco. Este ponto ?e representado da Figura 5

8

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download