Caraterização de estradas em tempo real através de métodos preditivos

FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO Caraterização de estradas em tempo real através de métodos preditivos Joaquim Rui Rocha Barros Mestrado Integrado em Engenharia Informática e Computação Orientador: Rosaldo José Fernandes Rossetti Co-orientador: Miguel Ramos de Araújo 14 de julho de 2015 Caraterização de estradas em tempo real através de métodos preditivos Joaquim Rui Rocha Barros Mestrado Integrado em Engenharia Informática e Computação Aprovado em provas públicas pelo Júri: Presidente: Ana Paula Cunha da Rocha, Professor Auxiliar (PhD) Arguente: Luís Paulo Gonçalves dos Reis, Professor Associado (PhD) Vogal: Rosaldo José Fernandes Rossetti, Professor Auxiliar (PhD) 14 de julho de 2015 Resumo Nos últimos anos, tem-se verificado um crescimento cada vez maior do número de pessoas que visitam as cidades, conduzindo a um aumento do número de veículos que viajam através das principais estradas de acesso. Filas e incidentes cada vez mais frequentes obrigam a uma monitorização alargada da rede, rápida deteção de incidentes e melhores tempos de resposta. Esta situação verifica-se na Via de Cintura Interna (VCI), uma autoestrada em forma de anel que contorna as cidades do Porto e Vila Nova de Gaia. De forma a melhorar o desempenho e a capacidade desta via de acesso, propõe-se o desenvolvimento de algoritmos, métodos ou ferramentas que permitam perceber o estado da rede, bem como identificar a dinâmica e os locais onde se verificam os incidentes. A partir deste processo, pretende-se prever o estado da rede em tempo real com um intervalo máximo de previsão de 30 minutos. Os cálculos a realizar terão como base os dados recolhidos através de sensores em loop instalados ao longo da VCI. A solução desenvolvida deverá ser integrada num sistema de gestão de tráfego que se encontra em funcionamento atualmente. Esta dissertação apresenta alguns conceitos e trabalhos relacionados que seguem as abordagens model-driven edata-driven. Relativamente à primeira abordagem, o foco do estudo situa-se na modelação mesoscópica que permite a representação e simulação de redes rodoviárias com níveis de detalhe e eficiência adequados. No último caso, são referidos alguns conceitos de aprendizagem estatística e algoritmos frequentemente utilizados. Todos estes conceitos suportaram o desenvolvimento de uma framework e de diferentes algoritmos de previsão que serão posteriormente comparados e avaliados. Palavras-chave: trânsito; previsão; model-driven;data-driven; simulação; data mining i ii Abstract Title: Real-time characterization of road networks through predictive methods The increasing number of people visiting cities has led to a greater number of vehicles traveling through main access roads. Queues and more frequent incidents require wider network monitoring, faster incident detection and quicker response times. This situation happens on Via de Cintura Interna (VCI), a highway that surrounds Porto and Vila Nova de Gaia cities. In order to improve performance and capacity of this road, it is proposed the development of algorithms, methods or frameworks which allow to understand network state, dynamics and places where incidents could occur. After completing this process, it should be possible to forecast network state in real-time within a maximum interval of 30 minutes. The resulting computation should be based on data collected by loop sensors installed on VCI. The final solution will be integrated on a traffic management system currently in use. This dissertation presents some concepts and related work following model-driven and datadriven approaches. Relatively to the first approach, study is focused on mesoscopic simulation which allows representation and simulation of road networks and entities with adequate levels of detail and performance. Relatively to data-driven approach, it is referred the statistical learning concept and some frequently used algorithms. All these concepts supported the development of a new framework and different forecasting algorithms which will be compared and assessed. Keywords: traffic; prediction; model-driven; data-driven; simulation; data mining iii iv Agradecimentos Ao meu orientador, Prof. Rosaldo Rossetti, e ao meu co-orientador, Miguel Araújo, por me darem a conhecer diversas áreas de estudo e me motivarem a explorar novas áreas que se mostram relevantes nos dias de hoje. À Armis, por ter facultado informação indispensável à realização deste projeto, permitindo assim explorar diferentes técnicas e conceitos. Ao Alexey Seliverstov, António Garcez, Filipe Oliveira, Nelson Mendes, Tiago Azevedo, Tiago Costa e Tiago Vieira pelas ideias e conhecimentos que complementaram este trabalho. A todos os meus colegas de curso que estiveram ao meu lado nestes últimos 5 anos e com os quais tive a oportunidade de trabalhar e passar bons momentos. Aos meus amigos e à minha família, por me terem apoiado neste caminho e nesta importante etapa da minha vida, estando sempre ao meu lado. Obrigado, Joaquim Barros v CONTEÚDO xii Lista de Figuras 2.1 Diagrama fundamental de fluxo de tráfego . . . . . . . . . . . . . . . . . . . . . 8 2.2 Diagramafluxo-densidade ............................. 8 2.3 Diagrama velocidade-densidade . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4 Diagramavelocidade-fluxo............................. 9 2.5 Diferentes modelos de simulação . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.6 Minimização das medidas de erro MAE e MAPE . . . . . . . . . . . . . . . . . 17 2.7 Minimização da medida de erro RMSE . . . . . . . . . . . . . . . . . . . . . . . 18 3.1 Estruturação do sistema DynaMIT . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.2 Estruturação do sistema DynaSMART . . . . . . . . . . . . . . . . . . . . . . . 22 3.3 Estruturação do sistema TRANSIMS . . . . . . . . . . . . . . . . . . . . . . . . 26 3.4 Processo do algoritmo k-NN de regressão não paramétrico . . . . . . . . . . . . 31 3.5 Esquema do sistema de previsão com recurso ao algoritmo Particle Filter .... 32 3.6 Diagrama de fluxo com perguntas que devem ser consideradas na escolha da abordagemmaisadequada................................ 35 4.1 Exemplo de mapa com apresentação do estado do trânsito . . . . . . . . . . . . . 41 4.2 Interface gráfica da aplicação . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.1 Erro médio quadrado em R para um intervalo de 15 minutos . . . . . . . . . . . 50 5.2 Erro médio quadrado em R para um intervalo de 30 minutos . . . . . . . . . . . 51 5.3 Melhoria média do erro médio quadrado em Rapós integração do estado geral do tempo ........................................ 51 5.4 Melhoria média do erro médio quadrado em Rapós integração da visibilidade . . 53 5.5 Melhoria média do erro médio quadrado em Rapós integração do estado geral do tempoporalgoritmo ................................ 54 5.6 Melhoria média do erro médio quadrado em Rapós integração da visibilidade por algoritmo ...................................... 55 5.7 Erro médio quadrado na aplicação para um intervalo de 15 minutos . . . . . . . . 56 5.8 Erro médio quadrado na aplicação para um intervalo de 30 minutos . . . . . . . . 57 5.9 Erro médio quadrado (com meteorologia) na aplicação para um intervalo de 15 minutos ....................................... 58 5.10 Erro médio quadrado (com meteorologia) na aplicação para um intervalo de 30 minutos ....................................... 59 5.11 Melhoria do erro médio quadrado após utilização de dados meteorológicos para umintervalode15minutos............................. 60 5.12 Melhoria do erro médio quadrado após utilização de dados meteorológicos para umintervalode30minutos............................. 61 xiii LISTA DE FIGURAS 5.13 Melhoria do erro médio quadrado quando não são considerados períodos de incidentes para um intervalo de 15 minutos . . . . . . . . . . . . . . . . . . . . . . 61 5.14 Melhoria do erro médio quadrado quando não são considerados períodos de incidentes para um intervalo de 30 minutos. . . . . . . . . . . . . . . . . . . . . . . 62 5.15 Erro médio quadrado para diferentes estados do tempo . . . . . . . . . . . . . . 62 5.16 Evolução do erro de acordo com a variação temporal do volume . . . . . . . . . 62 5.17 Evolução do erro médio quadrado ao longo de um dia . . . . . . . . . . . . . . . 63 5.18 Evolução do erro médio quadrado ao longo de uma semana . . . . . . . . . . . . 63 B.1 Diagrama de Gantt com o planeamento do projeto . . . . . . . . . . . . . . . . . 81 C.1 Diagrama de packages da solução desenvolvida . . . . . . . . . . . . . . . . . . 83 xiv Lista de Tabelas 3.1 Comparação entre simuladores mesoscópicos . . . . . . . . . . . . . . . . . . . 36 3.2 Comparação entre as diferentes abordagens model-driven ............. 37 3.3 Comparação entre as diferentes abordagens data-driven .............. 38 5.1 Melhores resultados obtidos para a execução do script em Ra 15 e 30 minutos . . 52 5.2 Melhores resultados obtidos através da aplicação . . . . . . . . . . . . . . . . . 52 5.3 Melhores resultados obtidos após introdução de dados meteorológicos na aplicação 53 5.4 Erro médio quadrado máximo registado nos sensores . . . . . . . . . . . . . . . 54 5.5 Correlação entre as variáveis e o erro médio quadrado . . . . . . . . . . . . . . . 57 5.6 Tempo de execução de acordo com o algoritmo e o intervalo de previsão . . . . . 61 xv LISTA DE TABELAS xvi Abreviaturas e Símbolos API Application Programming Interface ATIS Advanced Traveler Information Systems ATMS Advanced Traffic Management Systems BCNN Bayesian Combined Neural Network CORBA Common Object Request Broker Architecture CRM Customer Relationship Management CSV Comma-separated Values DTA Dynamic Traffic Assignment FEUP Faculdade de Engenharia da Universidade do Porto GPS Global Positioning System HMM Hidden Markov Model ITS Intelligent Transportation System k-NN k-Nearest Neighbor LIACC Laboratório de Inteligência Artificial e Ciência de Computadores MAE Mean Absolute Error MAPE Mean Absolute Percentage Error MIT Massachusetts Institute of Technology OD Origem-Destino RMSE Root Mean Square Error SMC Sequential Monte Carlo VCI Via de Cintura Interna UP Universidade do Porto xvii Capítulo 1 Introdução Pretende-se, neste capítulo, introduzir a dissertação, começando por referir o enquadramento da mesma, a formalização do problema e a motivação para a sua resolução. Como conclusão, serão apresentados os objetivos gerais a atingir, a metodologia que será seguida no desenvolvimento deste projeto, a contribuição esperada para a área científica em estudo e também a estrutura deste documento. 1.1 Contexto/Enquadramento Nos últimos anos, tem-se verificado um crescimento cada vez maior do número de pessoas que visitam as cidades. A maioria viaja todos os dias para o seu posto de trabalho ou para ter acesso a diferentes serviços que não estão disponíveis fora das áreas metropolitanas. Existe, assim, a necessidade de recorrer aos meios de transporte públicos ou até à utilização dos seus próprios veículos, conduzindo a um aumento significativo do tráfego existente nas autoestradas e nas principais vias de acesso às cidades. Estas alterações à normal circulação provocam trânsito lento, congestionamento, filas intermináveis, atrasos e acidentes. Todos estes fatores, em conjunto com as condições atmosféricas, trabalhos nas vias e eventos especiais (como por exemplo concertos ou jogos de futebol), têm um impacto significativo no fluxo de trânsito, tornando-se mais difícil o acesso à cidade. Estes problemas acontecem de forma semelhante na Via de Cintura Interna (VCI), uma estrada em forma de anel que constitui uma das principais vias de acesso às cidades do Porto e Vila Nova de Gaia. 1.2 Formalização do problema Tendo em conta as características e as ocorrências registadas na VCI, torna-se necessário implementar um conjunto de algoritmos que permita fornecer informação em tempo real sobre as 1 Introdução condições de tráfego em redes rodoviárias. Desta forma, consegue-se perceber o estado atual das vias, os locais onde se podem verificar maiores constrangimentos e atuar em conformidade. Apesar dos benefícios conseguidos através desta abordagem, considera-se que a prevenção destas ocorrências poderá revelar-se mais eficaz de forma a manter um fluxo de circulação ajustado [BF12]. Assim, a utilização de uma abordagem preditiva poderá trazer maiores vantagens, permitindo gerir o tráfego de forma a evitar congestionamentos, filas de trânsito, atrasos, acidentes e, desta forma, a perda de vidas humanas. Na sequência do exposto, pretende-se a resolução eficaz de dois problemas principais: •Como detetar situações anómalas e quais as razões associadas? •Como prever as condições do tráfego em tempo real numa determinada rede rodoviária? Para a primeira pergunta, importa reconhecer o estado do trânsito, tendo em conta os dados obtidos na via e perceber se se trata de uma situação normal ou anómala. Desta forma, é possível perceber possíveis ocorrências e de que forma os seus efeitos se propagam na rede em estudo. Relativamente à segunda pergunta, é importante perceber se existem trabalhos realizados na área de transportes que permitam prever o tráfego em tempo real, quais as metodologias e algoritmos mais utilizados e de que forma os mesmos podem ser aplicados na previsão do tráfego da VCI. 1.3 Motivação A partir de uma análise ao trânsito da VCI verifica-se que é importante encontrar uma solução que permita compreender o tráfego nesta importante via de acesso e prever eventuais ocorrências que possam surgir. Os sistemas de gestão ativa de tráfego (Active Traffic Management Systems - ATMS) apresentam-se, nos dias de hoje, como uma forma efetiva e de custos reduzidos para monitorização contínua e gestão de redes rodoviárias [Sis12]. Apesar das diversas vantagens associadas, a abordagem wait and see implica uma monitorização 24 horas por dia, elevados custos técnicos e operacionais, dificuldades no acesso aos locais dos acidentes e a execução de operações complexas para a gestão rápida das estradas. Assim, considera-se ser do maior interesse o desenvolvimento de novos algoritmos que permitam perceber como evolui o tráfego e, desta forma, alertar os condutores através dos sistemas de navegação e de informação. Nos últimos anos tem havido bastante interesse por parte da comunidade científica no desenvolvimento de diversas técnicas de simulação e previsão a aplicar em redes rodoviárias. A maioria dos trabalhos desenvolvidos permite perceber de que forma os diversos componentes interagem e condicionam a circulação nas redes. Apesar da qualidade dos resultados obtidos, uma abordagem model-driven implica sempre a execução do simulador o que, para além do custo computacional, poderá não ser suficientemente rápido para que os agentes gestores do tráfego possam atuar. Assim, pretende-se analisar outras abordagens baseadas na análise de dados que permitem obter resultados mais rapidamente (antecipadamente), com um grau de detalhe superior e que permita 2 Introdução reunir dados de outras fontes consideradas relevantes tais como bases de dados de registo de acidentes ou informações sobre condições meteorológicas. A conceção de um sistema de análise e de previsão de tráfego torna-se, por isso, uma maisvalia na gestão de uma rede de estradas. Para além das vantagens diretas obtidas com o sistema descrito, é possível utilizar os sistemas de informação e navegação de forma a modificar o comportamento dos condutores, evitando congestionamentos, filas de trânsito, atrasos e acidentes, conseguindo-se também maximizar a satisfação dos utilizadores. 1.4 Objetivos O objetivo principal desta dissertação consiste no estudo e desenvolvimento de métodos, algoritmos ou ferramentas que permitam avaliar o estado da rede, sendo possível prever as suas condições a curto prazo e em tempo real. Pretende-se, a partir dos dados recolhidos através de sensores instalados na VCI, obter modelos e aplicar técnicas de data mining que permitam estabelecer relações entre as diversas variáveis. Desta forma, deverá ser possível compreender as causas de determinadas ocorrências e de que forma as mesmas se propagam ao longo da rede. O resultado final obtido deverá ser integrado em sistemas de gestão de tráfego que se encontram atualmente em funcionamento. De forma a atingir o objetivo principal indicado anteriormente, pretende-se no decurso desta dissertação atingir os seguintes objetivos específicos: •Estudo dos conceitos e definições necessários no decurso da dissertação, principalmente ligados às abordagens model-driven edata-driven. Para além disso, pretende-se apresentar o estado da arte no que respeita aos trabalhos sobre previsão em redes de transportes. •Estudo da metodologia a adotar e dos requisitos necessários ao desenvolvimento da solução pretendida. •Implementação do protótipo. •Teste do protótipo desenvolvido. •Análise dos resultados obtidos. •Escrita da dissertação. 1.5 Metodologias Tendo em conta os objetivos propostos, o trabalho de investigação inicial constitui a base do desenvolvimento dos algoritmos pretendidos. Por isso, pretende-se, numa primeira fase, perceber quais os conceitos e definições essenciais no estudo e desenvolvimento de sistemas de previsão de tráfego. Será analisada a abordagem model-driven, constituída pelas técnicas de simulação macroscópica, mesoscópica, microscópica e nanoscópica. O foco do estudo dirigir-se-á para as 3 Revisão Bibliográfica: Background 2.2 Modelação e simulação de tráfego Todos os dias são produzidos um elevado número de dados recolhidos através de sensores instalados na VCI, tornando-se difícil o seu processamento e representação. Por isso, torna-se indispensável construir modelos computacionais que permitam representar o tráfego registado nas diferentes vias. A modelação de tráfego permite obter os parâmetros das vias e a forma como os mesmos variam em função de diversos fatores. Pretende-se, nesta secção, apresentar os conceitos fundamentais à modelação do tráfego, os diferentes graus de detalhe e fazer uma referência à simulação a partir destes modelos. 2.2.1 Definição/Conceitos Os primeiros modelos de tráfego surgiram na década de 50, constituindo representações simples pelo facto de não apresentarem muitos detalhes relativos ao estado do tráfego e por não serem rigorosamente percebidos ou provados [BM00]. A simulação, baseando-se nos modelos de tráfego representados computacionalmente, surgiu pela primeira vez com a publicação da dissertação de D. L. Gerlough intitulada Simulation of freeway traffic on a general-purpose discrete variable computer em 1955 na Universidade da Califórnia (Los Angeles). A partir daí verificou-se uma evolução considerável nesta área, tendo por base 5 forças fundamentais: avanços na teoria de tráfego, avanços na tecnologia e nas ferramentas de programação, desenvolvimentos das infraestruturas gerais de informação e a necessidade de obter análises detalhadas sobre os efeitos de determinadas medidas e planos no tráfego [Pur99]. Atualmente, a modelação do tráfego pode ter em conta diversos parâmetros tais como fluxo, velocidade e densidade, integrando técnicas analíticas tais como a análise de oferta-procura, capacidade, ondas de choque (shock-wave) e filas. A lógica associada aos modelos depende das diferentes abordagens adotadas para a representação do tráfego e os modelos obtidos são geralmente utilizados na simulação das condições de tráfego numa determinada área. Existem diversas classificações utilizadas para a distinção dos modelos [Wan96]: •Domínio de aplicação - interseções, artérias, redes urbanas, autoestradas e corredores de autoestradas; •Incerteza do conteúdo - natureza determinística ou estocástica e o horizonte temporal que representa as propriedades estáticas ou dinâmicas; •Taxa de atualização – por intervalo ou por eventos; •Nível de detalhe – macroscópico, mesoscópico, microscópico e nanoscópico. Tendo em conta a evolução do tráfego nos últimos anos, a utilização de simuladores tem permitido estudar modelos cada vez mais complexos do ponto de vista analítico e numérico. Assim, é possível realizar estudos que permitem identificar algumas relações e apresentar de forma visual cenários presentes e futuros. Uma aplicação atual passa pela determinação do impacto de 10 Revisão Bibliográfica: Background determinados fatores, realizar previsões e avaliar o desempenho das infraestruturas existentes ou projetadas. No entanto, este conceito também pode ser aplicado de forma a estudar a qualidade do ar e os níveis de ruído ([TW07], [WBK06]). 2.2.2 Modelos Pretende-se nesta secção apresentar as principais características dos modelos, tendo em conta o nível de detalhe utilizado. São, assim, apresentados os modelos macroscópicos, microscópicos, mesoscópicos e nanoscópicos. 2.2.2.1 Modelação macroscópica Os modelos macroscópicos surgiram na década de 50 e representam o fluxo de trânsito de uma forma agregada. Neste modelo, o tráfego é caraterizado através da taxa de fluxo, densidade espacial de veículos e velocidade média em função da localização e do tempo, permitindo simular estradas com diferentes faixas de rodagem e com uma probabilidade de ultrapassagem associada [PRK11]. Esta modelação tem como principal vantagem a eficiência no tempo de execução, mas, por outro lado, tem como principal desvantagem a baixa precisão (o comportamento individual dos veículos não é modelado). Os modelos macroscópicos podem ser de três ordens, sendo os modelos de primeira e segunda ordem os mais utilizados [FL02]. A modelação macroscópica adequa-se especialmente a grandes redes rodoviárias com estradas longas, lisas e em linha reta. Recomenda-se a utilização de outros modelos de forma complementar para a modelação de rampas de saída, curvas, declives e estreitamentos [Bla08]. 2.2.2.2 Modelação microscópica Ao contrário da modelação macroscópica, os modelos microscópicos caracterizam o fluxo de tráfego tendo em conta os dados e o comportamento individual de cada veículo. As primeiras abordagens (com o nome Car-Following Models) têm origem na década de 50, não existindo a possibilidade de ultrapassagem entre veículos [Bla08]. Na atualidade, os modelos microscópicos permitem, por exemplo, modelar o comportamento de um condutor ao manter uma distância mínima entre dois veículos consecutivos na mesma faixa de rodagem, mudança entre faixas e mudança entre estradas. Existem diversas abordagens, incluindo a modelação discreta na qual os veículos são representados por partículas que se deslocam entre segmentos com comprimento igual à distância mínima entre dois veículos consecutivos [FL02]. O desenvolvimento e aplicação de modelos microscópicos cada vez mais detalhados deveu-se sobretudo à melhoria dos sistemas computacionais verificada nos últimos anos [RLT11] [RL15]. Apesar do aumento de precisão conseguido, estes modelos não são adequados para redes rodoviárias de grande dimensão. 11 Revisão Bibliográfica: Background 2.2.2.3 Modelação mesoscópica A modelação mesoscópica assume-se como uma solução intermédia, reunindo as vantagens conseguidas através modelação macroscópica e da modelação microscópica [PRK11]. Devido à fronteira ténue entre os diferentes modelos, os autores apresentam diferentes perspetivas, tendo em conta o contexto de aplicação. De acordo com Ratrout e Rahman [RR09], os modelos mesoscópicos vêm preencher a falha existente entre os modelos supramencionados, ao descrever os veículos com grande nível de detalhe enquanto que os comportamentos e as interações são descritos de forma menos detalhada. Por outro lado, Fujimoto e Leonard II [FL02] consideram a definição de clusters de veículos e das suas interações. Ainda Schwerdtfeger [Sch] desenvolve o algoritmo DYNEMO que se baseia na simplificação de um modelo microscópico no qual a unidade de fluxo de tráfego é o veículo. Apesar do movimento ser controlado através da média de densidade de tráfego, cada veículo contém informação do seu estado individual (velocidade desejada, destino e posição). Pelo facto de reunir as vantagens dos modelos anteriormente abordados, a modelação mesoscópica permite melhorar o tempo de execução quando comparada com a modelação microscópica, conseguindo-se um bom desempenho em redes com uma dimensão considerável. 2.2.2.4 Modelação nanoscópica A modelação nanoscópica apresenta-se como uma nova tendência, estendendo-se a visão do veículo através da divisão em partes, com a simulação do desempenho das baterias em veículos elétricos [MKS+13] [PRRA12]. Outro objetivo principal é a modelação detalhada da cognição, perceção, decisão e erros do condutor [RR09], permitindo assim que cada veículo reaja (de forma independente) a estímulos provenientes dos veículos vizinhos [BABW13] [DRO06] [FERO08]. Este tipo de modelos são vulgarmente utilizados na simulação e planeamento offline, quando não há a necessidade de obtenção de resultados em tempo real. Figura 2.5: Diferentes modelos de simulação (da esquerda para a direita): macroscópica, microscópica e nanoscópica. No círculo, modelação mesoscópica [SUM]. 12 Revisão Bibliográfica: Background 2.3 Análise de dados Apesar das vantagens conseguidas através da modelação e simulação de redes de transportes, a obtenção de soluções exige sempre algum tempo de cálculo e a calibração de diversos parâmetros, muitas vezes implicando atrasos e impedindo uma rápida atuação dos meios e agentes envolvidos. Assim, para a obtenção de soluções num período de tempo inferior, têm surgido diversas implementações baseadas em análise de dados. De uma forma geral, é possível obter previsões em tempo real através da análise dos dados provenientes dos sensores e considerando outros fatores, tais como a temperatura ou eventos nas proximidades. 2.3.1 Definição/Conceitos Data analytics é caraterizada como uma ciência que permite obter conclusões a partir de informações provenientes de diversas fontes. Esta área tem-se expandido nos últimos anos, sendo neste momento fundamental para que as organizações possam tomar melhores decisões e também para provar modelos ou teorias em diversos domínios. Dependendo dos dados estudados e das informações a obter, existem diferentes subáreas específicas para a análise de dados: •Análise de dados exploratória – tem como foco principal a descoberta de novas características a partir da informação analisada; •Análise de dados confirmatória – o objetivo passa por avaliar se as hipóteses são verdadeiras ou falsas; •Análise de dados qualitativa – esta análise torna-se adequada quando os dados estudados são de tipo não-numérico (palavras, fotografias, vídeo). O termo analytics pressupõe a compreensão e a construção de informação de acordo com o domínio em estudo. Está presente nas aplicações de CRM, prevenção de fraudes, identificação de situações de roubo (processamento de transações a partir de cartões de crédito) e, por exemplo, no reconhecimento de padrões de compra de um utilizador [Rou]. Devido às semelhanças entre os termos, torna-se importante distinguir data analytics edata mining. No primeiro caso, o foco da análise concentra-se no processo de inferência e de obtenção de conclusões enquanto que, no segundo caso, o objetivo principal passa pela análise de grandes conjuntos de dados de forma a encontrar novos padrões ou relações desconhecidas. As técnicas de data analytics, para além das áreas enumeradas anteriormente, têm grande aplicabilidade na área de planeamento e previsão em redes de transportes. Existem diversos trabalhos nesta área, tais como a aplicação de redes neuronais [VKG05], séries temporais [LK09] e árvores de classificação e regressão [XKL13]. 13 Revisão Bibliográfica: Background 2.3.2 Aprendizagem estatística A teoria de aprendizagem estatística constitui uma ferramenta na área de machine learning utilizada para encontrar uma função para a realização de previsões. Esta ferramenta apresenta um papel vital em diversas áreas tais como a estatística, data mining e inteligência artificial [HTF13], abrangendo a engenharia e até o desporto. Existem diversos exemplos da aplicação destas técnicas, tais como: •Previsão de doenças com base em diferentes fatores (bioinformática); •Previsão de preços tendo em conta fatores económicos; •Reconhecimento de caligrafia através de visão por computador; •Estudo de estatísticas no basebol. O principal objetivo passa pela estimação da função f, permitindo, assim, realizar previsões ou inferências. Esta função também poderá ser utilizada em processos em que é necessário combinar previsões e inferências no mesmo método. 2.3.2.1 Previsão Considerando Xos dados de entrada disponíveis e Yo valor de saída, pretende-se a partir do conjunto de valores X1, ..., Xpobter o valor deYque representa o resultado da previsão (ˆ Y=ˆ f(X)). Para este efeito, torna-se importante que a função frepresente os dados de teste (com o menor erro possível) e possa fornecer previsões que representem a realidade na forma mais próxima possível. Devido à dificuldade na modelação do sistema, a precisão do valor previsto de Ypoderá depender de erros redutíveis e irredutíveis. A minimização do erro (redutível) passa pela aplicação da técnica de aprendizagem estatística mais adequada ao domínio em estudo e aos dados disponíveis. Existe no entanto um erro associado à própria previsão (ε) que é considerado irredutível [JWHT13]. 2.3.2.2 Inferência Utilizando as mesmas considerações na previsão de resultados com a função f, importa agora perceber as relações que existem entre XeY, ou seja, de que forma o valor de Yé modificado com a alteração dos valores X1, ..., Xp. Isto permite obter resposta para as seguintes perguntas: •Quais as variáveis de Xque estão associadas à resposta? •Qual a relação entre a resposta e cada variável de X? •Como é modelada a relação entre a resposta e cada variável de X? A maioria dos métodos desenvolvidos até hoje baseiam-se na modelação através de equações lineares. Estes métodos, no entanto, são demasiado simples para certos domínios e apresentam uma precisão baixa, implicando assim a utilização de modelos de maior complexidade muitas vezes difíceis de interpretar [JWHT13]. 14 Revisão Bibliográfica: Background 2.3.2.3 Estimação de f A função fresulta da aplicação de métodos de aprendizagem estatística a dados de treino, de forma a que Y≈ˆ f(X)para qualquer observação dos dados de treino (X,Y). Este processo de aproximação e obtenção da função fpode ser enquadrado em duas categorias de métodos: paramétricos e não-paramétricos. Os métodos paramétricos são aplicados em duas fases: numa primeira fase, é escolhida uma função base com um conjunto de coeficientes que serão utilizados posteriormente para a adaptação da função; numa segunda fase, os dados de treino são aplicados de forma a modificar e adaptar o modelo. Este processo é realizado através da modificação dos coeficientes que configuram a forma da curva, sendo muitas vezes utilizado o método dos mínimos quadrados. Os métodos paramétricos, no entanto, apresentam algumas desvantagens relacionadas com a falha na escolha da função base de f, conduzindo a previsões pouco precisas, ou overfitting do modelo, impossibilitando o controlo perante erros ou ruído dos dados de entrada. Os métodos não paramétricos, ao contrário dos anteriores, não realizam quaisquer assunções sobre a função base de f, adaptando-se aos pontos de treino. Apesar de se adaptar a dados de diferentes tipos, exige um número muito superior de observações [JWHT13]. 2.4 Métricas de erro A avaliação de diferentes simuladores e métodos requer que se estabeleçam métricas para comparação dos resultados obtidos. Após uma análise de diferentes artigos na área de modelação e previsão de tráfego em tempo real, verifica-se que as métricas mais frequentemente utilizadas são o erro médio absoluto, o erro médio relativo e o erro médio quadrado. Estas métricas serão apresentadas mais detalhadamente nas subsecções que se seguem. 2.4.1 Erro médio absoluto O erro médio absoluto (Mean Absolute Error - MAE) corresponde à diferença média entre o valor observado e o resultado da previsão [CR14], podendo também ser chamado desvio médio absoluto. Este valor pode ser obtido através da seguinte fórmula: MAE =1 n n ∑ i=1 |ri−fi|(2.1) Em que: ricorresponde ao valor real obtido para o elemento ie ficorresponde ao valor da previsão obtido para o elemento i. 2.4.2 Erro médio relativo O erro médio relativo (Mean Absolute Percentage Error - MAPE) corresponde à diferença percentual entre o valor observado e o resultado da previsão relativa ao valor observado [CR14]. Esta 15 Revisão Bibliográfica: Background métrica também é apresentada como erro absoluto percentual, rácio do erro absoluto e precisão (1 -MAPE), podendo-se obter através da seguinte fórmula: MAPE =1 n n ∑ i=1 |ri−fi ri |(2.2) Em que: ricorresponde ao valor real obtido para o elemento ie ficorresponde ao valor da previsão obtido para o elemento i. 2.4.3 Erro médio quadrado O erro médio quadrado (Root Mean Square Error - RMSE) é calculado através da raiz quadrada aplicada à média das diferenças quadradas entre os valores observados e os resultados obtidos. Este valor poderá ser obtido através da aplicação da seguinte fórmula: RMSE =s1 n n ∑ i=1 (ri−fi)2(2.3) Em que: ricorresponde ao valor real obtido para o elemento ie ficorresponde ao valor da previsão obtido para o elemento i. 2.4.4 Comparação entre as diferentes métricas de erro Todas as métricas enunciadas anteriormente foram identificadas a partir da análise realizada à literatura existente na área de modelação e previsão em redes de tráfego. No entanto, torna- -se fundamental compreender de que forma a escolha de determinada métrica irá influenciar os resultados pretendidos. Numa primeira abordagem, importa perceber a complexidade na previsão do tráfego em determinadas estradas. Existem troços da rede que apresentam filas de trânsito de forma imprevisível, conduzindo ao aparecimento de erros elevados. Por outro lado, torna-se importante perceber algumas características associadas à minimização de medidas de erro tais como o MAE, MAPE e RMSE. A minimização do erro médio absoluto e relativo consiste na minimização do desvio existente entre o modelo construído e a realidade. Assim, poderá surgir uma situação de overfitting, impossibilitando a generalização para casos extremos e raros que importa prever. Pode-se verificar esta propriedade através da figura 2.6. No caso da minimização do erro médio quadrado, os pontos mais afastados são igualmente considerados podendo, por um lado, permitir uma generalização mais adequada do problema em estudo ou introduzir ruído no modelo. Este fenómeno pode ser verificado através do gráfico apresentado na figura 2.7. 16 Revisão Bibliográfica: Background Figura 2.6: Minimização das medidas de erro MAE e MAPE [Cro15]. De acordo com o exposto anteriormente, torna-se importante definir uma medida de erro padrão que possa ser utilizada para comparar diferentes métodos e sistemas. No entanto, é importante perceber de que forma a escolha poderá influenciar os resultados finais. A minimização do erro médio absoluto e do erro médio relativo é especialmente adequada em situações de tráfego recorrentes e com poucas variações. No caso do erro médio quadrado, é possível ajustar o modelo a observações e previsões ocasionais nas quais se verificam grandes flutuações das diferentes variáveis a avaliar. Apesar da abrangência conseguida, importa perceber se o aumento do erro médio absoluto e relativo justificam a consideração dos pontos excecionais. Recomenda-se, por isso, a realização de diversos testes e uma discussão alargada na comunidade científica. Para além da escolha adequada da medida de erro, deve considerar-se o contexto de aplicação dos métodos. A utilização de métodos em redes de estradas diferentes implica necessariamente resultados diferentes, impossibilitando uma comparação direta. Assim, deve ponderar-se a utilização futura de datasets disponíveis publicamente e de fácil acesso. 2.5 Sumário Ao longo desta secção, foram analisados os conceitos fundamentais associados ao tráfego rodoviário, modelação/simulação, análise de dados e métricas de erro. Foi possível verificar que os modelos desenvolvidos nos últimos 50 anos têm apresentado bons resultados, permitindo obter previsões em diferentes horizontes temporais e podendo ser aplicados em diferentes redes rodoviárias. No entanto, a simulação de modelos complexos exige algum tempo de execução, requer a representação da rede e obriga à calibração de um conjunto de parâmetros, podendo limitar a sua aplicabilidade num contexto de previsão em tempo real. Assim, a análise de dados surge como alternativa, permitindo relacionar dados de diferentes fontes, reconhecer padrões e perceber a dinâmica associada. Esta abordagem tem adquirido maior visibilidade recentemente devido à evolução da tecnologia e da capacidade de armazenamento. Para além disso, estas técnicas têm 17 Revisão Bibliográfica: Background Figura 2.7: Minimização da medida de erro RMSE [Cro15]. sido utilizadas em diferentes áreas e têm apresentado bons resultados, considerando-se, por isso, adequadas no contexto desta dissertação. No que se refere às medidas de erro, existem diversas alternativas que poderão ser aplicadas neste projeto, sendo necessário determinar qual ou quais as métricas a minimizar de forma a reduzir o erro associado às previsões. 18 Capítulo 3 Revisão Bibliográfica: Trabalho Relacionado Após a análise de todos os conceitos fundamentais para a modelação, simulação e previsão de trânsito, pretende-se neste capítulo apresentar o trabalho realizado neste domínio. A abordagem será feita segundo duas categorias: simulação mesoscópica e análise de dados. No primeiro caso, são apresentados 5 projetos citados por Blatnig [Bla08] e Lopes [Lop11] que permitem simulação e previsão, possibilitando a sua utilização em contexto real. Relativamente à abordagem datadriven, apresentam-se oito trabalhos desenvolvidos recentemente e que se adequam à situação em estudo. 3.1 Simulação mesoscópica Nos últimos anos, tem-se verificado um progresso significativo na área de modelação e simulação mesoscópica. Devido ao compromisso entre simplicidade e detalhe na modelação de caminhos e movimentos na rede, têm surgido diversos simuladores para previsão offline eonline1, permitindo prever o tráfego em redes de média e grande dimensão [Bur05]. Pretende-se nesta secção apresentar as principais características, vantagens e desvantagens dos seguintes projetos: DynaMIT, DynaSMART, VISTA, TRANSIMS e DYNEMO. Como conclusão, será apresentada uma comparação entre os diferentes projetos e algumas recomendações para a aplicação de um simulador mesoscópico. 3.1.1 DynaMIT O projeto DynaMIT (Dynamic Network Assignment for Management of Information to Travelers) é um sistema DTA (Dynamic Traffic Assignment) para previsão de tráfego em tempo real 1As designações offline eonline referem-se à capacidade do sistema incorporar informação de trânsito em tempo real [Bal06]. 19 Revisão Bibliográfica: Trabalho Relacionado as emissões dos veículos. Desta forma, é possível capturar as interações entre os diferentes subsistemas de viagem, perceber os planos de viagem individuais e situações de congestionamento do trânsito. Ainda é de salientar a possibilidade de avaliação de alternativas, percebendo-se quais os utilizadores que serão beneficiados ou prejudicados com as alterações que se pretende introduzir [BY00]. A metodologia aplicada neste sistema centra-se na atribuição do tráfego e iteração, aproximandose do equilíbrio de Nash. Para isso, o sistema apresenta os seguintes módulos: sintetizador de população, gerador de atividades, planeamento de rotas e microsimulador de tráfego. A partir dos dados das redes rodoviárias, censos, horários dos transportes e sistemas de informação geográfica pretende-se obter a localização exata de cada indivíduo num determinado instante, sendo possível obter uma visão geral do estado da rede. Figura 3.3: Estruturação do sistema TRANSIMS [LEM14]. 3.1.4.1 Sintetizador de população O sintetizador de população, baseando-se em dados obtidos através de censos, gera a população a utilizar para o planeamento de caminhos e simulação. 3.1.4.2 Gerador de atividades O gerador de atividades é responsável pela criação e atribuição das atividades aos indivíduos em função dos levantamentos realizados anteriormente. 26 Revisão Bibliográfica: Trabalho Relacionado 3.1.4.3 Planeamento de rotas Na primeira iteração realizada por este módulo são geradas diferentes rotas, tendo em conta os tempos de viagem armazenados previamente. Nas iterações seguintes são atualizadas apenas algumas frações dos caminhos calculados anteriormente, tendo como base a informação OD. Neste módulo não são considerados os atrasos causados pelos viajantes nas ligações que pretendem utilizar (algoritmo de Dijkstra dependente do tempo). 3.1.4.4 Microsimulador de tráfego O simulador TRANSIMS utiliza o cellular automata para a representação das estradas e dos veículos na rede. Este modelo foi desenvolvido e apresentado por Nagel e Schreckenberg [NS92] e permite, desta forma, simular o movimento dos veículos na direção da via e também as mudanças de faixa de rodagem (para ultrapassagem, por exemplo). Cada veículo desloca-se entre células vizinhas (cada célula apenas poderá conter um veículo [dOBdS+06]), permitindo a simulação em intervalos de tempo discretos e a representação da dinâmica de tráfego [PK11]. Face às características do TRANSIMS, consegue-se modelar o comportamento da população no sentido de obter caminhos mais curtos para a generalidade dos indivíduos. No entanto, surgem críticas por parte da comunidade científica devido à pouca precisão conseguida através do modelo cellular automata e por não conseguir capturar alterações rápidas nas condições de tráfego [CMZB05]. De forma a facilitar a computação de modelos cada vez mais complexos, foram desenvolvidos outros sistemas baseados no TRANSIMS que permitem a paralelização do processamento, tal como apresentado por Rickert e Nagel [RN01]. 3.1.5 DYNEMO O sistema DYNEMO (Dynamisches Netz Modell) foi desenvolvido por Schwerdtfeger em 1984 (Universidade de Karsruhe, Alemanha) e faz parte da família de modelos de fluxo de tráfego Payne-Cremer [Sch]. Neste sistema mesoscópico, apesar da unidade de fluxo de tráfego ser o veículo individual, o movimento é controlado pela densidade média de tráfego na ligação correspondente, sem ter em conta o comportamento individual dos veículos na sua vizinhança como nos modelos microscópicos [NS02]. Este sistema foi desenvolvido com o intuito principal de avaliação de esquemas de gestão de tráfego em autoestradas, principalmente na aplicação de limites de velocidade e de sinalização ramp metering. Os caminhos percorridos pelos veículos são calculados através do algoritmo do caminho mais curto com base na matriz OD dependente do tempo que é fornecida ao modelo [Wat91]. Tendo como input a relação entre densidade e velocidade média em cada secção, o modelo DYNEMO permite obter padrões de volume de tráfego, velocidade média em cada ponto da rede, 27 Revisão Bibliográfica: Trabalho Relacionado tempo de viagem e consumo de combustível para cada veículo e distribuição do tempo de viagem em todos os caminhos calculados. Estes valores são passados ao sistema de controlo de tráfego, permitindo assim indicar aos veículos novos caminhos e recalcular os fluxos nas diferentes secções. Para a utilização desta abordagem optou-se pela utilização de um modelo mesoscópico. Os modelos macroscópicos puros impedem o cálculo de dados estatísticos enquanto os modelos microscópicos consomem mais recursos em espaço e tempo de execução [NS02]. 3.1.5.1 Estruturação do modelo O modelo DYNEMO representa a rede dividida em extensões com características semelhantes (número de faixas e limites de velocidade, por exemplo), sendo cada uma subdividida em secções com comprimentos de cerca de 500 metros. Assume-se em cada secção condições de tráfego constantes (densidade de tráfego constante), associando-se uma relação entre densidade e velocidade média e uma distribuição de velocidades em free flow (distribuição de velocidades desejadas). Para a realização dos cálculos necessários, cada veículo é representado através da posição atual (por comprimento), velocidade atual e velocidade desejada (parâmetro entre 0 e 1 relativamente à velocidade máxima permitida). Para a deslocação dos veículos na rede, assume-se que cada veículo numa secção Si, dada uma condição de tráfego ρi, move-se com uma velocidade num intervalo dependente da velocidade média da secção. A velocidade do veículo também depende da velocidade desejada atribuída inicialmente. Tal como no modelo TRANSIMS, existe uma versão paralelizada do DYNEMO que permite a obtenção de resultados em tempo real para a gestão de tráfego. A implementação deste sistema baseou-se na utilização de multiprocessadores e de memória distribuída, apresentando-se a título de exemplo o estudo realizado numa zona de Berlim [NS02]. 3.1.6 Sumário Pretende-se, nesta secção, comparar os simuladores apresentados anteriormente de forma a perceber qual o mais adequado para cada situação. A tabela 3.1 tem como base a comparação realizada entre os simuladores DynaMIT, DynaSMART, VISTA e TRANSIMS referida por Chien et al. [CMZB05]. A partir da tabela 3.1, é possível identificar um conjunto de características que se apresentam como essenciais em sistemas de gestão de tráfego. As capacidades de estimação e previsão constituíram a base do desenvolvimento destes sistemas, permitindo, assim, perceber a dinâmica do tráfego de uma forma abrangente. No entanto, verificou-se alguma dificuldade para a obtenção de informações relativas ao DynaMIT e DynaSMART (estes dois sistemas não se encontram disponíveis publicamente). Tendo em conta as informações obtidas, a escolha de um sistema de modelação/simulação ideal deverá ter em conta os seguintes pontos: 28 Revisão Bibliográfica: Trabalho Relacionado •Dados necessários – Os sensores disponibilizados nas estradas poderão limitar a obtenção e utilização de dados. A maioria das estradas estudadas dispõe de loop sensors, permitindo, assim, obter dados de contagem e de velocidade dos veículos. No entanto, diversas entidades apostam na obtenção de dados através de dispositivos GPS e telemóveis dos utentes, bem como a utilização de sistemas de vigilância. Isto permite melhorar consideravelmente a precisão dos cálculos realizados. •Resultados obtidos – Os dados fornecidos ao sistema condicionam diretamente os resultados obtidos. Tendo em conta o contexto de aplicação, deve-se considerar um sistema que permita a obtenção de relatórios sobre o estado da rede e de que forma o mesmo evolui. A apresentação de estatísticas também pode ser da máxima relevância. •Representação dos veículos – O nível de detalhe aplicado na representação de veículos deve ter em conta os custos computacionais. Em redes de maior dimensão poderá ser do maior interesse a modelação de veículos e a realização de operações sobre os mesmos de forma agregada. •Detalhe da rede – O sistema de modelação e simulação deverá ter em conta as vias onde se pretende aplicar. Em autoestradas ou vias rápidas pode ser mais conveniente a utilização de sistemas que modelam a rede com pouco detalhe. •Alteração do comportamento face a avisos – Tendo em conta os diversos sistemas eletrónicos de informação existentes atualmente, deve optar-se por um simulador que permita compreender a reação dos condutores de acordo com a informação apresentada, evitando assim os fenómenos de overreaction,oversaturation econcentration [CC05]. •Situações não consideradas – Deve avaliar-se de que forma as limitações apresentadas condicionam os resultados obtidos. Em casos mais simples pode não ser importante considerar ultrapassagens ou a manipulação de dados com elevada precisão. •Incorporação de outros transportes – A simulação de outros meios de transporte pode melhorar a precisão dos resultados finais. No entanto, deve ter-se em conta o custo computacional associado e os dados a fornecer ao sistema (horários, linhas, ...). •Dimensão da rede (recomendada) – Este fator é crucial e pode afetar severamente a qualidade dos resultados finais. •Tipo de funcionamento – A possibilidade de obter dados da via em tempo real permite estimar e realizar previsões com um maior grau de precisão. Deve ter-se uma especial atenção por simuladores online. •Otimização – Os diferentes simuladores podem ter heurísticas específicas, condicionando a atribuição e previsão de tráfego. Deve ter-se em conta o equilíbrio entre a satisfação dos condutores e o estado do sistema. 29 Revisão Bibliográfica: Trabalho Relacionado •Paralelização – A utilização de sistemas multiprocessador permite melhorar de forma significativa o tempo de resposta na obtenção de estimativas e de previsões, sendo especialmente adequado para redes de grande dimensão [KPRG11]. Deve-se, por isso, ter em conta se é possível paralelizar o processamento de dados. Na tabela 3.2, são apresentadas as variáveis que deverão ser introduzidas para a representação do modelo, bem como os parâmetros obtidos após a execução dos simuladores referidos. Em resumo, deve-se ponderar se os dados disponíveis permitem obter resultados mais completos. No caso da VCI, a contagem de veículos e velocidades poderão limitar a capacidade de estimação e previsão do tráfego. Assim, deve considerar-se a utilização de veículos sonda, permitindo obter a localização GPS e a utilização da rede rodoviária. Por outro lado, o processamento de grandes quantidades de dados poderá condicionar a capacidade de obter previsões em tempo real, devendo-se procurar um equilíbrio entre custo e benefício. 3.2 Análise de dados A evolução da capacidade de processamento e armazenamento dos dispositivos conseguida nos últimos anos tem permitido, de uma forma cada vez mais eficaz, a análise de grandes quantidades de dados. Seguindo esta tendência, muitos investigadores da área de sistemas inteligentes de transportes têm apostado na previsão recorrendo à análise de padrões, permitindo perceber a dinâmica do tráfego e prever o estado da rede num menor intervalo de tempo. Assim, apresentam- -se, nesta secção, 8 artigos em que são aplicadas abordagens data driven de forma a obter previsões a curto prazo e em tempo real. 3.2.1 An Improved K-nearest Neighbor Model for Short-term Traffic Flow Prediction Os autores Zhang et al. centram o estudo na implementação de um sistema de previsão de tráfego numa rede de estradas, utilizando os dados obtidos através de sensores instalados numa autoestrada de Xangai [ZLY+13]. Foi desenvolvido um algoritmo baseado no k-Nearest Neighbors, posteriormente integrado num sistema composto por três componentes principais (figura 3.4): base de dados histórica, mecanismo de pesquisa e componente de previsão. A base de dados histórica é atualizada em tempo real, sendo a informação submetida a um conjunto de processos de normalização e eliminação. A informação de tráfego recolhida em tempo real é vetorizada e comparada de seguida com a base de dados, utilizando um fator de hysteresis2. Obtém-se como resultado deste processo um fluxo (veículos de passageiros por cada 5 minutos) com erro médio relativo inferior a 10% e um erro médio absoluto compreendido entre 6.2 e 7.6. Foi ainda adotado um algoritmo baseado na distância Euclidiana, obtendo-se um erro relativo inferior e um erro absoluto superior. 2O fator de hysteresis evita uma excessiva semelhança entre valores na comparação entre os dados observados e os dados provenientes da base de dados. 30 Revisão Bibliográfica: Trabalho Relacionado Figura 3.4: Processo do algoritmo k-NN de regressão não paramétrico [ZLY+13]. 3.2.2 A Hidden Markov Model for short term prediction of traffic conditions on freeways O estudo realizado por Qi e Ishak propõe uma abordagem estocástica através da utilização do algoritmo HMM [QI14]. Os dados analisados foram obtidos a partir de sensores em loop duplos instalados numa autoestrada de Orlando (Califórnia) que registam os parâmetros fluxo, ocupação e velocidade. Estes dados são, posteriormente, classificados de acordo com o estado do tráfego (normal ou intenso) e apresentados num espaço bidimensional segundo estatísticas de primeira e de segunda ordem (média e contraste, respetivamente). São ainda apagados todos os registos nulos ou que apresentam valores inconsistentes (velocidade e ocupação do sensor) e categorizadas algumas variáveis (ex. velocidade). A informação passa então a ser organizada através de estados e transições (com probabilidades associadas), pretendendo-se obter a sequência ótima de estados como resultado final. Através do trabalho desenvolvido, verificou-se que existem mais do que 5 padrões de velocidade diferentes, dificultando a utilização de modelos simples. Para além disso, verificou-se que o trânsito tende sempre para estados de baixo contraste e que pode evoluir para qualquer estado (segundo as matrizes de probabilidade). Foram obtidos erros relativos inferiores a 10%, confirmando a sua aplicabilidade em situações de tráfego intenso. 3.2.3 Freeway Traffic Estimation in Beijing based on Particle Filter Este artigo apresenta uma abordagem híbrida, estabelecendo uma ligação entre métodos model- (modelo macroscópico) e data-driven (Particle Filter) [RBF+10]. É considerado um sistema esto31 Revisão Bibliográfica: Trabalho Relacionado Figura 3.5: Esquema do sistema de previsão com recurso ao algoritmo Particle Filter [RBF+10]. cástico constituído por estados discretos e contínuos no qual esses mesmos estados podem interagir com os seus vizinhos (grafo da rede). Os sensores encontram-se instalados apenas na primeira e na última secção e os cálculos correspondentes às variáveis densidade de tráfego, velocidade média no espaço e fluxo de tráfego são realizados por cada segmento, permitindo reduzir o custo computacional associado. Passa também a ser possível a manipulação de grandes quantidades de dados e de modelos não-lineares e não-gaussianos de grande dimensão. Neste trabalho foram geradas previsões do fluxo, velocidade e densidade de tráfego em intervalos de 2 minutos (numa autoestrada de Pequim, China), obtendo-se um erro médio quadrado relativo de 9.691% para a velocidade e 11.90% para a densidade. De notar que foi aplicado um processo ressampling apresentado na figura 3.5, mas que não se encontra descrito no artigo. 3.2.4 Short-Term Freeway Traffic Flow Prediction: Bayesian Combined Neural Network Approach Neste artigo Zheng, Li e Chi [ZLS06] apresentam uma nova abordagem que consiste na combinação de redes neuronais back propagation e de base radial, originando o Bayesian-combined neural network model (BCNN). O funcionamento baseia-se na atribuição de um valor de crédito a cada rede, permitindo mudar o comportamento e adaptar-se aos resultados pretendidos. O funcionamento do método BCNN depende da classificação do estado do tráfego, selecionando e adaptando o modelo mais adequado para previsão. Para a realização de testes foram utilizados dados de tráfego recolhidos de uma autoestrada de Singapura que são agregados em intervalos de 15 minutos. Estes dados foram divididos em dois conjuntos, sendo o primeiro utilizado para o treino de cada uma das redes neuronais e o outro para testar o desempenho individual e combinado das mesmas. Verifica-se que os modelos combinados apresentam melhores resultados do que os modelos individuais, obtendo-se uma probabilidade do RMSE ser inferior a 10% de 77.8% para o modelo back propagation, 85% para o modelo de base radial e 86.9% para o BCNN. 32 Revisão Bibliográfica: Trabalho Relacionado 3.2.5 Real-time travel time prediction using particle filtering with a non-explicit state-transition model Neste artigo Chen e Rakha apresentam um método baseado no algoritmo Particle Filter, permitindo obter previsões do tempo de viagem a curto e médio prazo em tempo real [CR14]. Os resultados obtidos baseiam-se na utilização da informação recolhida em tempo real e de dados históricos armazenados previamente, não exigindo a utilização de modelos físicos ou de funções de transição de estados. De forma a evitar o problema da degenerescência os autores aplicam técnicas de ressampling que eliminam ou substituem partículas inválidas ou com pouco peso. Este método foi utilizado para a previsão do tempo de viagem numa autoestrada entre Richmond eVirginia (EUA) com base em dados provenientes do serviço INRIX. A partir desta informação procedeu-se à obtenção dos tempos de viagem para utilização na base de dados histórica e como input em tempo real. Após a realização de testes, verifica-se um desempenho superior em comparação com Kalman filters e com o algoritmo k-NN, obtendo-se erros médios absolutos (de acordo com o intervalo de previsão entre 0 e 60 minutos) entre 8.26 e 10.54 minutos e erros médios relativos entre 7.32 e 9.29%. Os autores referem, ainda, a possibilidade deste algoritmo ser utilizado noutras áreas e com outras fontes de informação. 3.2.6 Adaptive Kalman filter approach for stochastic short-term traffic flow rate prediction and uncertainty quantification Guo, Huang e Williams apresentam neste artigo o estudo realizado sobre o método SARIMA + GARCH que tem ganho especial relevância nos últimos anos [GHW14]. Enquanto que o método SARIMA (stochastic seasonal autoregressive integrated moving average) captura a dinâmica de tráfego (primeiro momento condicional) a componente GARCH (generalized autoregressive conditional heteroscedasticity) captura a variação da dinâmica do fluxo de tráfego (segundo momento condicional). É, ainda, feita uma breve análise aos Kalman filters que, apesar de realizarem processamento em tempo real, assumem parâmetros constantes. Assim, recomenda-se a utilização de Adaptive Kalman filters de forma a melhorar os resultados obtidos. Na sequência dos desenvolvimentos enumerados, foram realizados testes a partir de taxas de fluxo agregadas em intervalos de 15 minutos que foram recolhidas em autoestradas do Reino Unido e dos Estados Unidos da América. A partir da comparação entre 4 abordagens distintas, verificou-se que o BATCH apresenta melhores resultados no que se refere ao erro médio absoluto, relativo e quadrado. Também foi possível perceber que a utilização de Adaptive Kalman filters ajuda a melhorar a precisão dos resultados. 3.2.7 An Aggregation Approach to Short-Term Traffic Flow Prediction Tan et al. apresentam, neste artigo, uma solução híbrida que resulta da junção de três modelos distintos [TWX+09]. Através da aplicação de uma rede neuronal, foi possível desenvolver um sistema que integra os resultados dos modelos moving average (MA), exponential smoothing (ES) eautoregressive MA (ARIMA). 33 Revisão Bibliográfica: Trabalho Relacionado Para a aplicação do sistema referido foram construídas três séries temporais (diária, semanal e por hora) a partir dos dados recolhidos na Autoestrada Nacional 107, China (agregados em intervalos de uma hora). Verificou-se que esta solução apresenta melhores resultados em comparação com o ARIMA naïve, regressão não paramétrica e redes neuronais artificiais no que se refere ao erro médio absoluto, relativo e quadrado. 3.2.8 Real-time road traffic prediction with spatio-temporal correlations O artigo de Min e Wynter apresenta uma abordagem que se baseia no modelo MSTARMA(p,q)3, possibilitando a obtenção de previsões para a velocidade e volume num intervalo máximo de uma hora [MW11]. O sistema desenvolvido recebe as variáveis velocidade e volume recolhidas através de sensores em loop e taxis, permitindo obter resultados com baixos erros relativos associados. A abordagem desenvolvida teve em conta a redução do número de parâmetros necessários (conduzindo a processos computacionais mais eficientes) e permite considerar outras variáveis, tais como a meteorologia, incidentes e trabalhos na via. É, também, de salientar o ajuste periódico realizado sobre os pesos de algumas variáveis, adequando os resultados ao padrão verificado na rede. 3.2.9 Sumário De um ponto de vista geral, os oito trabalhos referidos apresentam erros considerados aceitáveis tendo em conta o caráter da previsão a obter. No entanto, é de reconhecer a simplicidade associada ao algoritmo k-NN utilizado no trabalho de Zhang et al. [ZLY+13] que permite com um conjunto de passos simples obter soluções de precisão adequada. Torna-se também importante referir abordagens que consistem na aplicação conjunta de diferentes modelos/algoritmos, tais como as sugeridas por Ren et al. [RBF+10], Zheng, Li & Chi [ZLS06] e por Tan et al. [TWX+09]. No caso da primeira solução, foi construído um sistema híbrido que apresenta caraterísticas interessantes do ponto de vista da interação com modelos macroscópicos. No entanto, o artigo não revela em pormenor os dados utilizados e o contexto de utilização, podendo condicionar a sua replicação noutras situações de elevado interesse. No segundo caso, Zheng, Li & Chi referem a abordagem BCNN, possibilitando a obtenção de resultados mais adequados através da combinação de diferentes algoritmos. A última solução é semelhante, acrescentando a possibilidade de integrar fontes de informação externas tais como meteorologia, incidentes e trabalhos na via. Apresenta-se, na tabela 3.3, um resumo das abordagens apresentadas nesta secção. Um 3indica que a variável foi explicitamente utilizada enquanto que um + significa que os autores consideram como uma possível extensão. Tendo em conta as relações existentes entre as diferentes variáveis (ex. fluxo, densidade e velocidade), algumas métricas poderão ser derivadas e, por isso, foram omitidas. Esta tabela permite assim apresentar a relação existente entre os dados de input 3multivariate spatial-temporal autoregressive - moving average 34 Revisão Bibliográfica: Trabalho Relacionado Input/Output Best approach Data driven Model driven Historic data available? No Yes Predict unmeasured variables? No Route choice analysis? Queue analysis? Yes No Yes Input Output What if scenario? No Predict on random location? Yes No No Yes Yes Figura 3.6: Diagrama de fluxo com perguntas que devem ser consideradas na escolha da abordagem mais adequada [BAR15]. eoutput, guiando na escolha dos métodos mais adequados para o contexto pretendido. Por outro lado, permite identificar a informação a obter para a sua posterior utilização. Ainda, como referência na escolha da abordagem mais adequada, recomenda-se a utilização do diagrama de fluxo da figura 3.6. Este diagrama resume o processo de decisão na escolha da abordagem mais adequada, permitindo assim considerar os diferentes dados disponíveis e os resultados que se pretende obter de acordo com o contexto em estudo [BAR15]. 35 Abordagem Metodológica e Implementação Tendo em conta a dimensão dos dados e o processamento demorado na realização de testes, optou-se pela agregação da informação por cada par sensor-direção. Os cálculos realizados basearam-se na média pesada de acordo com o volume de veículos registado e teve em conta a disponibilidade de informação no momento. Para a realização de todo este processo foi desenvolvida a classe Java AggregateEntriesFromFile, integrada no package converters. 4.3.2 Realização de experiências utilizando R De forma a perceber a viabilidade na utilização de algoritmos de previsão de tráfego a curto prazo, optou-se pela execução de testes recorrendo ao software R que permite a realização de cálculos estatísticos. Foi utilizada a biblioteca caret que integra um conjunto de algoritmos de regressão adequados à situação em estudo. Para a execução deste script, foram utilizados diferentes ficheiros de dados (formato CSV) contendo os valores registados por cada sensor (numa determinada direção) num período fixo de análise. Este ficheiros foram compilados através da classe Java GenerateFilesPerSensor, sendo o resultado apresentado como input ao software R. Os resultados finais obtidos foram, posteriormente, convertidos e agregados através da classe GenerateReportFromROutput, permitindo, assim, uma análise mais detalhada. Para estas experiências foram utilizados os seguintes algoritmos de regressão: •lm - Linear Regression; •spls - Sparse Partial Least Squares; •rlm - Robust Linear Model; •lars - Least Angle Regression; •SaN - Same as Now; •lasso - The Lasso; •ridge - Ridge Regression. 4.3.3 Visualizador do estado da rede A compreensão do estado da VCI, num determinado momento, implica a análise e interpretação de um grande conjunto de dados obtido através de diferentes fontes de informação. De forma a otimizar este processo e obter relatórios sobre os diferentes métodos, optou-se pelo desenvolvimento da interface gráfica apresentada na figura 4.2. Este visualizador pretende integrar as diferentes funcionalidades num só lugar, incluindo-se: •Apresentação dos sensores num mapa (Google Maps) com o estado verificado no momento e informação detalhada, bem como apresentação dos locais onde ocorreram incidentes; 42 Abordagem Metodológica e Implementação Figura 4.2: Interface gráfica da aplicação para visualização do estado da rede e respetiva evolução. •Botões para leitura de informação sobre os sensores, entradas de trânsito registadas, meteorologia e incidentes verificados no momento; •Seleção da variável a utilizar para a apresentação de cores nos marcadores dos sensores; •Seleção da data e hora para a qual se pretende obter o estado da rede ou que deverá ser utilizada na obtenção de previsões; •Seleção do algoritmo e do intervalo a utilizar para a realização de previsões; •Execução de uma interface de testes que permite gerar um conjunto de relatórios sobre os resultados obtidos. A interface é executada através da classe Java TrafficViewer contida no pacote gui. O mapa apresentado depende de uma biblioteca externa para visualização de um browser, sendo por isso necessário uma ligação à Internet e a verificação da licença que poderá ser obtida no site da TeamDev/JxBrowser. 4.3.4 Desenvolvimento de métodos de previsão Nos últimos meses foram desenvolvidos diversos algoritmos que, a partir da informação disponibilizada, indicam o estado futuro da rede após um determinado intervalo de tempo. Neste 43 Abordagem Metodológica e Implementação conjunto de métodos incluem-se o same as now, média, média baseada na diferença, média móvel e k-NN. Aos métodos referidos foram aplicadas diferentes configurações, permitindo, assim, obter um conjunto de variantes adequadas a este processo. O caso da distinção por dias úteis e fins-desemana (weekdays) torna-se essencial, permitindo assim obter entradas mais ajustadas e que se adequam ao comportamento da rede. As subsecções seguintes apresentam detalhes referentes aos algoritmos enunciados previamente. 4.3.4.1 Same as now Este algoritmo baseia-se na crença de que não existirão quaisquer alterações no estado do tráfego e, por isso, a previsão será igual ao estado atual registado. Dado que esta abordagem pode ser adotada sem a necessidade de utilizar quaisquer sistemas de previsão avançados, definiu-se como caso base que se pretende superar no desenvolvimento de novos algoritmos. 4.3.4.2 Média O algoritmo de previsão baseia-se no cálculo da média das variáveis velocidade, volume e ocupação em todos os sensores e direções da VCI. Para este cálculo são analisadas todas as entradas anteriores que apresentam hora igual e que foram recolhidas em dias úteis ou em fins-de-semana caso se pretenda realizar essa distinção. 4.3.4.3 Média baseada na diferença Este algoritmo considera que o futuro estado da rede resulta da diferença média que ocorre no intervalo de previsão indicado. Assim, é calculado em primeiro lugar este valor que posteriormente é somado ao estado atual da rede. 4.3.4.4 Média móvel O algoritmo média móvel apresenta um funcionamento semelhante ao cálculo da média, distinguindo-se no número de entradas que são consideradas para o seu cálculo. Para efeitos de teste, foram utilizadas as últimas 200 entradas antes do instante a prever. 4.3.4.5 K-NN O algoritmo k-nearest neighbours serviu como base à implementação de um método de previsão de tráfego. Tendo em conta o domínio pretendido, foram realizadas as seguintes considerações: •As entradas que são analisadas foram registadas à mesma hora nos dias anteriores, considerandose a distinção entre dias úteis e fins-de-semana. 44 Abordagem Metodológica e Implementação •A proximidade de estados é verificada por cada variável, tendo como prioridade a menor distância entre o valor verificado atualmente e o valor a comparar. •A construção do estado do tráfego resulta da combinação dos estados próximos para cada variável (velocidade, volume e ocupação). O funcionamento do algoritmo desenvolvido obedece aos passos enumerados de seguida: 1. Determinação do estado mais próximo para cada uma das variáveis; 2. Obtenção do estado da rede verificado no passado após o intervalo de tempo selecionado; 3. Agregação dos resultados obtidos a partir das diferentes variáveis em estudo. Para além do funcionamento base, o utilizador pode ainda introduzir algumas configurações que permitem ajustar o processo de recolha ou o processo de inferência de estados. No primeiro caso pode-se atribuir um intervalo de tolerância para a recolha de estados de tráfego, permitindo, assim, considerar possíveis desvios temporais que possam surgir1. No que se refere ao processo de inferência de estados, é possível realizar previsões, considerando cada um dos sensores ou considerando toda a rede em estudo. 4.3.5 Processamento de dados meteorológicos Após a construção de métodos base de previsão a curto prazo e em tempo real, considerou-se oportuno incluir dados meteorológicos da cidade do Porto de forma a poder estudar as possíveis melhorias na qualidade das previsões. Para a obtenção destes dados foi desenvolvida a classe DownloadMeteoEntries (incluída no package utilities) que se responsabiliza pela obtenção dos dados no website Wunderground e correção dos mesmos. A informação obtida passa a estar disponível para utilização na framework desenvolvida e inclui o estado geral do tempo (chuva, nevoeiro, trovoada, limpo), percentagem de humidade registada e visibilidade. Os dados meteorológicos descarregados são, posteriormente, relacionados com as entradas de trânsito registadas na VCI e consideradas na previsão do tráfego. Foram, assim, desenvolvidas algumas variantes que permitem a incorporação da meteorologia nos cálculos realizados e que serão apresentadas nas próximas subsecções. 4.3.5.1 Média baseada nas condições meteorológicas Este algoritmo baseia-se na média, realizando os cálculos de acordo com o estado meteorológico verificado no momento. Assim, as entradas analisadas deverão apresentar o mesmo estado geral do tempo, calculando-se de seguida a média das variáveis obtidas. 1Exemplo: para uma entrada a 15/01/2015 às 20:35 e um intervalo de tolerância de 5 minutos são consideradas todas as entradas até dia 14/01/2015 que ocorreram às 20:30, 20:35 e 20:40. 45 Abordagem Metodológica e Implementação 4.3.5.2 K-NN baseado nas condições meteorológicas O algoritmo k-NN apresentado anteriormente encontra-se preparado para incorporar as condições meteorológicas. Através da ativação de uma flag, este método filtra as entradas a utilizar de acordo com a semelhança entre as condições meteorológicas atuais e as registadas no passado. Caso não seja encontrada nenhuma entrada, optam-se pelos registos em que se verifica céu limpo. 4.3.6 Processamento do registo de incidentes Na sequência da parceria estabelecida entre o LIACC e a Armis, foi possível aceder aos dados relativos aos incidentes registados na VCI nos últimos dois anos. Estes dados contêm os seguintes campos: •Data e hora de início; •Data e hora de fim; •Descrição; •Tipo de incidente; •Latitude e longitude da ocorrência. De forma a integrar esta fonte de informação foi necessário proceder à identificação dos sensores afetados pelas diferentes ocorrências. Considerou-se como referência que os sensores afetados estavam situados a uma distância máxima de um quilómetro em relação ao foco do incidente. O processamento desta fonte de informação permite a aplicação de filtros sobre as previsões, retirando os períodos em que se verificaram incidentes. Esta abordagem foi utilizada de forma a compreender a influência dos incidentes sobre o erro apresentado pelas previsões. 4.3.7 Implementação de métricas de erro Foram implementados um conjunto de métodos que calculam e apresentam o erro obtido na classe Error (pertencente ao package algorithms). As métricas implementadas basearam-se nas técnicas apresentadas na secção 2.4, contendo o erro médio absoluto, erro médio relativo e erro médio quadrado. Desta forma é possível analisar uma lista de previsões confrontando-as com os valores reais observados. 4.3.8 Geração de resultados Na sequência das funcionalidades anteriormente referidas, procedeu-se à implementação de um processo de teste e verificação iterativo que permite, no final, obter um relatório com o erro médio quadrado (RMSE) para cada um dos diferentes algoritmos desenvolvidos. As funcionalidades e características descritas de seguida encontram-se codificadas na classe TestingUtility pertencente ao package utilities. 46 Abordagem Metodológica e Implementação Esta classe, após processamento do algoritmo num dado intervalo de previsão, imprime no ficheiro CSV (report.csv) o erro médio para cada variável (velocidade, volume e ocupação) respeitante a cada par sensor-direção, condição meteorológica (chuva, nevoeiro, trovoada e céu limpo) e resultados agregados. São, ainda, apresentados o número total de entradas analisadas, o número de pares sensor-direção lidos e o número de pares sensor-direção com registo de incidente. Estes testes são realizados para as entradas compreendidas entre uma data de início e de fim especificadas pelo utilizador. Para além do relatório por algoritmo, esta classe também apresenta ao utilizador o erro médio quadrado obtido de acordo com os dias da semana e a hora do dia. Pretende-se, com estes resultados, perceber de que forma o erro varia e quais as abordagens mais adequadas em função do dia ou da hora registadas. 4.4 Sumário Neste capítulo pretendeu-se apresentar as principais tarefas que foram executadas ao longo da dissertação e os detalhes da implementação realizada. Optou-se pelo estudo e desenvolvimento de técnicas data-driven, permitindo assim explorar diferentes algoritmos que se consideram adequados ao contexto em estudo. Por outro lado, a possibilidade de integração de outras fontes de informação tornou-se um fator decisivo para a escolha entre as diferentes abordagens. De seguida, foram definidos os objetivos gerais que deverão ser atingidos no decurso desta dissertação. Importa assim compreender a informação recolhida pelos sensores instalados na VCI, implementar métodos de previsão de tráfego, estudar a integração com outras fontes de dados e aplicar as métricas de erro mais adequadas e que deverão ser minimizadas. No que se refere à implementação, foram apresentadas as principais funcionalidades e ferramentas desenvolvidas que permitem a obtenção de previsões de tráfego em tempo real e a realização simplificada de testes. Para este efeito, foi necessário dividir o processo em quatro etapas principais: •Implementação do processo de leitura dos dados obtidos pelos sensores em loop, meteorologia e incidentes. •Implementação de uma interface gráfica para visualização e monitorização dos dados recolhidos anteriormente. •Implementação de diferentes algoritmos de previsão, bem como aplicação de diferentes configurações e variantes. •Implementação de um motor de testes que aplica as funcionalidades anteriores e apresenta ao utilizador o erro médio quadrado por algoritmo, dia da semana e hora do dia. Todas as etapas foram concluídas com sucesso, permitindo assim a realização de experiências e desenvolver novas abordagens no futuro. Todos os módulos podem ser reutilizados e melhorados de forma a aumentar a precisão destes métodos. 47 Abordagem Metodológica e Implementação Foi também desenvolvido um script em Rque permite a realização de experiências com diversos algoritmos e respetivo cálculo da precisão obtida. Considera-se esta abordagem especialmente adequada para compreender quais os algoritmos que podem ser adaptados à framework desenvolvida e perceber se é possível obter melhorias significativas através da integração de fontes de informação externas. Sugere-se, no futuro, o desenvolvimento de algoritmos mais avançados que possam tirar partido das relações temporais (hora e dia da semana), informações meteorológicas e incidentes registados. No que se refere à meteorologia, a utilização de dados com um intervalo de agregação de 30 minutos poderá limitar a sua aplicação, sendo por isso importante encontrar fontes de informação mais precisas e num menor intervalo de tempo. Por outro lado, os dados dos incidentes exigem um estudo mais aprofundado para compreender a influência nos resultados e quais os tipos de incidentes que causam maiores congestionamentos. 48 Capítulo 5 Resultados e Discussão Este capítulo apresenta os resultados obtidos ao longo da dissertação tendo como base as ferramentas desenvolvidas e as abordagens utilizadas. Estes resultados servirão de base a uma discussão pormenorizada que permitirá perceber a qualidade da solução implementada, bem como perceber quais os próximos passos que deverão ser dados para melhorar o sistema de previsão de tráfego a aplicar na VCI. 5.1 Dados disponíveis e período de testes De forma a avaliar a solução desenvolvida e as opções tomadas, foi necessário obter informação que permite representar o estado da rede num determinado momento. Foram consideradas as seguintes fontes de informação: •Caraterização e localização dos sensores instalados na VCI. •Entradas recolhidas pelos sensores, contendo o identificador, número da faixa, direção, velocidade, volume, ocupação e data/hora de recolha. •Condições meteorológicas incluindo o estado geral do tempo, percentagem de humidade, visibilidade e a data/hora de recolha. •Registo de incidentes com indicação da localização, tipo, data/hora de início e fim da ocorrência. A caraterização dos sensores permitiu definir a estrutura para armazenamento dos registos de tráfego, facilitando a ordenação e interpretação dos resultados obtidos. No que se refere ao registo do tráfego, as entradas encontram-se agregadas em intervalos de 5 minutos, apresentando por isso os resultados médios nesse período para a velocidade e ocupação. O processamento destes resultados teve como base algumas considerações importantes: os valores finais deverão estar compreendidos entre o valor mínimo médio e o valor máximo médio, tendo 49 Resultados e Discussão em conta o limite mínimo e máximo das variáveis (tal como o limite máximo de velocidade, por exemplo); foram invalidadas todas as entradas com volume inferior a 30 de forma a considerar períodos em que se regista algum movimento no local. Os dados meteorológicos foram recolhidos a partir do serviço online do site Wunderground, obtendo-se as entradas registadas a cada 30 minutos na estação meteorológica do Aeroporto Francisco Sá Carneiro - Porto (LPPR). O registo de incidentes foi obtido através da parceria entre o LIACC e a Armis, apresentando todos as ocorrências verificadas na VCI. Neste caso foi necessário verificar a duração dos incidentes de forma a compreender se os dados apresentados eram válidos. Para as próximas secções foi considerado o intervalo de testes compreendido entre o dia 1 de março de 2014 às 00:00 e o dia 31 de maio de 2014 às 23:55, utilizando como dados de treino os valores obtidos entre o dia 1 de março de 2013 às 00:00 e o dia 28 de fevereiro de 2014 às 23:55. 5.2 Aplicação de diferentes algoritmos utilizando R Tendo como intenção compreender quais as abordagens e qual a informação necessária que permite melhorar a qualidade das previsões, procedeu-se à separação das entradas por sensordireção, integrando no 2.oconjunto de dados o estado geral do tempo e a visibilidade registados num determinado instante. De seguida foi iniciado o script em R, tendo sido obtidos os resultados das figuras 5.1 e5.2. Figura 5.1: Erro médio quadrado em R obtido para um intervalo de previsão de 15 minutos. A partir das figuras 5.1 e5.2, é possível verificar que de uma forma geral o erro médio quadrado aumenta à medida que o intervalo de previsão aumenta. Este comportamento está em linha de conta com a informação disponível do momento, ou seja, para intervalos de previsão menores, é possível integrar maior informação e, por isso, aumentar a precisão dos resultados. Após a análise do comportamento geral, procedeu-se a uma avaliação do desempenho obtido para diferentes intervalos de previsão. Apresentam-se os algoritmos com melhor desempenho na tabela 5.1. 50 Resultados e Discussão Figura 5.2: Erro médio quadrado em R obtido para um intervalo de previsão de 30 minutos. Na sequência dos testes realizados, procedeu-se à integração dos dados meteorológicos obtidos previamente. Foram analisadas as melhorias associadas à previsão quando se integra o estado geral do tempo e a visibilidade, estando os resultados disponíveis nos gráficos das figuras 5.3 e5.4. Figura 5.3: Melhoria média do erro médio quadrado em Rapós integração do estado geral do tempo. Verifica-se, assim, que a integração dos dados meteorológicos poderá conduzir a melhores previsões da variável ocupação para intervalos crescentes. As previsões para a velocidade e volume pioram, importando, no entanto, referir uma ligeira melhoria do erro do volume para previsões a 25 e 30 minutos quando se utiliza a visibilidade. Na sequência da análise dos dados, após integração das condições atmosféricas, procedeu-se à análise das melhorias médias tendo em conta o algoritmo aplicado. Apresentam-se os resultados obtidos nos gráficos das figuras 5.5 e5.6 respeitantes à integração do estado geral do tempo e visibilidade. Pela análise dos gráficos, verifica-se que o método Sparse Partial Least Squares apresenta 51 Resultados e Discussão Figura 5.9: Erro médio quadrado na aplicação obtido para um intervalo de previsão de 15 minutos após integração de dados meteorológicos. •Processador Intel i7-740QM a 1.73Ghz com 4 núcleos físicos e 8 núcleos lógicos; •Memória RAM 8GB DDR3; •Disco de armazenamento SSD Samsung 840 EVO de 250GB. A partir da análise dos resultados obtidos, verifica-se que os mesmos estão de acordo com a estrutura dos algoritmos desenvolvidos. A média móvel apresenta melhores tempos de execução, dado que a previsão é calculada com um número limitado de entradas (200). Por outro lado, os algoritmos k-NN apresentam tempos de execução elevados, podendo limitar a sua aplicabilidade no contexto pretendido. A aplicação de um intervalo de incerteza de 5 minutos implica que o número de entradas a analisar triplique, aumentando, assim, o tempo de processamento. Por fim, a utilização de informações meteorológicas tem uma consequência positiva sobre o tempo de execução devido ao pré-processamento realizado para filtragem de entradas com condições meteorológicas semelhantes. Os algoritmos com melhores resultados correspondem aos que apresentam menores tempos de execução (Same as now, média e média móvel), recomendando-se por isso a sua utilização. Considera-se que a utilização de outros algoritmos deverá ser ponderada caso seja possível obter melhorias significativas no erro médio quadrado registado. 5.4 Sumário Os resultados apresentados anteriormente permitiram compreender de que forma a aplicação e as abordagens se adequam ao problema e contexto em análise. Por um lado, pretendeu-se perceber quais os algoritmos em Rque apresentam melhores resultados e se a meteorologia poderá contribuir para a redução do erro. Neste sentido, os resultados mostram que considerar que o estado do 58 Resultados e Discussão Figura 5.10: Erro médio quadrado na aplicação obtido para um intervalo de previsão de 30 minutos após integração de dados meteorológicos. tráfego permanece estático durante curtos períodos de tempo (SaN) permite obter bons resultados. No entanto, recomenda-se a análise dos algoritmos (da biblioteca caret)lasso,lm eridge dado que apresentam erros reduzidos. É, ainda, importante considerar a integração de outras fontes de informação, tais como a meteorologia ou o registo de incidentes. Testes preliminares através do software R com integração da meteorologia demonstram que as melhorias são visíveis para intervalos de previsão iguais ou superiores a 25 minutos. O método Sparse Partial Least Squares apresenta melhorias superiores em comparação com as restantes abordagens, conseguindo-se uma redução do erro de aproximadamente 1% para o volume e ocupação. Estes resultados são obtidos a partir da análise do estado geral do tempo e da visibilidade. Relativamente à aplicação desenvolvida, obteve-se uma solução que permite integrar novos algoritmos, visualizar e obter previsões de trânsito em tempo real. A partir daqui verificou-se que existem algoritmos mais adequados tendo em conta o intervalo de previsão de tráfego, a existência de incidentes e as condições meteorológicas registadas. A utilização de algoritmos como a média, média móvel ou o k-NN apresentam resultados interessantes e demonstram que podem ser usados neste contexto. No entanto, são necessárias técnicas mais robustas que permitam perceber a evolução e aplicar o método mais adequado à situação verificada. A meteorologia é um dos fatores condicionantes do estado do tráfego mas exige um estudo mais aprofundado de forma a determinar quais as variáveis que estão ligadas diretamente aos resultados obtidos. A categorização do estado geral do tempo não é suficiente face às melhorias pontuais verificadas. Por outro lado, verifica-se que a existência de incidentes e as horas/dias da semana têm influência sobre os erros médios quadrados obtidos. Os períodos de tempo entre as 8:30 e as 9:30 e entre as 18:00 e 20:00 ("horas de ponta") apresentam valores mais elevados para o RMSE, acontecendo de forma semelhante às sextas-feiras. Por último, verifica-se a existência de correlações entre as variáveis velocidade e ocupação e os erros médios das três variáveis estudadas. Esta análise poderá ser útil 59 Resultados e Discussão Figura 5.11: Melhoria do erro médio quadrado após utilização de dados meteorológicos para um intervalo de previsão de 15 minutos. para o desenvolvimento futuro de novos algoritmos com erros mais reduzidos. 60 Resultados e Discussão Figura 5.12: Melhoria do erro médio quadrado após utilização de dados meteorológicos para um intervalo de previsão de 30 minutos. Figura 5.13: Melhoria do erro médio quadrado quando não são considerados períodos de incidentes para um intervalo de previsão de 15 minutos. Tabela 5.6: Tempo de execução de acordo com o algoritmo e o intervalo de previsão (em segundos). Algoritmo 5 min 10 min 15 min 20 min 25 min 30 min Same as now 0.071 0.035 0.029 0.034 0.036 0.034 Média 14.196 13.622 12.945 12.994 13.719 13.084 Média (Meteo) 14.453 13.915 13.567 13.382 14.222 13.431 Média dif. 20.129 19.769 19.502 19.874 21.486 20.477 Média móvel 12.415 11.922 11.597 11.448 12.079 11.689 K-NN 113.791 108.959 106.582 105.438 111.246 108.117 K-NN (Meteo) 101.603 96.147 95.380 94.719 100.199 99.550 K-NN int. 5 min 397.086 368.244 368.483 366.567 371.235 383.899 K-NN int. 5 min (Meteo) 346.263 323.103 326.483 342.647 330.067 343.133 61 Resultados e Discussão Figura 5.14: Melhoria do erro médio quadrado quando não são considerados períodos de incidentes para um intervalo de previsão de 30 minutos. Figura 5.15: Erro médio quadrado para diferentes estados do tempo. Figura 5.16: Evolução do erro obtido para as variáveis velocidade, volume e ocupação de acordo com a variação temporal do volume. 62 Resultados e Discussão Figura 5.17: Evolução do erro médio quadrado ao longo de um dia. Figura 5.18: Evolução do erro médio quadrado ao longo de uma semana. 63 Resultados e Discussão 64 Capítulo 6 Conclusões e Trabalho Futuro Pretende-se, neste capítulo, apresentar as principais conclusões referentes ao estudo e trabalho desenvolvido ao longo da dissertação. Serão apresentadas, em primeiro lugar, algumas considerações adotadas, incluindo-se um breve resumo sobre os resultados obtidos e contribuições associadas aos objetivos pré-estabelecidos. A partir daqui serão realizadas algumas propostas para melhorias e trabalho futuro a realizar no âmbito do problema em estudo. 6.1 Satisfação dos Objetivos Ao longo da dissertação foram desenvolvidas um conjunto de técnicas que permitem, por um lado, processar e disponibilizar a informação sobre as condições de tráfego na VCI, bem como a realização de previsões a curto prazo e em tempo real. Numa fase inicial, procedeu-se ao estudo de conceitos e de diferentes técnicas para modelação e previsão de tráfego, permitindo, assim, perceber quais as abordagens mais adequadas tendo em conta o contexto, os dados disponíveis e os objetivos finais deste projeto. De seguida, como suporte ao estudo das técnicas de previsão, foi necessário desenvolver uma interface que permite a visualização da informação (através de um mapa) e o processamento dos dados recolhidos através das diferentes fontes de informação. Implementaram-se mecanismos de agregação e integração que permitiram simplificar a informação obtida e relacionar com dados meteorológicos e com os incidentes verificados. Por outro lado, o cálculo dos erros e a execução iterativa dos testes permitiu também facilitar o processo de implementação dos métodos de previsão. No que se refere aos métodos, foram desenvolvidos um conjunto de algoritmos (abordagem data-driven) e respetivas variantes que permitem estudar a influência de determinados parâmetros nos resultados da previsão. Em conjunto com a média, média baseada na diferença, média móvel e k-NN, foi possível tirar partido das datas de registo das entradas, dados meteorológicos 65 Conclusões e Trabalho Futuro e incidentes registados. Os estudos realizados no capítulo 5mostraram que, apesar dos resultados satisfatórios das previsões (quando comparados com outros trabalhos realizados em diferentes redes rodoviárias), são necessárias novas abordagens para lidar com as variações do tráfego e situações de congestionamento às quais se associam erros médios quadrados elevados. Por outro lado, a integração com os dados meteorológicos e dos registos de incidentes não se encontra otimizada, sendo necessário perceber de que forma condicionam os resultados. Como análise introdutória às possíveis dependências existentes, foram calculados os fatores de correlação entre os valores observados e os erros médios quadrados obtidos, mostrando que existe uma correlação moderada para as variáveis velocidade e ocupação. Estes resultados estão de acordo com a situação observada, verificando-se uma grande dependência entre a variação da velocidade e da ocupação e os erros obtidos para as três variáveis estudadas. Como guia para futuros desenvolvimentos do atual sistema, foi executado um script no software R que permite testar um conjunto variado de algoritmos e comparar o seu desempenho. Regressão linear, lasso eridge são os algoritmos que apresentam melhores resultados e que, por isso, devem ser aplicados futuramente. No entanto, o método base same as now continua a apresentar bons resultados, o que traduz que o tráfego varia pouco em intervalos de curta duração (até um máximo de 30 minutos). Após a integração dos dados meteorológicos, verificou-se uma melhoria geral do erro da ocupação, piorando os resultados para a velocidade e volume. Ao analisar as melhorias por algoritmo, verifica-se que o método Sparse Partial Least Squares apresenta melhores resultados, especialmente para os erros das variáveis volume e ocupação. Em suma, esta dissertação permitiu explorar o domínio das técnicas de previsão de tráfego (com especial foco nos métodos data-driven), percebendo-se quais as principais fatores a considerar e de que forma é possível melhorar a precisão e avaliar as diferentes soluções. Todas estas conclusões permitiram a escrita do artigo apresentado na conferência MT-ITS 2015 (Budapeste, Húngria), tendo como principal intuito a comparação das duas abordagens principais, uma análise à literatura existente e a apresentação de algumas questões para a avaliação das soluções que deverão ser resolvidas nos próximos trabalhos relacionados com a área de sistemas inteligentes de transportes [BAR15]. Considera-se, assim, que os objetivos gerais propostos foram atingidos, apresentando-se uma aplicação com bons resultados no que se refere à obtenção de previsões e permitindo, num futuro próximo, adicionar diferentes fontes de informação que possam revelar-se úteis para melhorar a precisão já conseguida. 6.2 Trabalho Futuro Tendo em conta os objetivos e a solução obtida, recomenda-se daqui em diante o foco exclusivo sobre os algoritmos de previsão a desenvolver. Apesar dos resultados satisfatórios, é importante analisar outras abordagens que possam tirar partido dos dados de tráfego disponíveis e de outras fontes de informação externas adequadas. Perceber de que forma evolui o trânsito e a relação com a data/hora e com as condições atmosféricas poderá revelar-se útil para a situação 66 Conclusões e Trabalho Futuro em estudo. É, ainda, importante analisar os valores da correlação apresentados na secção 5.3.8, tornando-se o ponto de partida para determinar as relações existentes e desenhar uma abordagem mais eficaz. Como objetivo a atingir posteriormente, seria fundamental que a aplicação pudesse estender as previsões a todos os pontos da VCI. As abordagens data-driven permitem apenas a realização de previsões nos pontos de recolha, o que poderá limitar a análise integrada do problema em causa. Recomenda-se, por isso, um estudo aprofundado sobre as abordagens híbridas (model-driven + data-driven) que permitem obter previsões para todos os pontos da rede e modelar situações excecionais, tais como acidentes e formação de filas [RBF+10]. Existem soluções que apresentam um algoritmo de deteção automática, permitindo assim a aplicação de uma abordagem data-driven em situações normais e a aplicação da abordagem model-driven para a simulação dos incidentes ocorridos e da respetiva propagação. Ainda deve-se considerar futuramente o estudo de métodos baseados na utilização de tensores, tal como apresentado por Dauwels et al. [DAA+14]. Neste trabalho, procedeu-se à realização de previsões para a velocidade numa rede de estradas em Singapura, tendo-se verificado que é possível obter soluções satisfatórias. No entanto, é necessário analisar os recursos computacionais necessários, podendo não ser adequado para os meios técnicos e para o espaço temporal (a curto prazo) disponíveis. Ainda é de considerar a limitação associada aos dados recolhidos através dos sensores em loop. Estes dados apenas permitem a monitorização de um conjunto pequeno de parâmetros, limitando assim os outputs obtidos. Assim, recomenda-se a utilização conjunta de floating-car data, permitindo acompanhar os trajetos dos condutores (através do posicionamento por GPS) e o tempo de viagem necessário. Por outro lado seria possível obter uma visão completa da rede, facilitando o processo de previsão [LAB+13]. A solução apresentada neste documento for desenvolvida com o propósito inicial de análise das metodologias mais adequadas a aplicar num sistema de previsão de tráfego. No entanto, a aplicação já se encontra preparada para utilização com dados em tempo real, permitindo assim a sua utilização em contextos reais. No que se refere à VCI, o sistema desenvolvido poderá ser integrado na aplicação de gestão de tráfego utilizada atualmente para monitorização desta via. Com a introdução e pré-processamento dos dados recolhidos pelos sensores, é possível obter rapidamente previsões com erros médios quadrados baixos e, desta forma, tomar as melhores decisões no sentido de assegurar níveis adequados de serviço. Para além da gestão do tráfego, os sistemas utilizados atualmente têm como um dos principais objetivos a redução da sinistralidade rodoviária. Dado que a VCI é considerada um dos "pontos negros"da rede de estradas portuguesa, torna-se importante a adoção de uma atitude preventiva que permita reduzir a ocorrência de acidentes. Assim, uma extensão futura deveria passar pela determinação da probabilidade da ocorrência de um incidente. Desta forma seria possível mobilizar os meios adequados e assegurar a segurança dos utilizadores. Por fim, este sistema poderia ser utilizado para a geração automática de informações para viajantes (ATIS) a partir das previsões obtidas. Desta forma seria possível determinar as mensagens 67 REFERÊNCIAS 74 Anexo A Systematic Review A.1 Quais os objetivos desta Systematic Review? O foco desta Systematic Review centra-se na pesquisa de informação sobre técnicas de análise de dados que possibilitam a estimação de tráfego numa rede rodoviária. Tendo como base as técnicas estudadas, pretende-se perceber o trabalho já desenvolvido nesta área e como implementar uma solução que possa ser aplicada à VCI. A.2 Quais os problemas a abordar? Não existem algoritmos desenvolvidos e aplicados que permitam modelar e estimar o tráfego na VCI em tempo real. A informação obtida poderia ser utilizada para uma ação preventiva, permitindo assim aos agentes reguladores de trânsito gerir o tráfego na via e enviar informações aos condutores. A.3 Questões •Que tipo de técnicas baseadas em data mining podem ser utilizadas para previsão do tráfego em redes rodoviárias? 1. Existe alguma aplicação prática destas técnicas? 2. Quais os dados e características necessárias à implementação de um algoritmo de estimação de tráfego? 3. Existe alguma abordagem com combinação de algoritmos ou técnicas (como por exemplo model driven)? A.4 Palavras-chave •Traffic flow 75 Systematic Review •Traffic simulation •Estimation •Prediction •Statistical learning •Model-driven •Data-driven •Data mining •Traffic assignment A.5 Seleção de fontes A.5.1 Critério de seleção Para a seleção da informação a utilizar teve-se em conta os seguintes critérios: •Jornais Científicos, Relatórios, Conferências e Teses na área de simulation,prediction e road traffic assignment. –Jornais Científicos: Future Generation Computer Systems,Transportation Research, Environmental Modelling & Software,Engineering Applications of Artificial Intelligence,Procedia Computer Science, IEEE e MIT. –Relatórios: Center for Transportation Research,Center for Transportation Training and Research. –Conferências: Second International Conference on Advances in System Simulation. –Teses: Traffic prediction for unplanned events on highways,Microscopic Traffic Simulation with Intelligent Agents,Hybrid microscopic-mesoscopic traffic simulation, Vehicle-centric coordination for urban road traffic management: A market-based multiagent approach. •Todos os artigos devem estar disponíveis de forma gratuita (através de acesso livre ou assegurado pelo sistema de informação da FEUP e UP). •Todos os documentos aplicam-se diretamente à área de transportes. •Todos os documentos relacionados com previsão através de data mining abordam conceitos aplicáveis na área de transportes. •Livros relacionados com aprendizagem e a área de transportes, tais como: Introduction to Transportation Engineering,An Introduction to Statistical Learning with Applications in R eThe elements of statistical learning: data mining, inference and prediction. 76 Systematic Review A.5.2 Fontes de informação A pesquisa de informação tem como base os motores de pesquisa utilizados geralmente na área científica. Incluem-se essencialmente: •IEEExplore; •Google Scholar; •Science Direct. A.5.3 Termos de pesquisa principais (traffic AND (prediction OR estimation)) AND (highway* OR freeway*) Esta pesquisa retornou os seguintes resultados: •Google Scholar – 248000 resultados; •Science Direct – 4329 resultados. Os artigos selecionados obedeceram ao seguinte processo de seleção: •Análise do título; •Análise do abstract; •Análise das conclusões e erro associado; •Filtragem de algoritmos ligados diretamente à análise de dados ou abordagem híbrida; •Qualidade dos resultados. 77 Systematic Review 78 Anexo B Planeamento B.1 Escrita do artigo para a conferência MT-ITS •Descrição: Desenvolvimento de um artigo a submeter na conferência 4th International Conference on Models and Technologies for Intelligent Transportation Systems. •Input:Revisão da literatura na área de estimação e previsão de sistemas inteligentes de transportes. •Resultado: Análise da literatura e algumas considerações a ter em conta no desenvolvimento de um sistema de estimação e previsão. •Período de execução: 16/01/2015-27/02/2015 (31 dias úteis). B.2 Conceção de interface gráfica de teste •Descrição: Desenvolvimento de um programa constituído unicamente por uma interface gráfica, possibilitando a visualização de um mapa onde é apresentada a previsão do estado da rede. Permite a realização de testes e a obtenção de resultados. •Input:Documentação da linguagem de programação e API da aplicação de visualização de mapas. •Resultado: Programa capaz de apresentar um mapa e a localização dos sensores instalados na via. •Período de execução: 23/02/2015-06/03/2015 (10 dias úteis). 79 Planeamento B.3 Identificação de algoritmos e definição de medidas de benchmarking •Descrição: Identificação e definição de algoritmos que podem ser utilizados para análise e previsão do estado da rede. Desenvolvimento de métricas que permitem avaliar o desvio das previsões relativamente ao valor real obtido. •Input:Literatura na área de data mining e literatura ligada à estimação e previsão na área de transportes. •Resultado: Algoritmos planeados e que podem ser implementados e testados. Métricas que permitem comparar a qualidade dos resultados de estimação e previsão. •Período de execução: 09/03/2015-03/04/2015 (20 dias úteis). B.4 Implementação, teste e análise •Descrição: Desenvolvimento de algoritmos, realização de testes, comparação e análise dos resultados obtidos. •Input:Algoritmos definidos, benchmarks e programa desenvolvido. •Resultado: Solução desenvolvida capaz de realizar previsões, resultados obtidos e análise. •Período de execução: 06/04/2015-08/05/2015 (25 dias úteis). B.5 Escrita da dissertação •Descrição: Escrita da dissertação, integrando a literatura e conceitos analisados, algoritmos desenvolvidos, resultados, testes realizados e conclusões obtidas. •Input:Toda a informação recolhida no decurso da dissertação e dados do relatório intermédio. •Resultado: Dissertação. •Período de execução: 04/05/2015-12/06/2015 (30 dias úteis). B.6 Diagrama de Gantt 80 Planeamento Figura B.1: Diagrama de Gantt com o planeamento do projeto. 81 Planeamento 82 Anexo C Diagrama de packages Figura C.1: Diagrama de packages da solução desenvolvida. 83