Examiner Abdelaziz

Stephane Mousset

Christele Lecomte

Bernard Matyjasik

Amnir Hadachi

Gabriel Wiart

Tahri Jouti

Ndèye Rokhaya

Kane Diallo

Thibaut Yoquet

Charlie Boulo

Mathieu Fresquet

Thibaut Reiter

Ali Lazaar

Alexis Attimont

Youssef Hafi

Paul Jégouic

Sébastien Ng

Chun Hing

Hamza Benjamin

Françoise Errougani

Du Juvanon

Grégory Vachat

Benoit Coutant

Boucher

Choong Kok

Vincent Wong

Mirela Cassé

Jean Rasinar

Creusefond

Perrote Matthew

Risso--Bourgés Jérémy

Mrs Samia Ainouz

Mrs Alexandrina Rogozan

Elsa Planterose

Mr Mr Stéphane Canu

Mr Sébastien Kramm

Mr Mhamed Itmi

Mr Pascal Vasseur

Bruno Sadeg

Mr Claude

Yadu Prabhakar

Alina Dana Miron

Laura Giuliani

Nadeen Salameh

Carlo Abi Chahine

Zakariae Bram

Bassem Besbes

Yacine Sid Ahmed

Pierre Yver

Georges Challita

Iyadh Cabani

Florian Yger

Aurélie Boisbunon

Ovidiu Serban

Guillaume Dubuisson Duplessis

Zacharie Ales

Abbu Keita

Abir Zribi

Pierre Bourgeois

Travel Time Estimation Using Sparsely Sampled Probe GPS Data in Urban Road Networks Context

This dissertation is concerned with the problem of estimating travel time per road sections in urban context using sparsely sampled GPS data. One of the challenges in this thesis is the use of sparsely sampled data. The thesis work and the report were done in a period of two years and half. The thesis research work was conducted within the project PUMAS, which is an advantage for our research regarding the collection process of our data from the real world field and also in making our tests. The project PUMAS (Plateforme Urbaine de Mobilite Avancee et Soutenable / Urban Platform for Sustainable and Advanced Mobility) is a preindustrial project that has the objective to inform about the traffic situation and also to develop and implement a platform for sustainable mobility in order to evaluate it in the region, specifically Rouen, France. The result is a framework for any traffic controller or manager and also estimation researcher to access vast stores of data about the traffic estimation, forecasting, and status. Sparsely sampled probe GPS data refers to the case where vehicle send their current location at a fixed frequency. The frequency aspect makes it not enough to directly measure the speed or travel time on the road section. In order to overcome these challenges the contributions of this thesis mainly around the following subjects:

1. Digital map and GIS information: During our research work we noticed the importance of creating the digital map. For example, in transportation planning and logistic, it is advantageous to use digital map or numerical incorporated with information such as transportation facilities data, speed limits, roadway indicator, and type of roads. These information are very helpful to improve traffic algorithms and estimations. Thus, we extracted our digital map from OpenStreetMap (OSM) and we added our GIS information that contains all the information needed such as speed limit at each section, intersection, defining the type of roads and its directions, new features, etc.

2. Map--matching problem In our approach we defined a spatial analysis criteria and we defined the area of interest by detecting the road sections that has the highest probability, where the GPS position should be matched on the digital map, without scanning the whole There are many people I would like to thank for all of their support in making this dissertation possible. First and foremost, I want to thank my parents, Ahmed and Rabha Hadachi, my brother Izgh, my sister Lacey and her husband Dennis for being supportive of absolutely everything I have done in my life and always encouraging me to pursue every opportunity. A special thanks to my second family, Roman and Tiia Ubakivi, and also Piret and Kalle Soovares for their support during this thesis period.

map. Then, we added temporal analysis criteria. Finally, we applied an orthogonal projection on the GPS position into the concerned road section that have the highest score of the combination of spatial and temporal criteria. Moreover, we added the notion of the orientation in order to enhance the map matching. The orientation informs us about the direction that the car is following; making it easier to be located on the road that has the same direction as the car's heading. In some of the case we still have non--matching cases. Therefore, we added a correction method that makes a new prediction of the defective data and then apply the whole process of map matching to the corrected data.

3. Time dependent shortest path problem The time--dependent shortest path problem given a departure and arrival time was one of our research interests. There are many solutions that has been developed for different types of graphs such as Dijkstra in the case of positive weights, Bellman in the general case, etc. However, these methods are time consuming regarding the computational process, which mean that they need enhancement and speed up. We adopted a new approach by applying the process in a database context. In this method we introduced a new step that we called a learning phase, where we process on offline mode using a recursive Dijkstra. The results of this learning process are saved in the database. Then, during the online mode the method uses the output of the learning step that is called by the map matching. Introducing this learning step at the level of the database enhanced the speed of finding the answers on online mode.

Travel time estimation per road sections

The use of sequential Monte Carlo approach to estimate travel time using sparsely sampled GPS data is certainly not new. However, to our knowledge the application of Monte Carlo methods on urban networks has not been found in the literature.

a. Travel time estimation using Monte Carlo method Using this approach we adopted the Monte Carlo method to our case by defining a state equation. The creation of the filter was done in a way to process and use the sparsely sampled GPS data. The filter gave us the ability to estimate the moment when the probe vehicle enters a road section and also when it exits the same road section. By considering these information it was easy for us to know how long the probe vehicle was in that section.

b. Travel time estimation using Monte Carlo method enhanced with measurements and road sections characteristics To enhance the approach, we injected the algorithm with additional information concerning the travel time distribution of each road sections. This information concerned the measurements and the features of the road sections on the road network.

Résumé :

Cette thèse porte sur le problème de l'estimation des temps de parcours, de véhicules, par section de route dans un contexte urbain, en utilisant les données GPS à faible densité d'échantillon. L'un des défis de cette thèse est d'utiliser ce genre de données. Par ailleurs, les travaux de cette thèse et le rapport ont été fait dans une période de deux ans et demi.

La thèse s'inscrit dans le cadre du projet PUMAS (Plateforme Urbaine de Mobilité Avancée et Soutenable), ce qui est un avantage pour nos recherches en ce qui concerne le processus de collecte de données réelles sur le terrain ainsi que pour faire nos tests. Le projet PUMAS est un projet préindustriel qui a pour objectif d'informer sur la situation du trafic mais également de développer et de mettre en oeuvre une plate--forme de mobilité durable afin de l'évaluer dans la région, notamment à Rouen, France. Le résultat offre un cadre pour tout contrôleur de la circulation, gestionnaire ou chercheur pour accéder à de vastes réserves de données sur l'estimation du flux du trafic, sur les prévisions et sur l'état du trafic. Les données GPS échantillonnées, réfèrent au cas où les véhicules envoient leurs positions courantes, à une fréquence fixe. L'aspect de la fréquence n'est pas suffisant pour mesurer directement la vitesse ou le temps de déplacement sur les sections de route. Afin de surmonter ces défis les contributions de cette thèse s'articulent essentiellement autour des thèmes suivants:

Carte numérique et information SIG:

Au cours de notre travail de recherche, nous avons été convaincu de l'importance de la création de la carte numérique. Par exemple, dans la planification des transports et de la logistique, il est avantageux d'utiliser la carte numérique intégrante des informations telles que les données des installations de transport, les limites de vitesse, indicatrice de la chaussée et le type de routes. Ces informations ont été très utiles pour améliorer les algorithmes de la circulation et des estimations. Ainsi, nous avons extrait de OpenStreetMap (OSM) notre carte numérique et nous avons ajouté nos informations SIG qui contiennent toutes les informations nécessaires telles que la vitesse limite pour chaque section, les intersections, la définition du type de routes et de ses orientations, etc.

Géo-référencement

Dans notre approche, nous avons défini un critère d'analyse spatiale et nous avons défini la zone d'intérêt en détectant les tronçons de route qui ont la plus forte probabilité, où la position GPS doit être mappé sur la carte, sans scanner celle-ci entièrement. Ensuite, nous avons ajouté des critères d'analyse temporelle. Et enfin, nous avons appliqué une projection orthogonale des positions GPS, qui ont le score le plus élevé de la combinaison des critères spatiaux et temporels, sur le tronçon de route concerné. De plus, nous avons ajouté la notion du cap en vue d'améliorer l'appariement sur la carte. Le cap nous renseigne sur la direction que la voiture a suivie; ce qui rend sa localisation sur la route facile vis-à-vis du sens de la circulation sur la section de route concernée. Suite à des rejets de données ou des mauvaises correspondances constatées, nous avons ajouté une méthode de correction qui fait une nouvelle prédiction des données défectueuses, avant d'appliquer l'ensemble du processus du géo-référencement aux données corrigées.

Problème du plus court chemin dépendant du temps

Le problème du plus court chemin dépendant du temps connaissant un départ et une arrivée a été l'un de nos sujets de recherche. Il existe de nombreuses solutions qui ont été développées pour les différents types de graphiques tels que Dijkstra dans le cas des poids positifs, Bellman dans le cas général, etc. Toutefois, ces méthodes prennent beaucoup de temps en ce qui concerne le processus de calcul, ce qui nous a amené à les améliorer. Nous avons, pour cela, adopté une nouvelle approche en appliquant le processus dans un contexte de base de données. Cette méthode, nous a permis d'introduire une nouvelle étape, que nous avons nommée phase d'apprentissage, où nous avons procédé, en mode hors ligne, en utilisant le Dijkstra récursive. Les résultats de la phase d'apprentissage sont enregistrés dans la base de données. Puis, pendant le mode en ligne, la méthode utilise la sortie de la phase d'apprentissage qui est appelée par le géo-référencement. L'introduction de cette phase d'apprentissage au niveau de la base de données améliore le temps de réponse en mode en ligne de façon significative.

Estimation du temps de parcours par section de route

L'utilisation de l'approche de Monte Carlo séquentielle pour estimer le temps de déplacement à l'aide des données GPS, à faible densité d'échantillon, n'est certes pas nouvelle. Toutefois, à notre connaissance, l'application de méthodes de Monte Carlo pour estimer les temps de parcours sur les réseaux urbains ne figure pas dans la littérature.

a. Estimation du temps de parcours en utilisant la méthode Monte Carlo

En utilisant cette approche, nous avons adopté la méthode de Monte Carlo pour notre cas en définissant une équation d'état. La création du filtre a été faite de manière à traiter et à utiliser les données GPS à faible densité d'échantillon. Le filtre nous a donné la capacité d'estimer le moment où le véhicule traceur pénètre dans une section de route et aussi quand il en sort. En tenant compte de ces informations, il était aisé de savoir combien de temps le véhicule traceur a mis pour traverser la section de route en question.

b. Estimation du temps de parcours en utilisant la méthode Monte Carlo

améliorée avec les mesures et les caractéristiques des sections de route. Pour améliorer l'approche, nous avons modifié l'algorithme en injectant des informations historiques relatives à la distribution des temps de parcours de chaque section. Ces informations concernent les mesures et les caractéristiques des sections de route sur le réseau routier.

7

This dissertation is dedicated to my awesome and amazing family, to whom I owe everything and my lovely fiancé, Pille.

I love you all List of Tables The urban road traffic today experiences increased rates of traffic jams that threaten the environment, the people's behavior and also the transport efficiency. In order to tackle these problems, knowledge about the traffic conditions is a must at many levels of urban traffic management and policy.

The involvement of traffic management can be seen in variations of factors, such as network structure, public transportation, city size, etc. Urban traffic management efficiency is relaying on the capability of individuals to plan their own trips more accurately. From this statement it is clear that travel time information plays a big role in urban traffic management. Moreover, it reflects the performance of urban road networks. Besides, travel time estimations or predictions, if accurate and reliable, can be beneficial to network users. The impact can be seen in the decreasing number and level of both the traffic jams phenomenon and the users stress. Travel time information is essential for transportation planning, transportation operation, and of course, transportation management. In addition, it is a necessity to characterize urban traffic or traffic in general.

Travel time appears to be the most significant measure of road traffic information. Over the last decade, many researchers have conducted travel time estimation [START_REF] Hofleitner | Optimal decomposition of travel times measured by probe vehicles using a statistical traffic flow model[END_REF], [START_REF] Fang | Analysis of Hydrogen Station Network Using Geographic Information Systems[END_REF], [START_REF] Kumar | A Model Based Approach to Predict Stream Travel Time using Public Transit as Probes[END_REF] and demonstrated its importance in practical applications of transportation and logistics [START_REF] Li | Arterial Travel Time Estimation Using VII Probe Data and Point--based Detection Data[END_REF], [START_REF] Lianxiong | Mining Travel Time from Intelligent Card Toll Data[END_REF]. The use of travel time estimation enhances efforts in many fields to give road users the information needed for understanding the road traffic status [START_REF] Nanthawichit | Application of Probe Vehicle Data for Realtime Traffic State Estimation and Shortterm Travel Time Prediction on a Freeway[END_REF].

In practice, the methodologies applied to estimate or predict travel time depends on the data available. Furthermore, the approaches that will be adopted differ in terms of the provided data from sensors available on the urban network. We have to take into consideration that the urban networks are not completely covered with sensors as much as the freeways. As a consequence, it will be a challenge to develop a model or a method that will work in all scenarios.

In order to make the real--time traffic monitoring a success, we need information about the networks state in the past, present and also the future. The information required is collected from a variety of sources, such as inductive loops, cameras and floating cars. Besides, this information should be as complete and accurate as possible.

Unfortunately, all data collected suffer some specific problems. For example, all local sensors detection techniques do not provide an actual traffic state in terms of queue lengths and delays due to traffic jam or traffic lights. Furthermore, the travel time collected from probes [START_REF] Torday | Probe Vehicles Based Travel Time Estimation in Urban Networks[END_REF] showed high variances, which means that they need a preprocessing before use. Another conceivable source of data is the Global Positioning System (GPS).

Nowadays, the information we can get from GPS is so rich for exploitation. This latter can be used through floating car in the urban network. The data collected can give us information about the network status, which in turn implies traffic status.

Throughout time, the literature on travel time estimation using GPS sensors has grown thanks to the technology that become more available. Most of the research, such as [START_REF] Zou | Arterial speed studies with taxi equipped with global positioning receivers as probe vehicle[END_REF] and [START_REF] Work | An ensemble Kalman filtering approach to highway traffic estimation using GPS enabled mobile devices[END_REF] conducts high frequency data, which eliminate many of the challenges of interest due to the progress done. However, low sampling frequency continues to be a challenge because of the difficulties presented by this kind of data. Some of the difficulties faced when dealing with sparsely sampled data with low frequency is the inference of the probes path between two positions reports, which may involve in some case a considerable number of road section in the urban network, like it was stated in [START_REF] Rahmani | Path inference of low--frequency GPS probes for urban networks[END_REF] and [START_REF] Miwa | Route identification and travel time prediction using probe--car data[END_REF]. Another point regarding the difficulties is to estimate the travel time spent on each individual road section. A variety of local methods have been developed for this issue like in [START_REF] Miller | Determining time to traverse road sections based on mapping discrete GPS vehicle data to continuous flows[END_REF], [START_REF] Hellinga | Decomposing travel times measured by probe--based traffic monitoring systems to individual road links[END_REF], and [START_REF] Zheng | Urban link travel time estimation based on sparse probe data[END_REF]. By taking into consideration the idea proposed by Gustafsson [START_REF] Gustafsson | Particle filters for positioning, navigation, and tracking[END_REF] it is important to start by preprocessing the data before trying to estimate the travel time in order to reduce errors caused by the GPS [START_REF] Pinana | GPS Multipath Detection and Exclusion with Elevation--Enhanced Maps[END_REF] or the Map--matching [START_REF] Hadachi | An Application of the Sequential Monte Carlo to Increase the Accuracy of Travel Time Estimation in Urban Areas[END_REF]. These preprocessing steps are very important, especially when dealing with the sparsely sampled GPS data with low frequency. In this chapter the background is described in order to give an idea how this research work took its path regarding the available data and tools. Next, the research objectives and restrictions are defined in order to make a clear statement of thesis context and boundaries of the research. Then, our strategy and contribution regarding the problematic are summarized. Finally, a clear outline of the dissertation of this thesis is given.

Research Objectives and Restrictions

This section is going to be elaborated in a manner to establish a clear description of the travel time estimation problematic. Travel time is the outcome of traffic flow processes, which brings up the question of the governance. In this case, travel time is ruled by interactions between traffic supply characteristics and traffic demands. Moreover, the non--linearity interactions between the heterogeneous groups (vehicle, drivers, road) bring to life a complex problem, due to their behavioral characteristics. Nevertheless, in real world field we have enough information to estimate travel time with a certitude that is close to the reality.

Objectives

The main objective of this dissertation is to develop a methodology capable of estimating travel time in a specific platform, using a database of sparsely sampled GPS data. To reach our main objective, we are obliged to deal with other issues related to the preprocessing of the sparsely sampled raw data. We named these in our dissertation the preprocessing tools. The preprocessing tools contain the process of building our digital map and its geographic information system (GIS), filtering the raw data, map matching and shortest path problem.

Scopes

Travel time estimation is a broad research topic. In literature, a wide variety of techniques were used in order to estimate travel time. Those methods can be classified in terms of special scope, road type, input traffic data, etc. In this dissertation the research will be limited in the following manner: First, the work done applies to an urban road network. This means that the spatial scope is limited to urban road type in an urban network context. Of course the concept can be easily extended to other kind of networks.

Although there are a lot of factors influencing urban travel time, such as the weather, traffic composition and public transit. In this dissertation we will focus on the road network geometry that will be used in the process of the map matching and correcting the raw data errors.

The raw data that is used in this dissertation is the sparsely sampled GPS data with low frequency. This kind of data is massively available, that's why the researchers are using it a lot in their application and research. However, the sparsely sampled data present a big challenge when it comes to its use, especially when estimating travel time per road sections (details of the challenges chapter 2).

Finally, this research focuses on travel time estimation per road section in urban areas. The estimation will be run on a historical database of sparsely sampled GPS data on offline mode and also on online mode, by simulating the data. In general, travel time estimation is used for forecasting but also for real time route guidance. Apparently, longer the estimation accuracy of traffic either in the future or present is, the more the models rely on statistical and theoretical assumptions regarding the data size and future traffic conditions [START_REF] Van Lint | Monitoing and predicting freeway travel time reliability--using width and skew of day--to--day travel time distribution[END_REF]. In fact, the estimation of travel time plays a big role in learning about the traffic aspects and its behaviors. 1.3 Project PUMAS We had a chance to conduct this research within the project PUMAS, which helped us in the collection process of our data from the real world field and also in conducting our tests. The project PUMAS [117] (Plateforme Urbaine de Mobilite Avancee et Soutenable / Sustainable and Advanced Mobility and Urban Platform) is a preindustrial project that has the objective to inform us about the traffic situation, to evaluate gas emission and also to develop and implement a platform for sustainable mobility in order to evaluate it in the region, specifically in Rouen, France.

Description

The PUMAS project aims at developing a software platform for collection and analysis of road traffic information in real time. The software platform will benefit to local Public Authorities (towns, cities, regions), providing them with:

• Real time knowledge of current and future traffic conditions along urban and peripheral networks in terms of travel times and traffic patterns, • A significant contribution to greenhouse and pollutant gas emission models, in real time and throughout the area, based on the knowledge of flow mean speed along all the city road sections • An accurate tool for urban mobility decision--making through the permanent day--to--day monitoring of traffic conditions in the area. The project is based on the floating car data concept, by equipping a significant sample of vehicles operating constantly in a given area (public buses, for example) with an on--board device with GSM and mapping capabilities, thus capturing their speed, journey time and location. This data is transmitted via GPRS or WiFi (Figure 1.1) to a platform for analysis. Real--time and predictive travel times are produced using enhanced algorithms. A thousand of vehicles were fitted with a custom--made on--board unit in order to do travel time estimation, prediction and path reconstruction in the urban agglomeration of Rouen (Normandy). More details about the project will be discussed in chapter 2.

Contributions and Relevance

In this section we will show the main contributions of this dissertation and also the scientific relevance of the approach and the methods used.

Contributions

The main contributions of this thesis can be summarized as follows:

a. The estimation of travel time per road sections was done on urban road network, using sparsely sampled GPS data. Moreover, the estimation was based on the family of sequential Monte Carlo Method, more specifically on particle filter.

b. We made a study about the speed profile, where we conducted the characteristics of the speed distribution in the urban road network. The speed distribution study focused on the impact of the speed aspect on road sections. c. We also implemented the same study for the location of sparse probes in order to know the evolution of the displacement of the vehicle in the urban road sections. The two studies concerning the location and the speed were done because we will use them in the estimation of travel time for improvement purposes. d. Finally, this dissertation also dealt with the shortest path problem that we used in the process of map matching for raw data. Besides, we made an enhancement of the map matching process. In addition, the thesis work spawned software with friendly graphical user interface, where we can process and run the system on offline mode or online mode. Moreover, we can see the results of the process directly on the road network map.

Scientific Relevance

The aim of this work is to estimate travel time on urban road sections. The concerned roads are the ones with no dedicated sensing infrastructure and for which the only potentially available source of data is sparse GPS probe data. The challenge relies on the nature of the available data. For this reason, first we proposed an enhanced map matching technique applied to sparse GPS data by using probe vehicle heading and road orientations, itinerary reconstruction without any external information, spatio--temporal analysis, and correction of the rejected data during the process. Then we presented an original approach to solve this problem by using an applied Monte Carlo Method and historical probabilities distributions of travel time per road sections. The sequential Monte Carlo approach has been used in many research cases. However, the application of Monte Carlo method on urban networks to estimate travel time has not been found in the literature. The output of this thesis can be very beneficial by using it in a data--driven method or model--based method in order to forecast or monitor in real time the traffic status. Due to the complexity of urban traffic, it is also promising to combine the two methods to get better results.

Practical Relevance

The research results of this dissertation are used in the PUMAS system. This shows that our approach meets the industrially required standards. To be more specific, the practical relevance of this research work is to estimate travel time per road sections, using the sparsely sampled GPS data as accurately as possible and to implement it in the PUMAS system to apply it for real world environment.

Road Map

Apart from the Chapter 1 where we present the dissertation in general, the following chapters will be as follows (Figure 1.2): Chapter 2:

The chapter 2 gives a state--of--art of some techniques used to compute the travel time based on the technology and the nature of data collected for that purpose. Then, the chapter talks about the travel time estimation models with all the techniques used. It describes and analyses some similar project to ours. Finally, it gives a description and details about the project PUMAS in order to give a clear idea about the context of this thesis and the added value. Chapter 3: In this chapter we give a clear description of the tools used in the preprocessing step. In this step we make a raw data check for any incoherence. Then, we create the digital map embedded with our new characteristics of the geographic information system (GIS). Finally, we show the enhancement done to the map-matching process and the shortest path problem computation. Chapter 4: This chapter presents a study of the observed distributions from the empirical data in the historical database of the speed and location. This study is particularly important for the applied Monte Carlo Method used to estimate the travel time per road sections. Then, it presents a clear description of how the method was adapted to our case in order to estimate the travel time per road sections. Chapter 5: The chapter 5 presents the implementation's structures and the software processes of the system created in this thesis work. In addition, each section shows the results and analysis of the tests done in order to validate the methods and algorithms proposed in this thesis. Chapter 6: The final chapter summarizes the main conclusions of this research work and offers directions for future research. The same factors that draw the congregation of large urban areas leaded to intolerable levels of traffic jams on urban road networks. The urban traffic management has been conducted by researcher through processing specific sources of information such as public transport management and priority, traffic management in urban areas, and real--time traffic light signal management. The traffic management measurement has increased throughout time that leaded the focus of research to change from architectural aspect like effective monitoring of traffic using Variable Message Signs (VMS) [START_REF] Song | Estimation of legibility Distance for Portable Variable Message Signs[END_REF] to involving extensive data acquisition, enforcement, and control [START_REF] Fernandez | Road-traffic monitoring by knowledge--driven static and dynamic image analysis[END_REF] such as pedestrian activity, traffic speed, heavy goods vehicles, cycling, public transport usage, vehicle occupancy and congestion. This change in the approach of research gives more accuracy and effectiveness in the management strategy and policy. The more we know about the information available on the road network such as Variable Speed Limits (VSL) and Hard Shoulder Running (HSR), and its evolution through time, the more accurate and effective the traffic management will be. The processing of these extensive data needs a careful selection of the appropriate speeds and operational lane strategies. However, the fluctuating aspect of their patterns makes it a real challenge to control and master the system effectiveness. The urban context makes choosing the appropriate data an important step in the traffic management. The complexity of urban traffic relies on its actors (personal vehicles, public transportation, etc) that can constitute a source of conflict. Thus, priority system as Automatic Vehicle Identification and localization (AVI/AVL) is a must in order to enhance the traffic management strategies. Of course there exists some systems like the Automatic Incident Detection (AID). This latter uses probe vehicle data, which are one of the interest of the Intelligent Transportation Systems (ITS) community research [START_REF] Abuelela | Automatic Incident Detection In VANETs: A Bayesian Approach[END_REF]. One important piece of metric information that can help in investigating traffic status is travel time. Many techniques have been developed in order to gather information about traffic flow, speed, and travel time including: probe vehicles [START_REF] Li | Arterial Travel Time Estimation Using VII Probe Data and Point--based Detection Data[END_REF], loop detectors, mobile sensors [START_REF] Herrera | Traffic flow reconstruction using mobile sensors and loop detector data[END_REF], and so on. Different methods based on prediction models and historical data have been explored by researchers to estimate travel time [START_REF] Steven | Dynamic Travel Time Prediction with Real--time and Historical Data[END_REF].

Travel Time Estimation Using Traffic Information Systems

Most of the studies related to travel time estimation were done based on the fact that the traffic flow is uninterrupted [START_REF] Coifman | Vehicle Reidentification and Travel Time Measurement across Freeway Junctions using the Existing Detector Infrastructure[END_REF], [START_REF] Wei | Development of Freeway Travel Time Forecasting Models by Integrating Different Sources of Traffic Data[END_REF]. However in the real world field these studies cannot be directly applicable because traffic flow is highly dynamic. In order to find a solution to this issue in the literature there are many approaches for estimating travel time in urban areas such as data fusion, fuzzy control theory, and microscopic traffic simulation, etc; but all these techniques need costly GPS data. Therefore, the choice of the approach to adopt in order to estimate travel time is related to the nature of data available. During these last years various types of sensors have been developed to collect various type of data about the traffic. Overall, traffic data can be summed up to velocity data (distance per unit time), flow data (number of vehicles per time units), occupancy data (percentage of time a point on the road is occupied by vehicles), density data (number of vehicles per distance unit), and travel time (time needed to travel between two location). An additional kind of data is the vehicle trajectory data collected from vehicles equipped with GPS devices. The last kind of data gives the advantage to compute directly travel time and also distance velocities.

Loop Detectors

The traffic measurement is mainly based on counting the number of vehicles on the road. One of the technologies used for this purpose is the inductive loop detector that is buried under the road infrastructure to detect the passage of a vehicle. The information is collected locally in housing and conveyed to a central traffic management where they are aggregated. Moreover, the loop detectors can provide accurate information regarding the velocity data that can be provided by the loops by checking consecutive crossing times. In addition to the flow and occupancy data [START_REF] Chen | Freeway performance measurement system: mining loop detector data[END_REF], this leads to deduce the traffic density [START_REF] Jia | The PeMS algorithms for accurate, real--time estimates of g--factors and speeds from single--loop detectors[END_REF]. Computing technologies for travel time based on magnetic loops are reliable, but they correspond to old technology over fifty years and remain quite expensive because they require civil engineering and maintenance. Thus, they are only present in the economically advanced countries and in big cities. Regarding the information collected from the loop detectors many extrapolation methods have been developed to estimate travel time [START_REF] Chu | Adaptive Kalman Filter Based Freeway Travel time Estimatio[END_REF], [START_REF] Van Lint | Improving A travel Time Estimation Algorithm by Using Dual Loop Detectors[END_REF].

Half--Distance Approach

In this approach the assumption is that the speed measured by a set of dual loop detectors (figure 2.1) is valid to the half--distance on both sides. Therefore, the travel time between the two loops is defined as follows (equation 2.1):

! !!! = ! ! ( ! ! ! ! + ! ! ! ! ) (2.1)
Where,

• ! ! and ! ! : average speed measured at loop A and B respectively, for a specific time interval. • ! !!! : travel time between loop A and B • ! ! : is the distance separating the two loops

Average Speed Approach

In this approach its name reflects the assumption. Which is: the average speed will be the average of the two speed measured by the two loops (equation 2.2). Then the equation will be:

! !!! = ! ! (! ! !! ! ) ! (2.2)
Where,

• ! ! and ! ! : average speed measured at loop A and B respectively, for a specific time interval. • ! !!! : travel time between loop A and B • ! ! : is the distance separating the two loops

Minimum Speed Approach

For this approach the minimum speed detected by the loops will be assumed to be the speed of the vehicle during his travel between the two loops. Hence the equation 2.3 will be:

! !!! = ! ! ! !"# (2.3)
Where,

• ! !"# : minimum speed measured by loop A and B.

• ! !!! : travel time between loop A and B • ! ! : is the distance separating the two loops 2.2.2 Video and License Plate Readers Travel time can be measured also by using automatic plate recognition system (APR) [START_REF] Takaba | Estimation and Measurement of Travel Time by Vehicle Detectors and License Plate Readers[END_REF]. The difference between loop detectors and ARP system is that loop detectors can only provide information about the flow and local speed; thus some errors are present in the estimation of travel time; however, the APR system gives more accurate travel time. The process starts by having at least two fixed ARP systems on the road (figure 2.2). Then when the vehicles pass by the first APR system it will read its plate number. After, when he passes the second APR system it will do the same. Finally, the server will match the plate numbers and their time stamp tags in order to measure the travel time between the two APR systems [START_REF] Amri | Travel Time Measurement in Real Time using Automatic Number Plate Recognition for Malaysian Envirement[END_REF].

Radar

The radars have the ability to collect velocity, flows, and occupancy data when you place them along the side of roads. There are mainly implemented in highways rather than urban areas. Moreover, they are suitable with massive data collection; nevertheless, the collected data has low accuracy. Moreover, the accuracy data collected decreases in arterial environment. The radar uses vehicle speed S computed using the time difference ΔT corresponding to the vehicle reaching at the leading edges of two range bins. The distance D separating the range bins is known. The vehicle speed is given by equation 2.4:

! = ! ∆! (2.4)
Where,

• D: distance between leading edges of the two range bins and • ΔT: time difference corresponding to the vehicles arrival at the leading edge of each range bin.

Bluetooth

Bluetooth readers are based probes detection. They scan the area range and check if there is any Bluetooth enabled device; then they can determine travel times and speeds between points on a roadway network [START_REF] Malinovskiy | Field Experiments on Bluetooth--based Travel 473 Time Data Collection[END_REF]. The Bluetooth data give a straight measurement of travel time between pairs of scanners. The data include the "duration" of the vehicle to pass the range detection of the Bluetooth scanner [START_REF] Tsubota | ¨Arterial traffic congestion analysis using Bluetooth Duration data[END_REF]. Thus the Bluetooth can give the following information (Figure 2.

WiFi Technology

Getting travel time using WiFi localization alone is accurate enough for route planning but it's not the case for individual road section estimation. The technique used to estimate travel time is by knowing the location of the vehicle and the distance to the next WiFi spot [START_REF] Kwong | Arterial Travel Time Estimation Based on Vehicle Re--Identification Using Wireless Magnetic Sensors[END_REF]. The difficulty appears when there is noise affecting the localization of the car making it difficult to attribute the travel time to the concerned road section. However this problem can be fixed partially by adding an algorithm to estimate the nearest neighbor as it was shown in [START_REF] Kelly | Computationally Tractable Location Estimation on WiFi Enabled Mobile Phones[END_REF]. The author compared two approaches a probabilistic classifiers method and k--nearest neighbor method. In [START_REF] Kelly | Computationally Tractable Location Estimation on WiFi Enabled Mobile Phones[END_REF] the results showed that the best classification accuracy is possible using a simple brute force approach (K--nearest neighbor). Another issue with using WiFi localization alone is that sometimes it cannot detect hotspot accurately due to the outages present in the WiFi data. As consequence, they will be missing information of travel time in some road sections.

Sparsely sampled GPS Data

Sparsely probe GPS Data denotes the case when the probes send GPS information at a fixed frequency. Moreover, sometimes it is not frequent enough to measure the velocity evolution or the travel time in an accurate way (frequency can be more than 10 seconds). The use of this kind of data to estimate travel time presents many challenges. The first one is related to mapping of the GPS location on the road network or the digital map. This implies that the correct position should be found and matched to the right road section as well as the right itinerary of the probe journey. Second challenge is related to the situation when the probe travels many road sections in the road network before sending the GPS data. Thus, the estimation of path is required in order to compute travel time estimation. All these issues will be discussed in details in this dissertation because it is one of the topics conducted in this research work. Sparsely sampled GPS data are the most challenging data to process in order to estimate travel time per road section. For example (Figure 2.4) illustrates the sparse data used in [START_REF] Bolbol | Inferring hybrid transportation modes from sparse GPS data using a moving window SVM classification[END_REF]. The data is covering the whole area and it is 2--weeks long multi--modal tracks (2 waves -to account for seasonal variation) of 81 users within 2010-2011 [START_REF] Bolbol | Inferring hybrid transportation modes from sparse GPS data using a moving window SVM classification[END_REF]. The ubiquity of this kind data is going to make it the most used and available among the traffic information systems next decades.

High frequency GPS Data

The high frequency GPS insinuates when the probe vehicle has the ability to send GPS information every few second or each second (no more than 10 seconds). This aspect makes the data the most accurate regarding the itinerary and also the travel time per road section. It seems that using this kind of technology is the most accurate but still poses some problems with the map matching, especially close to the roundabouts or intersections. This will affect the localization on the map and also computing travel time [START_REF] Sen | Frequency of probe reports and variance of travel time estimates[END_REF]. Moreover, receiving this kind of data each second through the means of communication into the server is expensive. However, there some potential solution to this issue that Project PUMAS has treated.

Travel Time Estimation/Prediction Models

Available models can be categorized based on their way of computation to different kinds of statistical models, mathematical models, simulation models, and artificial intelligence models. Thanks to research, there are hybrid models too, where the hybrid models incorporate the combination of two or more the above cited models. For example the statistical models include Particle Filtering [START_REF] Arulampalam | A tutorial on particle filters for online nonlinear/non--gaussian bayesian tracking[END_REF], Monte Carlo Method [START_REF] Hongwei | Study on the Reliability of Travel Time in Transportation Network[END_REF], Kalman Filtering [START_REF] Yang | Travel time prediction using the GPS test vehicle and Kalman filtering techniques[END_REF], Bayes Analysis [START_REF] Casper | A General Model of Bayesian Travel Time Learning[END_REF], etc. The models that took advantage of research in the Artificial intelligence are mostly based on Neuro--Fuzzy models [START_REF] Oke | A neuro--fuzzy approach to vehicular traffic flow prediction for a metropolis in a developing country[END_REF] and Artificial Neural Networks [START_REF] Lee | Freeway Travel Time Forecast Using Artificial Neural Networks With Cluster Method[END_REF]. All these cited models have shown good performance in the linear environments such as freeways and highways. Moreover some of them have shown also good results in complex and non--linear environments such as urban networks. In this section the discussion will be about reviewing a number of these models and methods by type: "statistical, mathematical, and hybrid".

Statistical Approach

Proposed by Gordon et al [START_REF] Gordon | Novel approach to nonlinear/non Gaussian Bayesian state estimation[END_REF], this kind of algorithm, which uses particle filtering, has gradually emerged as the best technique for processing nonlinear signals. The concept of resampling introduced by Gordon has allowed many issues related to estimations and predictions to be solved, and also opened new windows to be explored and developed. The particle filtering algorithms [START_REF] Challita | Particle filters for accurate localization of communicant vehicles using GPS and vision systems[END_REF] can estimate probability through successive measurement by using a finite set of Dirac measurements centered in the corresponding points of "particles". Applying the Monte Carlo Method relies on two things: making the Monte Carlo approximation and resampling size. This method permits us to represent the density of the filter p(:) by samples. In general sampling gives a probability that depends on sampling size. In addition, the method allows us to sample the particles using a law q(:) called the importance law, the size/the number being chosen by the user. The estimation made by this method is valid when the samples are normalized. In [START_REF] Van Lint | Improving A travel Time Estimation Algorithm by Using Dual Loop Detectors[END_REF] the approach presented was based on an unscented Kalman filter in order to estimate travel time in urban networks. The algorithm used stochastically the vehicles count data from loop detectors and also the travel time data. The process of this method allowed doing real time estimation of travel time and the estimation of upstream of vehicles number as well as the number of mid--road sections. The Kalman filter is a very good tool to estimate the variables when we are dealing with a linear problem. In case the problem is non--linear then the approach will change either to particle filter or other derived methods from Kalman filter such as extended Kalman filter or particle Kalman. Let's move now to the Bayesian Analysis. For example in [36] the article shows how they use Bayesian approach to estimate arterial road section travel speed and travel time in urban network. Besides, the input data was collected from loop detectors and probe vehicles equipped with Dedicated Short--range Communication device. Moreover the Bayesian analysis gives this flexibility to combine with prior information and data. For example you can incorporate a prior distribution for future analysis with past information about the parameter. It provides also conditional inferences on the data without reliance on asymptotic approximation. In addition, it obeys to the likelihood principle and thanks to the probabilities representation in the method that gives a clear interpretation of the parameters. However, the Bayesian analysis cannot tell you how to select a prior. Besides, the Bayesian inferences need skills to translate subjective prior beliefs into mathematically formulated prior. It can also produce posterior distributions that are heavily influenced by the prior distributions. To sum up, during this presentation of the statistical methods we showed some advantages and also some disadvantages depending on the nature of the data and also on the objectives of the analysis behind using it. But still can be a good approach if combine between two or more methods and of course by choosing the right one that will fit the problematic or the situation treated.

Artificial Intelligence Approach

Artificial Intelligence is the discipline where we seek to understand the natural intelligence and create intelligent system capable of performing the same actions as the natural ones [START_REF] Lalla | Artificial intelligence hybrid heuristic based on tabu search for the dynamic berth allocation problem[END_REF]. Today, applying this technique is kind of fashion among all fields of research, especially the intelligent transportation system sector [START_REF] Keyarsalan | Designing an intelligent ontological system for traffic light control in isolated intersections[END_REF]. One of the most popular Artificial Intelligence technique is the Artificial Neural networks (ANN) and the Neural Network (NN). These two latter techniques have been applied in many fields [START_REF] Pino | Forecasting next--day price of electricity in the Spanish energy market using artificial neural networks[END_REF], [START_REF] Huang | Evolutionary neural networks and DNA computing algorithms for dual--axis motion control[END_REF]. Neural network has been explored a lot in research. For example in [START_REF] Lee | Freeway Travel Time Forecast Using Artificial Neural Networks With Cluster Method[END_REF] a novel travel time prediction was developed using artificial neural network with cluster method. The logic of the algorithm is based on functional relation between real time traffic data as input variable and actual travel time data as the output. The use of clustering method is to reduce the data features with less input and preserve the original traffic physiognomies. Then the travel time forecasting is obtained by inserting the real time traffic data into the functional relation. The article results showed good forecasting performances. Using neural network helped a lot dealing with nonlinear spatio--temporal relationship for example in [START_REF] Lint | Freeway travel time prediction with State--Space Neural Networks[END_REF] the author adopted recurrent neural networks in order to forecast freeway travel time. The test was done on synthetic data and the results were pretty good. The inconvenient issue with this approach is that in order to have good results you need detailed traffic information. However the author tried to fix this problem, which is noticeable in his article in [START_REF] Van Lint | Accurate freeway travel time prediction with state--space neural networks under missing data[END_REF] where he suggests a freeway travel time forecasting that exhibits both qualities accuracy and robustness with respect the gap in input data.

To understand why this approach needs a lot of information about traffic in order to give good results; we have to go back to the structure of artificial neural networks. The ANN are constructed by using nodes, which are laid in different layers. The manner in which the layers and nodes are designed and connected to each other is called "topology or architecture". The frequently used architecture is the "feed--forward" and "recurrent" architecture. The most used and famous architecture is the feed forward [START_REF] Lee | A multi--layer feed--forward neural network with dynamically adjustable structures[END_REF] where the network is build with startup input layer and ends with an output layer. Between these two layers there a layer called the hidden layer, where most computations will be done. Besides, in this design unidirectional road sections or connections connect the nodes or neurons. The second type is the recurrent architecture [START_REF] Guo | PMSM servo system based on dynamic Recurrent Neural Networks PID controller[END_REF] and it is the same structure as the feed forward the only difference is the kind of connections between the neurons. In this case the road sections are bidirectional or even recurrent providing feedbacks to the neuron itself. Using this kind of approach can be very helpful dealing with nonlinear complex problems. However, there are some disadvantages for example the ANN can be slow in converging to the final results [START_REF] Nandy | TRAINING A FEED--FORWARD NEURAL NETWORK WITH ARTIFICIAL BEE COLONY BASED BACKPROPAGATION METHOD[END_REF] and this is due to the nonexistence of physical insight in the construction of the mapping approximation of the results parameters. Moreover, using the ANN can be less accurate when the future traffic patterns did not exist in the training samples and also the number of weight in ANN is pretty large and time--consuming regarding the training process [START_REF] Meldrum | WA--RD 365.1 FREEWAY TRAFFIC DATA PREDICTION USING ARTIFICIAL NEURAL NETWORKS AND DEVELOPMENT OF A FUZZY LOGIC RAMP METERING SYSTEM[END_REF] [139]. It is clear that if we have more information we will have a rich hidden layer, which means that we are improving the quality of the predictions or the results; however, we are making the situation more complicated for the mapping process, which means that the convergence process to the results will take a lot of time to do so. To conclude, this technique is interesting but needs more adjustments to be done in order to improve it. And of course this opinion depends on our needs and also on the case that we are conducting.

Simulation Approach

Nowadays, traffic simulation models are becoming important tools for the assessment of the traffic infrastructure performance, traffic status, and driver's behavior analysis. Simulation can help in the validation process and also to predict the behavior of a system regarding different scenarios. Traffic is categorized as dynamic model. Thanks to this, we can represent the evolution of traffic over time. This representation will incorporate the notion of space and time variations. Besides, the characteristics of the road network are an important element in the creation of the simulation models. The dynamic models are segmented into two groups: macroscopic and microscopic models. But we will consider also the mesoscopic models, which is a combination of the two other models, cited above. The mesoscopic approach is when a large number of vehicles can interact in a quantum--mechanically correlated fashion.

Macroscopic Simulation

The macroscopic model has this ability to generate dynamic characteristics of the traffic flow, where it is considered in its general shape and not by its constituted elements. The macroscopic models are an analogy between the traffic flow and physics. Traffic is represented by aggregation to the characteristics of fluid mechanics such as density, speed, and flow rate. In this type of models the behaviors of the drivers is considered to be homogeneous. This kind of modeling assumes that the first movement of the vehicles depends on the overall state of traffic. The macroscopic models in general describe the evolution of time and space. The variables used to illustrate the empirical dynamics of the traffic are listed and determine the change in the flow. In addition, the model normally puts the hypothesis that the traffic evolution can be described by successive steady states. The most commonly used model to illustrate road traffic is LWF [Lighthill and Whitham, 1955] and [Richards, 1956] models. This model is build based on the analogy with fluids dynamics and it is a first order model. The LWF model is composed of three main equations:

• The velocity equation defined as the ratio of the flow on the concentration. • The conservation equation. (Coming from the conservation of the number of vehicles on a road section and for a period of time). • The fundamental diagram postulates that the speed of flow is obtained continuously for a steady state, it does depend only on the instantaneous concentration. This is an equation of state generally separating a fluid portion and a congested portion. The equations 2.6 are as follows:

! !, ! = !(!, !)×!(!, !) !"(!,!) !" + !"(!,!) !" = 0 ! !, ! = ! ! (! !, ! ) (2.6)
Where,

• Q(x,t) is the flow corresponding to the number of vehicles flowing in an abscissa x and at a time t per time unit. • K(x,t) is the concentration corresponding to the number of vehicles per unit of length lying on a section adjacent to the abscissa x, at time t.

• V(x,t) is the flow speed. • ! ! (! !, ! ) is the speed obtained from the fundamental diagram.
There is many research work done derived from LWF model. For example in [START_REF] Chevallier | A macroscopic theory for unsignalized intersections[END_REF] the author presents a dynamic macroscopic model which includes a system that presents a traffic light delay into a stream of vehicles entering a freeway. Moreover, the model is capable of predicting the average vehicle delays and also the queue length estimation. In addition, this latter estimation is compared to theoretical and empirical data. After this brief introduction about the macroscopic model, we will discuss the advantages and disadvantages of this kind of simulation. The main advantages of the macroscopic traffic simulation are the representation aspect. This means that the model gives the ability to simulate large road network. Besides, they are designed in order to size or resize infrastructure, obtain efficiency measures about: speed, density, travel time, traffic flow, and set back the travel time between pairs of origin--destinations. Concerning the disadvantages we can resume them to the fact that the details of any localized traffic is flattened out. This means that it does not make any representation of:

• Different type of vehicles • Driving style (playing with speed, acceleration, braking…)

• Drivers behavioral variations • Intersection To sum up, macroscopic models provide a global view of the traffic but not a focus analysis. The next section will be about the microscopic model.

Microscopic Simulation

In the microscopic models flow is not considered as overall homogenous when it is taken in its entirety because the models focus on the kinematics of each vehicle in the system. This means that the model takes into consideration the behavior of each driver in terms of its immediate environment. Moreover, the microscopic models have the ability to make assumptions about trigger actions from individual interactions between vehicles. Furthermore this kind of model is useful to test algorithms and methods to estimate travel time. For example in [START_REF] Blandin | Kernel regression for travel time estimation via convex optimization[END_REF] the author created an algorithm aimed at estimating travel time on road sections of a road network using a convex optimization framework. Then he used the approach presented in [START_REF] Chu | Using microscopic simulation to evaluate potential intelligent transportation system strategies under nonrecurrent congestion[END_REF] to evaluate the algorithm. The microscopic approach used allowed to accurately reproduce the macroscopic properties of traffic as well as inconsistent driving patterns observed in real life. Based on the article [START_REF] Chu | Using microscopic simulation to evaluate potential intelligent transportation system strategies under nonrecurrent congestion[END_REF] it is clear that the microscopic approach can help to evaluate the effectiveness of conceivable intelligent transportation system (ITS) strategies under non--recurrent congestion. The ITS strategies conducted in [START_REF] Chu | Using microscopic simulation to evaluate potential intelligent transportation system strategies under nonrecurrent congestion[END_REF] include incident management, adaptive ramp metering, traveler information systems, arterial management, and a combination of those strategies. The hardest part of the microscopic models is to formalize the specific movement of the vehicles such as lane change, arrivals at intersections. These actions require the calibration of decisional parameters like the influence of the vehicle on other lines, or the reaction time. The limitations of the microscopic models depend on the complexity of problem that the model is trying to solve. One of the main problems with microscopic traffic simulation is the heavy computation resource when we try to reproduce realistic patterns of traffic. However this model has some advantages, one of them being the focus on the driver, which means that he is localized at anytime. In addition, the aggregation of individual behaviors leads to the fundamental variables of traffic. This model gives you the ability to introduce heterogeneity in the traffic classes to learn more about vehicles and drivers. Finally, they allow real consideration of the interactions in the development of specific actions. The actual capacity of the transportation systems is not evaluated from the physical considerations of the infrastructure but from the interaction between the vehicles. This point pushes us to think about the general impact on the traffic flow and on the traffic status. To conclude, it seems that both microscopic and macroscopic approaches are motivating and by combining the two it will give interesting results regarding the flow of the traffic, density, and the travel time. Based on this view the next point will be the mesoscopic models, which are a combination between the two of them [START_REF] Lerner | The interplay of multiple scales in traffic flow: coupling of microscopic, mesoscopic, and macroscopic simulation[END_REF] (Figure 2

.5). Figure 2.5: Example of scale interactions and their representation by model coupling [49]

The illustration in figure 2.5 shows the characteristics that the mesoscopic models can give us. We can observe the macroscopic aspect of the traffic and we have this ability to zoom in and see the microscopic aspect too.

Mesoscopic Simulation

The mesoscopic models comprehend individual agents that refer to real vehicles. Additionally, the simulation is driven by the road characteristics such as junctions. This means that the mesoscopic model fills the gap between the macroscopic and microscopic models. In many researches conducted using this kind of model treated many issues like queuing networks [START_REF] Tolujew | Transport System's Mescopic Model Validation Using[END_REF], or sustainability aspect of traffic like studying Carbone oxide emission from vehicles and gas kinetic models [START_REF] Nagatani | Gas kinetic approach to two--dimensional traffic flow[END_REF]. Generally underneath mesoscopic models traffic flow details are described at high level. However, at the same time the flow behavior and interactions are shown at a low level too. This aspect has been helping a lot in analyzing the traffic status. For example in [START_REF] Gangi | Modeling Evacuation of a Transport System: Application of a Multimodal Mesoscopic Dynamic Traffic Assignment Model[END_REF] the author presents an application of multimodal mesoscopic dynamic traffic assignment model where he analyses the transportation system network under emergency conditions. To conduct this case an extension to a mesosscopic dynamic traffic assignment model was settled to determine quantitative indicators for estimating the exposure of the components regarding the traffic network. Imagining the movement of vehicles as packages travelling together can represent the mesoscopic operations. Each road section is subject to the following computation (equation 2.7):

! ! ! = !(! ! (!), ! ! (!), ! ! ) (2.7) Where,
• ! ! ! : travel time per road section i.

• ! ! (!): the flow.

• ! ! (!): the occupation.

• ! ! : other parameters to conduct. As it was mentioned before the mesoscopic models are a combination of microscopic and macroscopic models, which means that, they will combine the advantages and disadvantages of these two models. The mesoscopic models consume less time in computation regarding the microscopic models and they give more details than the macroscopic models. Moreover, it is not easy to design the mesoscopic models without drifting off to one of the models cited before (Macroscopic, Microscopic).

Similar Projects

In this section we focus on different projects aimed to answer the same question with which we are confronted in our thesis. We chose to discuss in this section the Mobile Millennium project and INRIX Traffic project. The objective of this literature survey is to gather technical elements and research methods, which will give an overview of different technologies available and applied methods. This section contains also a presentation of the PUMAS project, which constitutes a platform for our thesis to test and evaluate our research approaches in real life application for pre--industrial purposes.

Mobile Millennium Project

The Mobile Millennium project is identified in the field of research aimed at developing a system for monitoring traffic in real time and it is based on the GPS integrated in mobile phones to gather traffic information. The project was launched after a public--private partnership agreement involving the University of Berkeley, NAVTEQ (digital map producer) Calstran (The California Department of Transportation), and finally Nokia Research Center. The project was launch on November 2008, although research and data collection have previously started at the University of Berkley. This research project consists of three concrete applications and they are as follows:

• A mobile phone application has been made available to the public for 12 months. • An experiment size, in a controlled environment called "Millennium Century." • Finally, Mobile Millennium ensures the confidentiality and security of data.

System Architecture

The Mobile Millennium project [START_REF] Daniel | The Mobile Millennium Project[END_REF] aimed to gather data from probe vehicles preserving the anonymity of the sender of the information. This architecture as in shown figure 2.6 involves four different entities:

• Probe vehicle (carrying a phone with a GPS)

• Telephone operator (Network provider)

• A proxy server to ensure the anonymity of data • A reconstruction system traffic The system architecture is based on the concept of "Virtual Trip Lines" (VTLs). These are a kind of geographical markings stored directly at the client level; in our case it is the mobile phone.

The passage of a vehicle by a VTL launches an update of the velocity and position where it is performed at the proxy server via an HTTP request. This applies to the anonymity of the information; it performs a suppression of the MAC address and the identifier of the array antenna. Then transmit it to the server traffic reconstruction. Not to mention that all data exchanged is encrypted for safety and reliability reasons. The geographical aspect of VTLs facilitates the data anonymisation, because the only thing needed is the velocity at a point of several vehicles to estimate the traffic in the area; however, if the data is a timestamp kind, it is necessary to possess the identification of the vehicle in order to know its previous location; therefore, the estimation of the speed of the driven section will be possible. Finally the data collected are used to reconstruct the state of traffic and speeds on different axes using a reconstruction algorithm of traffic flow. The algorithm is based on non--linear flow models capable of reproducing accurately the impact created by an accident or a bottleneck. An algorithm of inverse modeling estimates the integration of these models. This algorithm is based on filters; two filters were tested, the Kalman filter and Newton relaxation "Nudging" [START_REF] Daniel | The Mobile Millennium Project[END_REF].

Mobile Phone Application

The operation of the application is based on a basic principle, when the application is launched on the free phone user; it sends information (position and velocity) of traffic each time they pass though VTLs, therefore, viewing real-time traffic conditions is visible. However this application is beyond the original concept of our project and the thesis work since the traffic information obtained by the user from a data fusion of different sources:

• Mobile phones with the application, all taxis in San Francisco (GPS data)

• Fixed speed cameras • Magnetic loops and historical data. 5000 users have downloaded the application over the period where the software was available. Today, the application is no longer available but the users who have previously downloaded it remains operational.

Millennium Century

Century Mobile is a full--scale experiment that took place on 8 February 2008 to study the feasibility of the System. The aim of this experiment is to estimate the traffic based only on data from the GPS integrated in mobile phones (Smartphone). The experiment involved 100 cars equipped with mobile phones Nokia N95 (with GPS) on a portion of highway about 16 km for 8 hours. This stretch of road was chosen because it has a large number of loops and also the presence of bottleneck. The Berkeley has mobilized 165 students to drive these cars between 10h and 18h. The objective was to determine if it is possible to estimate the statue of traffic with just the information sent by the "Smartphone", especially with a low penetration of vehicles. The VTLs were placed at the same locations as the magnetic loops in order to establish a comparison. These comparisons were made on two portions each one is having a clean penetration rate (3 to 4% for the left side, rarely more than 2% for the right portion). Here is the result in (figure 2.7) [START_REF] Daniel | The Mobile Millennium Project[END_REF]:

Figure 2.7: Penetration Rate (Magnetic Loops vs. VTLs) As expected, the results are less accurate when the precision is high. However, it is interesting to note that even with a low penetration rate, information is of high quality and comparable to those obtained through the magnetic loops for a much lower cost. This experiment was therefore successful.

Conclusion

The project has achieved its goal of estimating traffic by collecting GPS data from mobile phones, even with low penetration rates while respecting the confidentiality and anonymity of data. However, the project was informing about only the main roads in the city not all the road sections.

INRIX Traffic Project

INRIX is a private company based in Seattle created in July 2004 by two former Microsoft executives. It is a leader in the field of traffic information in the U.S., either historical or real--time prediction. The principle is simple and relatively common to other projects. It develops in three stages [START_REF] Lomax | Refining the Real--Timed Urban Mobility Report[END_REF]:

• The collection of information through various sources (trade name: Smart Dust Network). • The analysis and treatment with the Fusion Engine.

• The redistribution results to various organizations and devices. 2. [START_REF] Li | Arterial Travel Time Estimation Using VII Probe Data and Point--based Detection Data[END_REF]

.2.1 Smart Dust Network

A major benefit in INRIX system is the number and diversity of data collected. In fact it consists of more than 350 sources such as GPS traces provided by corporate fleets (taxis ...), existing sensors belonging to public bodies (up to 90% of the existing sensors in United States) such as magnetic loops, data from cell phones, information on accidents and construction cites but also information on the present and future climate or one--time events (concerts, games ...). Thus, INRIX own announcement dated and past information on average speeds for more than 1600000 km 400000 km in the USA and in Europe through 6 countries (France, Germany, Netherlands, Belgium, Luxembourg and the United Kingdom) and that real--time data representing 126 urban and 260000 km of roads to the United States and 400,000 km of inland different to Europe [54].

Fusion Engine

Another strength of INRIX system is their analysis program, processing and data fusion system named Fusion Engine. The Fusion Engine is based on Bayesian network and it uses different proprietary algorithms error correction to deal with data acquired via the Smart Dust Network. Another feature of the Fusion Engine is the use of error detection algorithms, and it allows also:

• The detection of dysfunctional traffic sensors as magnetic loops that can sometimes take longer to repair. The process is almost in real time, so that data provided by these sensors are not taken into account by the Fusion Engine in its calculations; • Collaborative filtering: in fact, by combining different sources of information about a geographic area at a given time, INRIX is able to detect the data off sketches or outliers, comparing different information received; • Optimization of spatial granularity: thanks to the diversity of sources and their number, INRIX is able to determine real--time traffic conditions with good accuracy. Regarding the quantity of data available at a specific time on a geographical area, the Fusion Engine is able to adjust in real time the accuracy or spatial granularity of data to maximize the accuracy of the traffic information; • Although when the data are insufficient for a given stretch of road, which means when the minimum error threshold is not reached, no information will be given to that concerned road portion.

Conclusion

As we have seen, INRIX is positioned on the market at different levels: It provides both solutions directly to the end user (mobile application), data to integrators (manufacturers or manufacturers of GPS) or data for the public sector. Based on this last point, INRIX approaches PUMAS project objectives. However, INRIX and mobile millennium focuses mainly on major routes, roads and highways. Conversely, the project PUMAS is more interested in the entire urban traffic networks.

The PUMAS Project System

The project PUMAS is a pre--industrial project involving industrials and research laboratories. This variety creates an atmosphere full of different views and helps to create a flexible system design, where it was easy to conduct research and also industrial view. PUMAS stand for urban platform for advanced and sustainable mobility (Plateforme Urbaine de Mobilité Avancée et Soutenable). One of the main contributions of this dissertation has been design, implementation, and testing of preprocessing module of the PUMAS project System. This section presents an overview of the project and how our work is related to it. Moreover, the design decisions include using Historical database and real time data provided by our probe vehicles.

Introduction

PUMAS is a project labeled by competitiveness clusters Mov'eo (DAS Mobility Solutions) and Advancity (COS New uses and mobility). It was held at the call for proposals No. 8 Unified Inter--ministerial Fund (FUI). PUMAS is funded by the state (DGCIS --General Directorate for Competitiveness, Industry and Services), Ile de France and Haute--Normandie Region FEDER (European Union). The project aims to develop mobility platform software, and to evaluate the territory of the Community of Agglomeration of Rouen Elbeuf Austreberthe (CREA). The project offers urban areas one integrated solution, flexible and economical:

• Knowledge of traffic conditions and real--time decision support;

• The development of sustainable mobility;

• Measuring the emission of Greenhouse Gases. Nowadays, collecting data about traffic is available using different kind of sensors. However, there is no tool to extrapolate the state of the circulation and the air quality in a dynamic and real--time manner over the whole territory. PUMAS try to give an answer to these needs by innovating ideas:

• Data collection method based on probe vehicle, less expensive and more flexible than traditional data collection by sensors embedded on the ground; • Dynamic transmission architecture to use the best available data from probe vehicles in different places and times;

• Calculations performing real--time prediction and estimation of travel time; Participate in the emerging sustainable economy where public transport systems are an alternative to road networks by providing better information on traffic conditions.

System Architecture

To view a system architecture there are many ways but we chose to show the functionality architecture of the system as it is illustrated in (Figure 2.9). There are two components, the server and the embedded box in the cars named PUMAS Box. The PUMAS Box is capable of collecting information about probe vehicle journey. The Box performance can be resumed as follows:

• The ability to gather data, the GPS position, travel time, traffic jam.

• The ability to temporarily store and process data • The ability to store reference data (eg. Mapping)

• The ability to communicate data to a server: GPRS or WiFi,

• Power supply (cigarette lighter or installation)

• The ability to read other sensors (plug OBD2, CAN)

• Functionality Automatic update of software Concerning the server, it can specify tasks such as gathering information sent by PUMAS Box or historical data, filter the data, save the data into the database, process the data in the database. Moreover, the server is capable of enriching the historical database and process all the information in it. In order to improve server performance, it was necessary in addition to the treatments mentioned above, the following tools:

• Monitoring of data processing (reporting of treatment)

• Support for the production of maps (OpenStreetMap size)

• Help the placement of PUMAS Points (map + statistics)

• Production of updates for packages shipped (invisible to the user)

• PUMAS Administration Server. After describing the PUMAS system architecture lets describe the nature of data stored in the databases. This latter is really important to understand it because the work done in this dissertation is related to the data collected from the real world field that constitute the historical database. way to run on. Concerning the sparsely sample GPS information the module will prepare this data and filter it in order to be enrich with travel time estimation per road section. In order to do so, the system will create the digital map and filter the data from GPS errors and coherence errors. Then, it will reconstruct the itinerary of the probe vehicles. Finally it will run the algorithms to estimate the travel time per road section or what we call PUMAS section. Processing The processing module contains two main algorithms that will make the traffic information nicely viewed. The first algorithm is a simulation process of the evolution of travel time estimation based on the belief propagation approach. It was created and developed by our partner in the project INRIA [START_REF] Furtlehner | A Belief Propagation Approach to Traffic Prediction Using Probe Vehicles[END_REF]. The second algorithm is regroup all the travel time collected or estimated from the historical data during the preprocessing step to reconstruct a general view of traffic status. This latter was created and developed by our industrial partner in the project EGIS [START_REF]Egis is a consulting and engineering group working in the fields of transport, urban development, construction, industry, water, environment and energy. In the road and airport fields, the group is also involved in project financing, turnkey--contract projects and facility operation[END_REF]. Then all the information coming from these algorithms will be regrouped in such a way to cover the whole urban network with travel time information per road section and also traffic jam detected in real time.

Server Manager

The server manager module is in charge of displaying the information given by the processing module and display it in a nicely way. Moreover, it process the data used in order to store it in the archive database. This module is in charge of doing any kind of update regarding the functionality of the whole system or regarding the digital map if needs an update. Besides, an external supervisor where he can supervise and check if there is any problem in the server system can control this section. The module does also an analysis of the information collected from the previous section in the chain. This latter process helps to detect the trouble if there is any and also locate the origin of the problem. Output The output of the PUMAS system will be a digital map representing the urban road network. In this map they will be information about the traffic, where travel time is specified per road section and also the traffic status (detection of any traffic jam). The output framework gives a real time visualization of the output of the PUMAS system. Moreover, inside the system there are two modules of analysis and evaluation that can be viewed too. This later and output can be used for optimization or research in the future.

After giving a general overview about the PUMAS server system, the next section will be about the data collection process and the experiment done in the real world field.

Data Collection and Field Experiments

The purpose of the experiment is to collect data from the real--world field. During the experiment we used three instrumented vehicles. The experiment allowed us to obtain data from the fields in sufficient quantities to calibrate and analyze the behavior of travel time estimator algorithms. Firstly, we defined constraints such as jams in small urban road or in the bridge sections that we might face in order to test the performance of the system in tough situations. We chose the itineraries based on those constraints. Our aim in the first scenario is to test our embedded system in the car's PUMAS Box (Figure 2.10). The PUMAS Box is a system that sends information to the server such as GPS position, traffic jam if detected (discussed in section 2.5.2), etc. Besides, it collects the data that we need for testing the travel time estimation algorithms.

Figure 2.10: The Embedded System PUMAS Box We had the chance to choose the city of Rouen, France, which has a multitude of different kinds of urban area roadway including bridges in the downtown, expressways, and small roads between buildings. The city is an excellent test-field as it affords a variety of scenarios with different situations regarding the road infrastructure (Figure 2.11). Moreover, the fact that the itineraries during the experiment were chosen based on the displacement of the traffic observed on the real--world field; will lead us to have a variety of situations. Besides, the data acquisition in the field was based on different modalities such as traffic flow, traffic density, rush hours, etc. Three Citroen C3 LaRA with their embedded systems consisting of: PC with RT maps (software with a component based framework for rapid development of multi--modal applications), a PUMAS--BOX connected to the PC and communicating with the server, a fixed GPS, a color camera positioned at the windshield, a sparsely sample GPS box transmitter; which we used in order to test our system and collect data in the real--world field. Moreover, C3 LARA is the first prototype of an intelligent vehicle that was developed by the robotics center of the Ecole des Mines de Paris and IMARA team from INRIA, France.

• Modes of transmission--type WiFi and GPRS.

• Server to retrieve data from PUMAS--BOX. The experiment took place in the city of Rouen, France over three days. The outcome was more than 1400 km driven and almost 4GB of data was collected. The data collected will be used to simulate our needed data and also to construct a reference data in order to run our tests and also compare our results.

Conclusion

This section has covered four main parts. First, we presented the methodologies adopted to estimate travel time based on the technologies used to gather traffic information. The second part was about the different kind of models that help to estimate travel time. Then, we presented a state of art about the similar projects that treats the same problematic. Finally, the last part was a description of the PUMAS project, this being important for the understanding of the context of this dissertation and thesis research.

Chapter 3: Preprocessing Tools 3.1 Introduction

There are two types of data used to estimate travel time. Data collected from fixed sensors on the roadside [START_REF] Del Arco | Vehicular Sensor Networks in congested traffic: Linking STV field reconstruction and communications channel[END_REF] and another one coming from floating cars [START_REF] Teemu Leppänen | Sensor Data Fusion Middleware for Cooperative Traffic Applications[END_REF], [START_REF] Corrado De Fabritiis | Traffic Estimation And Prediction Based On Real Time Floating Car Data[END_REF]. The one that interest us regarding our thesis will be the second type. The most common floating car data is collected from delivery vehicles or taxis and this type of vehicles are almost all the time on the freeway, highways, urban roads, or arterials roads. Based on the last idea it is clear that this kind of data coming from this kind of vehicles is convenient for the estimation of travel time in urban areas. As we know there is nothing perfect, which means the second type has positive and negative attributes. The first thing that will come to mind especially nowadays is the cost of this data. It is really cheap to get them regarding other type of data collection. And this is due to the fact that all the companies collect those data for marketing purpose, business, or logistics optimization, which made those data available in a large scale. However, the data provided from these floating cars are sparsely sample GPS data where the frequencies vary between 1 to 3 minutes. The reason why is that those companies running the system do not need to know precisely the path of their cars. They need only to know the areas location. Another challenge is that this kind of data presents the need of preprocessing before processing any computation to estimate the travel time. Building a traffic system to estimate travel time per road section using millions of data coming from floating cars is an algorithmic and computational challenge. In order to make good estimations preprocessing the data is a must; therefore, the error coming from the data is reduced. The preprocessing steps have various subcomponents that need significant research work, development, and integration to be done. This section presents the preprocessing that has been done in this thesis work to make our sparsely sampled GPS data ready to be used for travel time estimation. The first step is to represent the urban network by building a road model using geographic information system (GIS). This step is crucial for the travel time estimation using floating cars information both for data collection and also for the results analysis [START_REF] Zito | The use of GPS in travel--time surveys[END_REF], [START_REF] Taylor | Integration of the global positioning system and geographical information systems for traffic congestion studies[END_REF].

The second step is the data check or coherence check. Working with sparsely sampled GPS data implies a frequency in the data reception time. Thus the data frequency should be checked for any incoherence in the frequency or ambiguity. The most common and intuitive procedure, and also which is used in this work thesis is to track the number of consecutive GPS points that are less than a specified time distance (1 minute) from each other. The third phase is the map--matching process. This step is very important to the travel time estimation process. Moreover, the map matching is widely conducted in research applied to transportation. It seems that this field of research on map-matching techniques is still challenging and potentially difficult. During the thesis work the map--matching technique has been used with enhancement in the algorithm to improve the performances. Finally, the last step in the preprocessing part is the path reconstruction. This step is very important for the travel time estimation per road section. By using sparsely sampled GPS data, we need to define the road section taken by the probes. This process is a graphs problem well known in computer science, operation, and transportation research and it will be used in by the map matching process.

Urban Network Representation

As it was stated in the section (3.2) this part is about the building of the urban road networks using GIS information. This rubric contains an introduction about the importance of GIS information in constructing road networks. The following section is about road models that constitute information about the road and it is important for estimating traffic status. Besides, the context of the digital map is very important regarding the purpose of use. Finally, the extraction technique used in order to build the digital map using GIS with the information needed. All the work presented here in this dissertation section was implemented for the thesis purpose and also for the PUMAS project.

Introduction

Today, with the technological evolution many domains have been influenced, especially the geographic representation of maps has evolved from paper illustration to digital or numerical [START_REF] Li | Construction of GIS scientific experience zone based on experience learning theory and constructivism[END_REF]. Besides, thanks to the evolution of databases all the geographical information are stored and integrated often by the geographical information system (GIS). The GIS is really useful because they make many tasks easy to do such as spatial planning for cities and land use. Moreover, in transportation planning and logistic, it is advantageous to use digital map or numerical incorporated with information such as transportation facilities data, speed limits, roadway indicator, and type of roads. All this information is very helpful to improve traffic algorithms and estimations. There are two kinds of GIS mapping data the vector model and the raster model. The vector approach is designed to store and encode as collection of coordinates. For example in our context the road will be encoded to a linear feature of a set of point coordinates. However, the raster model encodes the road map to a collection of multiple grid cells. Each of these approaches has advantages and disadvantages. For example the advantages of Vector data can present as follows:

• Data can be represented at its original resolution.

• Graphic output is usually more visually pleasing;

• Accurate geographic location of data is maintained.

• Allows for efficient encoding of topology, and as a result more efficient operations that require topological information such as proximity, network analysis. However, it has also some negative aspects like:

• The location of each vertex needs to be stored explicitly.

• For effective analysis, vector data must be converted into a topological structure. This is often processing intensive and usually requires extensive data cleaning. As well, topology is static, and any updating or editing of the vector data requires re--building of the topology. • Algorithms for manipulative and analysis functions are complex and may be processing intensive. • Continuous data such as elevation data is not effectively represented in vector form. Usually substantial data generalization or interpolation is required for these data layers.

• Spatial analysis and filtering within polygons is impossible

To sum up the analysis of Vector data approach: their coordinates define the map elements such as points, lines and polygons. The structure describing topological relations between different objects provides a faithful graphical representation. The advantages of this system characterized by better management of databases data, and better graphic measures are more accurate than they are. Its main disadvantages are to be able to present a more complex data structure. After checking the Vector data we will move to the raster data. The advantage can be illustrated as follows:

• The geographic location of each cell is implied by its position in the cell matrix. Accordingly, other than the origin point such as bottom left corner, no geographic coordinates are stored. • The programming is usually easy thanks to the nature of the data storage technique data analysis. • The inherent nature of raster maps, for example one--attribute maps, is ideally suited for mathematical modeling and quantitative analysis.

• Discrete data, which facilitates the integration of the two data types.

• Grid--cell systems are very compatible with raster--based output devices like electrostatic plotters, graphic terminals. Concerning the disadvantages of the raster data are as follows:

• The cell size establishes the data illustration resolution.

• It is difficult to represent linear features depending on the cell resolution. Consequently, network linkages are difficult to establish. • Processing the data attributes may be heavy to do so if the existing data is large. Moreover, the Raster maps inherently reflect only one attribute or characteristic for an area. • Since most existing input data is in vector form, thus a conversion vector-to--raster is needed which means extra processing (time consuming). • Most output maps from grid--cell systems do not conform to high quality cartographic needs. To summarize the raster model, the area is subdivided to represent a grid of cells. Each cell contains digital information relative to an identifier, a qualitative or quantitative parameter. This is comparable to the term "pixel" (picture element) which is the smallest information unit contained in an image divided into grid. The dimensions of the cell are the resolution space. After introducing the GIS information, the next sections will discuss how we choose to represent our digital map. Based on the PUMAS project needs and also by conducting research approach we will show how we choose the appropriate approach. This part is a challenge in finding an compromise between industrial needs and research approaches that can adopted in order to be productive in the practical world (real word life situations).

Road Model and Digital Map

The road model in standard case involves information about geometric and topological characteristics of urban roads; all this information follows a hierarchical structure. The road system model describes the characteristics of the streets and roads in a large scale of transportation system. The road model can be defined in different ways depending on the research case and it is a part of the GIS information. Both of road model and GIS constitute the final results, which is the digital map. Moreover, using a digital map in our case will assure us the following statements:

• Maps ensure consistency and facilitate traffic analysis operations.

• Maps support data collection and can help monitor vehicles and traffic activities.

• Maps make it easier to present, analyze and disseminate traffic estimation results. 59 In addition, technology evolution has given a considerable push to GIS information. For example nowadays, we have better database software that allows managing a vast amount of information, which is referenced to digital map. Starting from this point the real world structure contains enough information or objects such as road network, road junctions, road sections, nature, etc. All this information is incubated in the digital map in order to approach a replica of the real world. Moreover, this information is organized in what is called GIS layer. This latter contains information that is not affected by any relation between the objects or layers. The real world represented by GIS information encloses many layers as the (Figure 3.1) shows. Besides, in our case the need for modeling large areas (urban road network of Rouen) pushed us to choose the digital map, which is the best solution till now. Unluckily, most of these are used for routing purposes; consequently, it does not contain fine--grained information about the junctions and the connections lanes over junctions [START_REF] Hormann | Simulation for Inter--vehicle Communication Based on Traffic Modeling[END_REF], [START_REF] Krajzewicz | Preparation of Digital Maps for Traffic Simulation; Part 1: Approach and Algorithms[END_REF].

Figure 3.1: GIS Layers Based on this analysis, it is important to add information to our digital map in order to improve the travel time estimation, map--matching, and path reconstruction. That's why we will add information about the junction and their lane road sections by detecting their locations. The section before introduced the vector data, which contains coordinates defining the road network map elements as points (Coordinates). Based on this, we will choose the vector data approach because it will give the information needed in order to construct the added information to the digital map in an easy and flexible way. Thus, we will introduce a PUMAS point as the intersection between two different roads, the zone around this junction will be a PUMAS zone, and a PUMAS section is the set of segments and nodes between two PUMAS points (Figure 3.2). In the previous paragraphs, we described our approach concerning the road model and its implication regarding the digital map. The next level, will be putting enlightenment on the context model. Since, the road model is extended by the knowledge about the context. The following section will analyze the context of our work in this thesis and define what we need as information to add to our road model that will be viewed on our digital map characteristics. The global context is related to the background objects such as buildings or vehicles. It is possible to find that the background information and the traffic roads have a relationship that give important information when it is combined and also there is the case where the roads show a typical obvious feature that is important. As a consequence, the road model and the context should be adapted to the region of interest where information is useful. However, in the urban road traffic context, the only thing that is very important is this relationship between the road and the vehicles, as Baumgartner et al stated it in his articles [START_REF] Baumgartner | Automatic road extraction in rural areas[END_REF], [START_REF] Baumgartner | Automatic road extraction based on multi--scale, grouping and context[END_REF].

Concerning the local context it is when we assign a relation between a small road number and the context objects. For example, in dense urban areas, the building footprints are almost parallel to the roads and vice--versa. The relation in this case is an occlusion or cast shadow on. Besides, all this relation must be implemented in the extraction process and internal evaluation. However, for our case we will not focus on this aspect because we are not willing to create a new digital map from scratch but one by taking into consideration the relationship between road and vehicles. This decision is based on our objective regarding the thesis work and the project PUMAS. The next section is about the map extraction strategy adopted in order to build our digital map by taking into consideration all the decisions made during the analysis presented in section 3.2.2 and 3.2.3.

Extraction and Digital Map Building Strategy

For our thesis work the best representation of the digital map is the direct graph, which means the digital map is built based on the set of nodes and road sections. This kind of representation is based on vector data as it was stated before this is the right representation for our case. Besides, for anything related to traffic estimation it is indeed the most used [START_REF] Census | Topologically Integrated Geographic Encoding and Referencing system[END_REF] by most map databases for navigation and display purpose. For these reasons in order to achieve our objective of this thesis, "Open Street Map" [START_REF]www.openstreetmap[END_REF] has been chosen as a source to extract the digital map. OpenStreetMap (OSM) is an international project established in 2004 to create a free map of the world. The data collected contains many kind of information such as the roads, railways, rivers, forests, buildings and more. The data collected are re--usable under a free license ODbL (since 12 September 2012). Moreover, this latter is an open source data built by consumers and it is an online access designed to build free editable map of the whole word from GPS traces uploaded by users around the world [START_REF] Haklay | OpenStreetMap: user--generated street maps[END_REF]. However, the physical representation of the road network topology is not accurate or unavailable. Thus, it is important to add the road layout such as intersections and junctions. For this reason, we will add these features that we described clearly in section 3.2.2 (PUMAS points, PUMAS sections, PUMAS zones). Figure 3.4: View of the Digital Map through the Process All the data are stored in the database of raw data. Moreover, the system is capable of doing update to the map directly from the OSM data and processes the PUMAS Kits to add the characteristics. Now after creating the digital map the next important part before doing any travel time estimation is preprocessing. The raw data used should be checked and cleaned and also mapped to the digital map or what is called the map matching process. The next section will debate these issues.

Raw Data Check and Map Matching

The purpose of this section is to put a light on the importance of validating the raw data before using it. The use of sparsely sampled data presents many challenges concerning the path reconstruction and the map--matching process. The Map matching process is the process of aligning a series of observed user positions with the road network on a digital map. It is a preprocessing requirement step for many applications, such as traffic flow analysis and travel time estimation, which is the case of this dissertation.

Introduction

Estimating travel times per road sections on a urban road network requires an efficient path reconstruction and accurate map--matching, which is the subject of the algorithms described in this section. As it was described in the section 2.3.6 the sparsely sampled GPS data has this characteristic of sending GPS information at a fixed frequency, which is unusual to use for road section travel time or measuring velocities. This type of data presents many challenges. The first challenge is the frequency of the data that has consequences on the path reconstruction. The probe vehicle can often travel a multiple of road sections between two successive GPS measurements when the frequency is high. Thus, estimating the path travelled by the probe vehicle will have low probability of precision. As consequence it will affect the travel time estimation. For all these reasons the process of running a check or validation of the raw data is a must. The section 3.3.2 will introduce the approach adopted in our case to validate the data used in this dissertation work. The second challenge is about the map matching. The GPS data measurement should be mapped to the digital map in order to know the exact location of the probe vehicle. Thus the exact location and the path reconstruction between two successive GPS data is a must for the travel time estimation. The third challenge is the path reconstruction. The path reconstruction is related to look for the realistic path taken by the probe vehicle. This process is very important in order to know the concerned road sections that are involved in the vehicle itinerary. This latter is very important in the travel time estimation per road section. Based on this introduction it is important to enlighten the fact that any estimation model needs precise information about the digital map (Section 3.2) and the data itself, which means path and location. For these reasons the following sections in this chapter will describe how we managed to reduce the errors coming from the raw data by introducing new approaches in dealing with these issues cited above.

Raw Data Check

The raw data that constitute our historical database is a sparsely sampled GPS data. Sparsely sampled probe GPS data is currently the most ubiquitous data source on the arterial network or urban network. Thus in order to make a check of data frequency or what we call time step let's start by illustrating the data. The raw data contains information of probe vehicles let's put !" ! {! ! , ! ! , ! ! , … , ! ! } the set of floating cars in the database. Each floating car ! ! has a set of GPS locations and time information. We will note

! ! ! ! {! ! ! , ! ! ! , ! ! ! , ! ! ! , … ! ! ! }
ℎ ! ! = ! !!! ! -! ! ! ! ! ! = ! !!! ! -! ! ! (3.1) Where, ℎ !
! check the time step between the first data and the second one.

However, ! ! ! check the time step between the first data and the third one.

Moreover our sparsely sample GPS data has a frequency of one minute; therefor, we will define the step ℎ ! = 60 !"#!"#$ and the second step ! ! = 120 !"#$%&s.

The defined steps will be used in our equation in order to make a decision. We define our two check functions (equation 3.2 and 3.3) as follows:

ℱ ℎ ! ! = 1 !" ℎ ! ! ≤ ℎ ! 0 !" ℎ ! ! > ℎ ! (3.2) And, Τ ! ! ! = 1 !" ! ! ! ≤ ! ! 0 !" ! ! ! > ! ! (3.
3) The conditions defined on the two function above was based on the fact that there is a risk regarding the results of our work in this dissertation when the sparsely sampled GPS data with intervals beyond 60 seconds. For example, reconstructing the path will be affected and also the travel time estimation. Finally, we define our check operator as follows (equation 3.4):

ℱ ℎ ! ! + Τ ! ! ! ≠ 0 , !ℎ!" !" !"#$%"&' !ℎ! !"#" !" !"#"$%&'( !"#$ ! ! ! - ℱ ℎ ! ! + Τ ! ! ! = 0 , !ℎ!" !" !"#"$% !ℎ! !"#" !" !"#"$%&'( !"#$ ! ! ! !!!!! !!!!!
(3.4) The following chain graph shows the building tree structure in order to make the raw data validation using the equation 3.4 (Figure 3.5). The graph shows how the computation structure is built and in each cell we will find the out put of this equation ℱ ℎ ! ! + Τ ! ! ! and then we apply the rule presented above in order to make a decision of keeping the data or not.

Map Matching Process 3.3.3.1 Overview

The map--matching problem is related to the correlation between the probe vehicle path and the vector map of the concerned road section. The problem aspect can vary depending on the input data and also on the desired output. In our case we are concerned by the current position of the probes in our historical database and the input that is the sparsely sampled GPS data. The purpose behind using the map matching is to correct the GPS localization errors. The trajectory mapping has to process a stream of infrequent position samples and map them to an accurate itinerary. Using the sparsely sampled GPS data brings up a challenge of processing inaccurate data and matches them to an accurate trajectory.

In the literature we can classify the map--matching technique to three kinds or approaches: geometric approach, topological approach, and enhanced approach.

The geometric approach takes into consideration the shape of the road section and the GPS position. In other word, each GPS position is matched to the closed node detected on the road section extracted from the digital map. It is exactly what Bernstein and Kornhauted (1996) named point--to--point matching and the method does not take into consideration the way road sections are connected. Another type of geometric approach is point--to--curve method. In this method as it was clearly stated by [START_REF] Kim | Efficient use of the digital road map in various positionning for ITS[END_REF] [67] the fixed GPS position is matched to the closed curve by using an orthogonal projection on the concerned road section. The other type is called curve--to--curve [START_REF] White | Some map--matching algorithms for personal navigation assistants[END_REF]Phuyal, 2002) and it refers to the probe trajectory is matched to the digital map road sections. Moreover there are many studies and research done by combining all these methods described above such as (Taylor, 2001;[START_REF] Bouju | Location--based spatial data management in navigation systems[END_REF]. The next type is related to the topology of the roads, which means the relationships existing between the entities like points, lines, and polygons. The relationships can be categorized as follows: adjacency when it's a point, connectivity when it's a line, and containment when it's a polygon. We could also combine the geometry with the topology as it was done by Greenfeld (2002) where the map matching is using the geometrical road sections and also the connectivity and contiguity of the road sections. The last category is the enhanced map matching and we mean by that when the algorithm uses such as Kalman filter, particle filter, fuzzy logic, etc. For example, [START_REF] Honey | Vehilce navigation system and method[END_REF] hosted in his article [START_REF] Honey | Vehilce navigation system and method[END_REF] the first kind of map matching technique. He used DR sensor positions and then used the map matching to match them into the map. This method has been discussed in many publications [START_REF] Kim | Efficient use of the digital road map in various positionning for ITS[END_REF], [START_REF] Yang | THE MAP MATCHING ALGORITHM OF GPS DATA WITH RELATIVELY LONG POLLING TIME INTERVALS[END_REF], one being the [START_REF] Zhao | vehicle location and navigation system[END_REF] where GPS data was used instead of DR sensor positions.

Moreover, Zhao states that the error region can be derived from the GPS error variance. Thus, we can detect the road sections that have a high probability that the GPS position should be associated to them without scanning the whole map.

Problem Statement and Definitions

In order to understand the problem of map matching for sparsely sampled GPS data trajectories we will define it in a formal way: Definition 1: (GPS Trace) A GPS trace is a set of GPS position of a specific probe vehicle . Each position contains the following information: latitude "lat", longitude "lng", timestamp "t " and the vehicle heading.

Definition 2: (Probe Trajectory) the probe trajectory T is a set of GPS position with a time interval between two successive GPS position. The GPS positions don't exceed a certain threshold . For example: , where and . and . Definition 3: (PUMAS section) is a road section "s" associated with an id. Each section contains the following information: length value s.l, a starting point s.start, ending point s.end, and a set of node and segments or polylines describing the road section in the digital map. Definition 4: (Road Network) is direct orientated graph G(V,E), where V is a set of vertices representing the road aspects such as intersections, junction, and terminal points. Finally, E is a set of edges illustrating the PUMAS sections. Definition 5: (Path) is a set of connected road sections which means in our case is a set of PUMAS sections thus where . Now we can state the map matching problem as follows: Given a raw sparsely sampled GPS data trajectory T and a road network G(V,E), find the path P from G that matches T with its real path.

Map Matching System

To describe clearly the map matching that we adopted in our thesis work and also in order to show the modification added. The structure was built this way as it is shown in the (Figure 3.6).

! = c 1 , c 2 , c 3 ,..., c n { } c i !! !T = 1min ute T : c 1 ! c 2 ! c 3 ! ... ! c n c i !! 0 < c i+1 t < !T (1 ! i ! n) P : s 1 ! s 2 ! s 3 ! ... ! s n s k .start = V i , s k .end = V j , s k+1 .end = s k+1 .start, s k .cape,1 ! k ! n Figure3.

6: Map Matching System

The system can be split into three main processes. The data preprocessing is the step where the data is prepared in order to be checked. In the preprocessing data analysis the data will be analyzed following some regulations regarding spatio-temporal rules or analysis. Finally, the results step is when the data is matched to the digital map with respect to the path reconstruction [START_REF] Hadachi | Increasing the Travel Time Accuracy in Arterial Networks using Particle Filter and Enhanced Map Matching[END_REF] that will be discussed in details in section 3.4.

Data Preprocessing

This component contains information about road network (edges, vertexes) and GPS traces from the probe vehicle (historical database). Each GPS trace is a GPS trajectory from the probe. This latter will be used to retrieve each possible situation for each GPS sample data. In other words, the system will build a set of all GPS samples and their candidate road sections they lie on. Thus for a given trajectory , we retrieve the entire PUMAS sections candidate for each GPS position within a radius r defined by the GPS receiver error. The next step is to get the line segments candidate where the orthogonal projection of will be on the PUMAS sections. The line segment orthogonal projection will be defined as follows: Definition 6: (Line segment orthogonal projection, LSOP) the LOSP of a position to a PUMAS section is the point on such that , where is the distance between and any point on s.

T : c 1 ! c 2 ! c 3 ! ... ! c n c i c i c i s i p s i p = argmin !p i "s dist( p i , c) dist( p i , c) c p i 69 Definition 7.
(Notation) we will note the jth candidate edge and the jth candidate of point (illustration figure 3.7).

Figure 3.7: Candidate projection points for a sample pi After selecting all the potential candidates the issue now to find the best match trajectory .

Preprocessing Data Analysis

In this step we were inspired by (Zhao,[START_REF] Isard | CONDENSATION --Conditional Density Propagation for Visual Tracking[END_REF] [69] approach and we will conduct two analyses to match the trajectory. First the process will start with a spatial analysis and then a temporal analysis. Spatial Analysis: This analysis takes into account the distance between a single GPS position and its PUMAS sections candidate. Moreover, it will take into consideration the road network topology to avoid redundant information about the paths. To determine the path we will use the shortest path algorithm (Dijkstra) that we will discuss in details in section 3.4. In order to do this analysis we will define what we call an inspection probability function. Definition 8: (Inspection probability function) it is defined as the likelihood that a GPS position matches a candidate using the distance between these two parameters . If we want to model the GPS error measurement it can be modeled as a normal distribution [START_REF] Bormann | The spatial structure of observation error in the atmospheric motion vectors from geostationary satellite data[END_REF] of the distance between and . This probability indicates the weight of the fact that the point can be matched to . We define the Inspection probability function as follows (equation 3.5):

s i j p i j p i Pc : p i j 1 ! p i j 2 ! p i j3 ! ... ! p i j n T : c 1 ! c 2 ! c 3 ! ... ! c n c i p i j dist( p i j , c i ) c i p i j c i p i j 70 (3.5)
Where, is the distance between and . For the mean it will be a zero mean and the standard deviation equal to 20 meters based on the empirical evaluation. The inspection probability function does not take into consideration the context where the GPS position it is. For that reason it can be some situation when matching will be wrong. For example we can have a situation when GPS location has been matched to the wrong PUMAS section, as shown in (figure 3.8) where the matched point was in another PUMAS section and there is no link connecting the two PUMAS sections. In order to solve this issue we will introduce the transfer probability function. Where,

•

is the Euclidian distance between and .

• is the length of the shortest path given by the algorithm defined in section 3.4 between and .

!(

p i j ) = 1 2!" exp (y i j " µ) 2 2" 2 # $ % & ' ( y i j = dist( p i j , c i ) c i p i j p i z p i+1 e c i c i+1 c i c i+1 p i z p i+1 e !(c i " c i+1 ) = De i"i+1 L (i,z)"(i+1,e) De i!i+1 = dist(c i+1 , c i ) c i+1 c i L (i,z)!(i+1,e) p i z p i+1 e
Therefore the spatial analysis function will be the combination of the inspection probability and the transfer probability. It will be expressed as follows (equation 3.7):

(3.7) The spatial function explicitly computes the likelihood that a probe vehicle drove along to using the two probabilities defined before. This means that we are taking into consideration the geometric and topological aspect of the network in our computation. However, in reality it is not sure that the probe vehicle will take the shortest path that's why we keep in order to reflect that aspect. Each candidate generated will check and have a value of spatial function and the one with the highest scope is the closed map matching of sparsely sampled GPS data to reality. Temporal Analysis: The temporal analysis measures the average speed travel between two neighborhoods position. Then it will compare the average speed with the speed limit on each candidate paths. This information will be used to match the trajectory to the candidate's paths with the closest similar speed limit during that time interval. Thus for a given two candidate points and for two successive GPS positions and . The shortest path from to is a set of PUMAS section . We will note average speed V m,(i,z)!(i+1,e) of the shortest path as follows (equation 3.8):

V m,(i,z)!(i+1,e) = l m m=1 k " #t i!i+1 (3.8)
Where,

• is the length of concerned PUMAS section of .

• Is the time interval between two sparsely sampled data and .

Moreover, each PUMAS section is associated with . In order to measure the similarity between the average speed from to and the section speed limit; we will use the cosine distance. By considering the vector with k elements

{ } l m = s m ' .l s m ' !t i"i+1 = c i+1 .t # c i .t c i c i+1 s m ' s m ' .v p i z p i+1 e
of the same speed V m,(i,z)!(i+1,e) and the vector the temporal analysis function will be as follows (equation 3.9):

T ( p i z ! p i+1 e ) = (s m .v *V m,(i,z)!(i+1,e) ) m=1 k " (s m .v) 2 m=1 k " * (V m,(i,z)!(i+1,e) ) 2 m=1
k "

(3.9)

Output

In this component we will describe the matching process based on the spatial and temporal analysis. In order to make a clear description we will illustrate the process in the following (figure 3.8). Thus, we were able to generate candidate graph for a trajectory . Where,

• is the set of candidates for each sparsely sampled GPS data.

• is the set of PUMAS sections representing the shortest path between any successive candidate positions. Which means that each G' is associated with . And each Section is associated with and . Therefore by combining the equations of spatial analysis function and the temporal analysis function we will have our final equation 3.10 as follows:

(3.10) To make a decision about all candidates we will consider a candidate path sequence for the entire trajectory T that is a path in the candidate graph. The total score for candidate path is

. Then the aim is to find the one with the highest score as the best matching path for the trajectory. Thus the selection expression will be (equation 3.11):

(3.11) After we find the path P that reflects the true path we run a check on the sparsely sampled GPS data orientation if it is logical with the PUMAS section .

s 1 ' .v, s 2 ' .v,..., s k ' .v ( ) T G T ' (V T ' , E T ' ) T : c 1 ! c 2 ! c 3 ! ... ! c n V T ' E T ' !( p i j ) !( p i z " p i+1 e ) T ( p i z ! p i+1 e )
ST ( p i z ! p i+1 e ) = S( p i z ! p i+1 e )*T ( p i z ! p i+1 e ), "1 # i # n . The function attributes a score of one if it fits otherwise a zero. The orientation function check is defined as follows (equation 3.12):

P p : p 1 z 1 ! p 2 z 2 ! p 3 z 3 ! .... ! p n z n P p F * (P p ) = ST ( p i z i ! p i+1 z i+1 ) i=1 n " P = arg max P p F * (P p ), !P p " G T ' (V T ' , E T ' ) c i .cape s i .cape
(3.12) Where, is an operator with condition rules defined as follows: Which means that the operator is equal to true when are from the same interval. However we don't run this check on a specific sparsely sampled GPS data if the speed on the probe at that position is lower than 4km/h. Because based on the empirical data the orientation is not precise or sometimes wrong when the speed is lower than 4km/h. In case the check was activated and finds a false case where the orientation is not following the same orientation of the PUMAS section. We will call the correction process to correct the sparsely sampled GPS data concerned.

CF c (c i .cape, s i .cape) = 1 if c ! ! s ! = true 0 if c ! ! s ! = false " # $ % $
regarding this issue of prediction. In our case we will be inspired by [START_REF] Balasundaram | Location Prediction Mechanisms for Tracking Lost Unmanned Vehicles[END_REF] where the author used a method to complete the gap of lost data and we will adopt it to our case.

In our case we have each sparsely sampled GPS data can be characterized by the position coordinated x--axis and y--axis. Thus we can write and . The future position or predicted position will be and will be predicted as follows (equation 3.13):

(3.13) Where, u represents the step length between each sparsely sampled data. is the estimated direction angle of the probe. After predicting the new position, the correction process is done and we run again the system with new correction added to the raw data as (figure 3.6) shows. Moreover, this process of correction is done only once for each set of trajectories T from the raw data. To sum up in this section 3.3 we showed how the raw data is processed in order to make it ready to be used for the travel time estimation. In the following section we will describe in details the path reconstruction that we used in the map matching process.

Path Reconstruction on Database Context

Path reconstruction can be seen as the shortest path problem between two vertices in weighted graphs is very well known as a graph problem. There are many solutions that have been developed for different types of graphs such as Dijkstra in the case of positive weights, Bellman in the general case, etc. However, these methods are time consuming regarding the computational process, which means that they need enhancement and speed up. In this section we will discuss these techniques and how we dealt with it in this thesis work.

Introduction

c k (x k , y k ) c k!1 (x k!1 , y k!1 ) c k+1 ' (x k+1 , y k+1 ) x k+1 = x k + u * cos! y k+1 = y k + u * cos! and, ! = arctan y k ! y k!1 x k ! x k!1 " # $ % & ' and, u = (x k ! x k!1 ) 2 + (y k ! y k!1 ) 2 ( ) * * * * + * * * * !
The choice of a way to move goods can be done by taking into account the travel time, cost, parking, etc. In general, the tools used to guide this choice are based on solving technical "problem of shorter path". Given a graph for given starting candidates position to the final destination candidate position the issue is to find the optimal shortest path regarding the constraints to travel from to . The shortest path problem is one of optimization problems over the network studied since the fifties (Bellman, 1958 [74]). All these studies are based on finding a path in a graph based on a single objective. Indeed, the shortest path problem for a traditional objective of minimizing the time, cost, or both. One aspect of shortest path problem that interests us in this dissertation is the time--dependent shortest path. This issue has been studied for the case of determining the shortest path. In other words we looking for the shortest path between two nodes or positions and it is called in the literature the point--to-point shortest path problem with time dependency. Concerning the point--to--point algorithm the most famous one is the Dijkstra 1959. The process starts by the initial position and it scans all the neighbors around it. All the paths found will be ranked based in the minimal sum of cost of the visited edges or roads in our case. In each subsequence step, the algorithm will apply a relaxation to the minimal cost, which means it has the highest rank then visits again all its neighbors and ranks them again. The process will stop when the end node or position is reached. The number of nodes visited during the search usually helps to evaluate the routing algorithm performance. For example, Dijkstra makes a scan of the neighbors in a circular area aspect enclosing the start position and the ending position. This explains why the algorithm needs a lot of computation time when the road network is dense. For this reason, many methods have been embedded to the algorithm to make it faster. To sum up these enhancement methods we will put them into categories as it was cited in [START_REF] Holzer | Combining Speed--Up Techniques for Shortest--Path Computations[END_REF] as follows: Shortest--path with Bi--directed search: In this approach as it was illustrated in [START_REF] Pohl | Bi--directional and heuristic search in path problems[END_REF], [START_REF] Kaindl | Bidirectional heuristic search reconsidered[END_REF] the search starts from both positions start and end, at the same time. Thus, the scanning time will be reduced because there is two processes running at the same time and the visit for a specific node will happen only once. By using this approach the running time improves.

G T ' (V T ' , E T ' ) p i z ! V T ' p i+1 e ! V T ' p i z p i+1 e
Shortest--path with Goal--directed search: This approach affects the nodes ranks that are unlikely to be on the shortest path [START_REF] Schulz | Dijkstra's algorithm on--line: An empirical case study from public railroad transport[END_REF]. Moreover, it applies the same principal to the road section regarding the shortest path. Shortest--path with Multi--level approach: This method in [START_REF] Holzer | Hierarchical speed--up techniques for shortest--path algorithms[END_REF] adds shortcuts indexes to the road network when it is possible in order to bypass many edges at a time during the routing process. The sub--class follows a hierarchical routing. First layer contains the full resolution of the network and the next layer contains less nodes and road sections. This aspect makes the searchlight but we lose in the accuracy. Shortest--path with Bounding boxes: Checks if there is any possibility that the concerned node can be in the shortest path if not it is rejected and not considered [START_REF] Wagner | Geometric speed--up techniques for finding shortest paths in large sparse graphs[END_REF].

There are many researches done in the shortest path problem but we have to be more specific regarding our case to narrow our focus on the real issue in this dissertation. The fact that the data used is sparsely sampled GPS data and we have to find the path between each pairs of successive data put as in the situation of point--to--point shortest path. Moreover, we have to take into consideration that between each two GPS position there is a time gap, which means that our approach to solve this issue is time dependent. To sum up we are dealing with point--to--point shortest paths on time dependent road networks.

Related work and Analysis

The shortest path problem is one of the subjects that have been conducted for many decades. Besides, many innovative ideas have been proposed to compute the point--to--point shortest path. Starting from the 1950th a lot of work related to our subject was developed but the purpose behind was different. The studies done in solving the shortest path were more for transportation planning or road network analysis not for individual travel time.

The first work in this period related to time dependent shortest path with a recursive formula that gave the needed shortest path with the minimum travel time between a starting point and ending position was citied in [START_REF] Cooke | The Shortest route through a network with time dependence intermodal transit times[END_REF]. In this article by taking the positive travel time value the method gives the shortest path from all nodes to a given final destination. In Dijkstra's algorithm [START_REF] Dijkstra | A note on two problems in connection with graphs[END_REF] the shortest path problem in a static directed graph is solved by using non--negative weights in a polynomial time. The algorithm can easily be extended to dynamic case with time dependence [START_REF] Dreyfus | An appraisal of some shortest--path algorithms[END_REF]. However, the FIFO in the tree structure is not mentioned which is really important to get the right path in time dependence case.

There were many similar algorithms developed to solve this issue such as by Whiting & Hillier. But the most used and enhanced algorithm is Dijkstra and there are many derived algorithm from it. One of the famous one is the A* algorithm which adds the concept of closeness [START_REF] Ji | The Vehicle routing problem with time--varying travel tiles and a solution method[END_REF] to push the search to the target node [START_REF] Osvald | Shortest--path and minimum--delay algorithms in networks with time--dependent edge--length[END_REF]. Besides, based on the nodes visited the Dijkstra visits almost all of them however in terms of norm he is actually the smaller. One of the aspect that shortest path have it is this time dependence issue which is interesting for our dissertation. The time--dependent shortest path problem has many applications in transportation. One of the articles that attracted us is [START_REF] Chabini | Discrete dynamics shortest path problems in transportation applications: Complexity and algorithms with optimal run time[END_REF] where the other adopted an algorithm where he compute all--to--one shortest path in a discrete dynamic network. Moreover, the author emphasizes that his method is the most appropriate to the dynamic transportation systems like the intelligent transportation systems. He put also in his approach specific characteristics that the shortest path problem depends on. We summarized them as follows in the table below.

Source and destination

• One--to--all: finding the path from the source to all possible destinations. • All--to one: finding the path from all possible sources to one destination. • One--to--one: finding the path from one source to one destination Objective

• Fastest path: minimum cost path with cost = delay • Bi--criteria: cost and time • Multi--criteria path: the use more than one criteria.

Another aspect of shortest path problem is in the database context, which is similar to our work in this dissertation. The fact it is on a database it involves the development of intelligent transportation systems (ITS). Our thesis deals with this issue of time--dependence shortest path on a database context. Besides, there is much reason by storing this processed data that can help for ITS purposes. For example in [START_REF] Everett | Dense subgraph computation via stochastic search: application to detect transcriptional modules[END_REF] the author suggested storing data in order to perform shortest path process. In [START_REF] Zhan | Shortest Path algorithms: an evaluation using real road network[END_REF] the authors explicitly refer to this issue where they deal with moving objects and they use a classical shortest path approach based on distance.

Problem statement

In the domain of traffic the road network are dynamic and time dependent. In fact between two positions of sparsely sampled GPS positions c k and c k+1 , we can have many possible paths. Moreover, the time received at the first position and the second position can vary depending on the probe vehicle. In our work we will focus on finding the right path based on the travel time per road section and also the travel time between the two positions c k and c k+1 in order to reconstruct the path that was used by our probe vehicle. The problem in our case is to find the optimal path that respects the travel time between c k and c k+1 . By stating our problematic, it will be easy to find the appropriate algorithm, adapt it, and enhance it to our case. As a start we will define clearly the model: Definition 11: G(V,E) is an oriented graph which means that each edge (i, j) has a defined orientation regarding its connections with other edges. This aspect makes the graph dynamic. Moreover, each position c k has a time of reception associated to it c k .t .

Definition 12: let ! : E " R be a cost function that assigns a cost ! ij to each (i, j) ! E . Given a root r p ! V the shortest path problem (SPP) consists in finding the directed trajectory T such as the path r p from i to j exist and it is the shortest path with respect to the weight function.

Definition 13: (First in First out property) for each pair of time t and t' with t>t':

!(i, j) " E, #(i, j, t)+ t $ #(i, j, t ')+ t ' . This means in our case, that when the probe vehicle left from a node at time t he cannot arrive a final destination node before t'. That's why this condition is really important in our case to rebuild the path of our sparsely sampled GPS data in our historical database especially in the case of a death node (the reached node does not lead to the final destination).

First, before modeling the time--dependent shortest problem (TDSPP), which is the interest in our case, let's start by formulating the shortest path problem. The classical formulation of shortest path problem is as follows: Let M ! "1, 0,1

{ }

V * E be the incidence matrix of the graph G(V,E) and its elements are m ij v and (equation 3.14):

m ij v = 1 if v = i 0 otherwise !1 if v = j " # $ $ % $ $ (3.14)
Moreover we will consider a network flow problem [START_REF] Ahuja | Network flows:theory, algorithms, and application[END_REF] illustrated by f v such as (equation 3.15):

f v = 1 for v = i !1 for v = j 0 "v # V \ i, j { } (TDSPP) min t v !(i, j) " E x ij (t i + #(i, j, t i )) $ t j !v " V m ij v x ij = f v (i, j )"E % !(i, j) " E x ij " 0,1 { } !v " V t i & 0 ' ( ) ) ) ) ) * ) ) ) ) ) (3.17)
Where !(i, j, t i ) represents the cost of the arc (i,j) at time t i . The representation above of the TDSPP contains the flow conservation constraint of the road network and also the arrival time t j at the destination node j starting from departure node i at time t i . Since, in our case we are trying to find the shortest path to reach node j with respect to the travel time between node i and j that we know from our sparsely sampled data; the arrival time constraint is satisfied.

Which means t i + !(i, j, t i ) = t j .
However this is a general representation of our case with a cost function and its constrain regarding the data used. Besides, we will state clearly how to define our cost function and the process in the following sections of this dissertation.

But the problem can be summarized to a Time--dependent Shortest Path Problem for a Given Departure and Arrival Time (TDSPP--GDAT).

Strategy adopted To Solve TDSPP--GDAT

In this section we will start by reminding the case problem and define some concepts and definitions that play an important role in the solving process. First, in our case we have sparsely sampled GPS data that constitute our historical database. This data has gap of information between each successive data. The problem is to find out the real path that has been taken by the probe vehicle between two known positions [START_REF] Hadachi | An Application of the Sequential Monte Carlo to Increase the Accuracy of Travel Time Estimation in Urban Areas[END_REF].

Let's now define some function that we will use in showing how we solved this graph problem.

!(k, k +1, c k"k+1 .T ) = f (e i .t) h(c k"k+1 .T ) k#i#k+1 $ . (3.19)
Definition 17: (Total path weight) the total weight path is the weight that we attribute to a specific path starting from source position to the final destination (equation 3.20).

W

(P i ) = c k .t { + !(k, k +1, c k"k+1 .T ) (3.20)
These formulations constitute the core of the process of making a decision regarding the time dependency and constraints in our case. The system process was done at the database level in order to run the process of learning routing process. This means that we will find the entire time dependent shortest path possible between all the nodes. The process will be done only once on offline status. Then on online status we will call the module, he will give the solution that he has already in his archives saved on the database. In order to solve the time-- depended shortest problem in our case TDSPP--GDAT we decided to combine two approaches the classical algorithm of Dijkstra [START_REF] Dijkstra | A note on two problems in connection with graphs[END_REF] and the time--dependent shortest path problem with least travel time in a given interval presented by Ding [START_REF] Ding | Finding time--dependent shortest path in a large graphs[END_REF]. However, this latter approach has been chosen because it can be easily generalized and modified for our case TDSPP--GDAT, by simplifying the arrival time function to our special case. This means that the path is determined after the travel time per road section function is processed. In other words we defined the time dimension on each node of the graph. Then we have to apply the travel time constraint function in order to have the weight on the edges for all the paths. Based on this decoupling we are close to what is called in literature Two--step--least travel time [START_REF] Ding | Finding time--dependent shortest path in a large graphs[END_REF]. Definition 18: (Two--step--least travel time) the algorithm determines the least arrival time to a specific node by performing a Dijkstra. The main advantage of this algorithm of decoupling the time refinement and path selection is the ability to figure out the right arrival time when we already know the arrival time.

Based on this definition, the situation is applicable to our case we will add some modification to the strategy in order to make useable to solve our case. Because in Tow--step least travel time they try to estimate the right arrival time function; however, in our case we already know the arrival time. The issue then is to find the path with arrival time function that is close to reality. For this reason we adopt an approach where we will gradually explain the process in the database context step by step. We distinguish two kinds of steps; the first one is an offline step where we make a learning process of our digital map or graph and the second one is online step where we find the appropriate path for our case. Before starting the algorithm we generate our graph by having all the vertices set and all edges sets and also attribute the time distance to them by using the travel time constraint function. First step (offline)--Dijkstra based on travel time. At this level the purpose to scan the whole graph that is already built with all the edges and vertices enhanced with travel time per road section function information. This means that the Dijkstra is involved in his search aspect. The algorithm starts by initialization process where he gets from the list of vertices the start point v k and the arrival point v k+1 . Then he will search for all possible connections that can lead him to reach the arrival point and computing at the same time the total travel time per road section function as it was defined in definition 15 for each path found. The final results will be a graph that contains information about all paths possible from a starting vertex to an arrival vertex knowing the travel time needed to do so. In order to make it clear we break it down into phases as follows:

• Phase1: all the vertices in the graph are assigned to a travel time distance equal to infinity except the initial vertex, which is equal to zero. • Phase2: set the initial node to status of current and all the other vertices to unvisited. Create a set of unvisited vertices excluding the initial vertex. • Phase3: take into consideration all unvisited neighbors of the current vertex and compute their travel time distance. • Phase4: after considering all the potential neighbors we mark the current vertex as visited thus it will be removed from unvisited vertices set. This means that the visited vertex will be never visited again and its time distance to all neighbors is recorded. • Phase5: the next current vertex is marked with the lowest time distance in the unvisited vertices set. • Phase6: in case the unvisited set is empty then we stop. Otherwise, the vertex in the unvisited set vertices with the lowest time distance is set to current and we go back to phase3.

This offline process will provide us a database with all possible tree paths from a start point to an arrival point including the Travel time constraint function or time distance information for each connection. Now during the online step the information collected from the offline step will be used to compute the Cost function and find the logical path for each pairs of the sparsely sampled GPS data in the historical database.

Second step (online)--shortest pathfinder. In this step we will have as input the two position from our sparsely sampled GPS data, starting position c k and the arrival position c k+1 with their time respectively c k .t and c k+1 .t . Moreover, we will have also the information concerning to which edge they are assigned to.

This latter information will help us find the concerned vertices v i and v i+k . By consulting our database of possible paths done in first step we will have the set of all possible paths. Therefore, it is easy to compute the weight of each path using the cost function defined in definition 16 and as a consequence we will have also the total weight for each path by conducting definition 17. Now we will have the set of total weight per path W (P i ) .

The next step is to get the real weight because we did not take into the consideration the time distance between the GPS positions and the concerned vertices. Where, L(c k ) = dist(v k , c k ) is the Euclidian distance between GPS position and the concerned vertex on the graph. Therefore the weight for a specific path will be as follows(equation 3.22):

Total _Weight(P k ) = T DS (c k ) + !(k, k +1, c k"k+1 .T ) + T DS (c k+1 ) (3.22)
Finally, the optimal path solving our TDSPP--GDAT will be the one with the highest total weight. Thus the method proposed eliminates the data outliers when compared to an estimated route

Conclusion

In this chapter we went through what we call in our dissertation the preprocessing tools. This latter makes reference to all processes needed to make the raw data in an urban context ready to be treated. The first process was to extract the digital map from the "openstreetmap" and also add new characteristics to it for enhancement purposes. Then we processed a raw data check in order to clean our Historical database from any ambiguity information. The second main tool in this chapter was the map matching process that we used to match our raw data to the digital map. Our map matching was explained and also the entire enhancement added to it in order to reduce all the error factors and get a good representation of the data reflecting almost the reality. The third part was related to the time--dependent shortest path problem given a departure and arrival time. This is used by the map matching process at a certain level of the process. In this part we explained our new approach in a database context. We have adopted a new step called a learning phase that we processed on offline status and then we described how the algorithm reacts when the map matching on online status calls it. Finally, after making all our raw data ready and filtered we will discuss in the following chapter the core of our dissertation which is the travel time estimation in a historical database context.

Chapter 4: Travel Time Estimation using Sparsely Sampled Data in an urban network 4.1 Introduction

Estimating travel time in an urban road network using sparsely sampled data from probes has proven to be a substantial challenge. The sparsely sampled GPS data represents the vast majority of the data available in urban road networks environment. Nowadays the feature of probe vehicle data includes the variety of data type, the lack of ubiquity and reliability, and the random aspect of its spatio--temporal coverage. All these features make it insufficient to make a clear idea about the macroscopic traffic model parameters with clear statement about the state estimation for the large transportation network. Moreover, the penetration rate of this kind of data is still typically low which mean the information regarding the urban network can not be homogeneous thus it is not representing the full traffic state of the system [START_REF] Van Aerde | Vehicle probes as realtime ATMS sources of dynamic O--D and travel time data[END_REF]. However, this data can be processed and enriched to make it usable for the macroscopic level. In order to so we can for example enrich it with travel time estimation per road section. Regarding the literature on travel time estimation using this kind of data presents two challenges the first is finding the path that was taken by the probe, which tried to solve in chapter 3 of this dissertation. The second one is to find the travel time spent in each road section and there are many methods that have been developed for this purpose such as: In [START_REF] Van Aerde | Vehicle probes as realtime ATMS sources of dynamic O--D and travel time data[END_REF] where the author used a probabilistic approach to model the travel time in an arterial network using low frequency taxi GPS information. The model developed assumes the following hypothesis: between two successive data there is at least a road section and it does not take into account the case when the two GPS data are located in the same road section. The problem with this approach, it needs to observe the route travel time on the road section, which is not the case with sparsely sampled data. That's why he used a simulation based on the maximum likelihood. This solution is good after all but it is not reflecting the reality and it complexity.

Another approach was presented in [START_REF] Jenelius | Travel Time Estimation for Urban Road Networks Using Low--Frequency GPS Probes[END_REF], where the author used a statistical approach to increase the reliability and the estimation of travel time by using all the observed data from the probes. The model learns from the data and predicts the travel time for any trajectory in the network. Whereas, there is another context of estimating travel time, which concerns us in our dissertation, is estimating travel time in a historical database. Some of the work done in this area was based on the analysis of traffic information from the real world data. By applying many techniques such as fuzzy logic, artificial intelligence, mathematical models or statistical models. For example in [START_REF] Li | Link Travel Time Estimation Using Single GPS Equipped Probe Vehicle[END_REF] the authors established a mathematical model to estimate travel time using GPS data from probe vehicles. The historical travel time data was used to adjust his statistical travel time estimation model based on historical travel time data. The result of this approach was good in a fluid traffic but the model was unable to perform good results when there is congestion in the network. A probabilistic model to estimate travel time in arterial network using sparsely sampled GPS data is presented in [START_REF] Hunter | Path and travel time inference from GPS probe vehicle data[END_REF]. The author used an Expectation--Maximization algorithm to estimate the probability distribution of travel time through the road section. As the roads sections travel time are not directly observed, a simulation based on EM algorithm is proposed. The author assumes in his analysis that the travel time per road sections are independent, which not the case in reality. In some article like in [150] and [START_REF] Herring | Using mobile phones to forecast arterial traffic through statistical learning[END_REF], they took into consideration the dependency of travel time per road sections using Spatio--temporal auto regression moving average approach. These models, however, were applied to stationary sensor data and not probe vehicle data. Thus, they used the traffic flow information in order to estimate travel time. Another approach, using sparsely sampled GPS data from ambulance, is presented in [START_REF] Westgate | Travel time estimation for ambulances using Bayesian data augmentation[END_REF]. The author used a Bayesian approach to estimate travel time. The travel time was assumed to be independent and follow a log--normal distribution. Besides, the parameters are estimated using a Markov chain. However, the approach presented does not take into consideration the variance of travel time and speed. All the methods presented do not take into account very important fact such as the dependency and the variance of travel time per road sections. That's why we choose to use particle filter in our approach because it gives us this ability to take into consideration all those features of travel time in reality (dependency, variance).

Our approach in this thesis work will be by presenting a new method to estimate travel time per road section at a microscopic level using Monte Carlo Method and historical probability distributions of travel time on each road section. The estimation will be done in the Historical database in order to enrich it with travel time information using sparsely sampled GPS data.

Problem Statement

In this section we will try to formalize the problem of travel time estimation in our case. We will start by illustrating the situation that we have to solve. First, we will state some definitions in order to make it easy to understand the problem. Definition 19: (PUMAS Points) is the virtual node on the digital map where the road section intersects (green squares on Figure 4.1). This means that any road section or PUMAS section is defined by a starting PUMAS point and an ending PUMAS point . Definition 20: (Moment of Passage,

) is the time when the probe vehicle passes through the PUMAS points. Thus each PUMAS point will have the information related to its position on the map and also the estimated time when the probe vehicle went through it . Definition 21: (Travel time per section) is the total time needed to cross the whole road section. In other words it is the time needed to go through the starting PUMAS point of the road section till reaching the ending PUMAS point of the same road section. The issue is to estimate the travel time between two successive sparsely sampled GPS data. The process start by detecting all the road sections which means find out all the PUMAS points between the two successive sparsely GPS data. Moreover this process can be done successfully when we apply all the processes described in chapter 3. After determining the PUMAS points the remaining step is to estimate the moment of passage through those virtual position (PUMAS points) then it is easy to find out the travel time estimation per road sections. Our approach to solve the problem will be based on the family of sequential Monte Carlo Methods (MCM). These methods are interesting for us due to their

n pp i n pp j Mp i j Mp i j Vi 1 Vi 2 d 1 d 2 l 1
aspect. They are a comprehensive approach based on an exploration of the space state of the problem using particles with a randomly changing dynamics. All these particles are distributed according to the probability of the process to estimate conditional observations issued by the sensors. Moreover, it does not require explicit resolution of the problem equations; this method is applicable regardless of the complexity of these equations, especially in terms of non--linearity and non--Gaussian.

Particle Filter Model

The particle filter (PF) proposed originally by Gordon et al [START_REF] Gordon | Novel approach to nonlinear/non Gaussian Bayesian state estimation[END_REF], this kind of algorithm which uses particle filtering has gradually emerged as the best technique for processing nonlinear signals. The concept of resampling introduced by Gordon has allowed many issues related to estimations and predictions to be solved, and also opened new windows to be explored and developed. The particle filtering algorithms can estimate probability through successive measurement by using a finite set of Dirac measurements centered in the corresponding points of "particles". This approach has a lot of success in the scientific community and its application has covered all kind of fields. It was used in the 1950s to simulate polymer chains of great length [START_REF] Rosenbluth | Monte Carlo calculation of the average extention of molecular chains[END_REF] and also to solve problems of physics during World War II [START_REF] Hammersley | Poor man's monte carlo[END_REF]. Since the 1990s, these simulation methods have become widespread in various fields such as radar signal processing [START_REF] Gordon | Novel approach to nonlinear/non Gaussian Bayesian state estimation[END_REF], genetics [START_REF] Irwing | Sequential imputation for multilocus linkage analysis[END_REF], robotics [START_REF] Fox | Markov localization for mobile robots in dynamic environment[END_REF], and the classical Bayesian estimation [START_REF] Kong | Sequetial imputation method and Bayesian missing data problems[END_REF], and also it has been applied to localization, navigation, tracking [START_REF] Gustafsson | Partilce Filters for Positioning, Navigation, and Tracking[END_REF] or multiple target tracking [START_REF] Hue | Sequential Monte Carlo methods for multiple target tracking and data fusion[END_REF], vision [START_REF] Isard | CONDENSATION --Conditional Density Propagation for Visual Tracking[END_REF], and communication [START_REF] Wang | Monte Carlo Bayesian signal processing for wireless communications[END_REF]. In many applications the goal is to estimate the posterior probability density for the states by using some observations. Thus we have to define the states equation parameters that we will denote by the vector while the vector denotes all the observations up to time t. Let's consider the following model representing the state equation and the observation equation 4.1:

(4.1) Where and are the process and measurement noises respectively. Besides, f and h are two arbitrary nonlinear functions. Moreover they are assumed to follow an independent distribution with known densities.

And the system state process can be defined as follows (equation 4.2):

X t = x 0 , x 1 , x 2 ,..., x t { } Y t = y 0 , y 1 , y 2 ,..., y t { } x t+1 = f (x t ) + u t y t = h(x t ) + b t ! " # u t ~pu t (.) b t ~pb t (.) 90 (4.2)
The prior distribution of the state at initial state t=to is given by . The particle filters are usually used when the posterior density and the observation density are non--Gaussian. The observations are conditionally independent given the states (equation 4.

We should forget that the purpose of the method is to estimate the posterior density . Since the case is neither linear nor Gaussian the posterior representation should be the total probability density function. Thus the estimation will be as follows (equation 4.4):

(4.4) The expression became as it is shown above due the definition of the system's state process (equation 4.2). The key idea behind the PF is to approximate the probability distribution by applying a weighted sample set. Let's are the samples set drawn from the posterior. Then the estimation expression will be:

(4.5)
Where is the Dirac delta function. The sampled in this situation are equally correct because they are drawn from the posterior itself. As a consequence, their weight sum will be equal to one. The value 1/N added is in order to respect the law of total probability. This estimation can be used for example to have an idea about different moments of the posterior by computing the expectation and the covariance. The samples that we have cannot be drawn from the posterior simply because it is unknown. To mitigate this problem, it is possible to choose an alternative known probability distribution density instead of using p(X t \ Y t ) . Therefore, they are drawn using which is depending on Y t (equation

4.6). p(X t ) = p(x 0 ) p(x k \ x k!1 ) k=1 t " p(x 0 ) p X t \ Y t ( ) p Y t \ X t ( ) p(Y t \ X t ) = p(y k \ x k ) k=0 t ! p x t \ Y t ( ) p(X t \ Y t ) = p(y t \ X t ,Y t!1 )p(x t \ X t!1 ,Y t!1 ) p(y t \ Y t!1 ) p(X t!1 \ Y t!1 ) = p(y t \ x t )p(x t \ x t!1 ) p(y t \ Y t!1 ) p(X t!1 \ Y t!1 ) X t (i) { } i=1 N P ^( X t \ Y t ) = 1 N !(X t ! X t (i) ) i=1 N " !(X t ) q(X t \ Y t ) q(X t \ Y t ) 91 (4.6)
The last equality (equation 4.6) that is shown is due to the restriction that the states at time t--1 and older are independent of the measurement at time t. This implies that we have the power to draw from and form the set without adjusting.

To make the estimation of the posterior by exploiting these samples we should associate them with what is called the importance weight (equation 4.7).

(4.7) The only relationship that is important for us is the weights regarding the particles thus we can neglect . Thus the expression of equation 4.7 will be:

(4.8) We can make it simpler by using the state of propagation density (equation 4.9), (4.9) Therefore, the weight equation 4.8 will finally as follows:

(4.10) As a consequence, the estimation of the posterior equation 4.5 will be at the end as follow:

(4.11)
During the PF algorithm process, time evolves; as a consequence, it pushes the samples tend to spread and the weights for almost all the samples tends to zero. This means they are not helping to converge to the estimation. However, there is a solution to this issue. We should just check the covariance of the samples and

q(X t \ Y t ) = q(x t \ X t!1 ,Y t )q(X t!1 \ Y t ) = q(x t \ X t!1 ,Y t )q(X t!1 \ Y t!1 ) x t (i) { } i=1 N q(x t \ X t!1 ,Y t ) X t (i) = X t!1 (i) , x t (i) { } { } i=1 N X t!1 (i) { } i=1 N w t w t (i) = p(X t (i) \ Y t ) q(X t (i) \ Y t ) = ( p(Y t!1 ) p(Y t ) ) p(y t \ x t (i) )p(x t (i) \ x t!1 (i) ) q(x t (i) \ X t!1 (i) ,Y t ) w t!1 (i) p(Y t!1 ) p(Y t ) w t (i) = p(y t \ x t (i) )p(x t (i) \ x t!1 (i) ) q(x t (i) \ X t!1 (i) ,Y t ) w t!1 (i) q(x t \ X t!1 ,Y t ) = p(x t \ x t!1 ) w t (i) = p(y t \ x t (i) )w t!1 (i) P ^( X t \ Y t ) = w _ t (i) !(X t ! X t (i) ) i=1 N " w _ t (i) = w t (i) w t ( j ) j=1 N "
the covariance obtained from the weighted sampled. Besides, by comparing the two covariance, we will get the efficiency measurement of our sampling. It is shown in many application of the filter like in [START_REF] Liu | Sequential Monte Carlo Methods for Dynamics Systems[END_REF] that we can estimate the efficiency by using the following expression (equation 4.12):

(4.12)

And in order to know if the samples have spread far enough the use of threshold can give this information normally it is defined as follows: .

To sum up, the particle filter algorithm can be illustrated as follows:

1. Initialization at t=to Generate samples for Calculate for and Normalize 2) of some generalities about the particle filter based on the Monte Carlo methods. This approach allows us to construct recursively a cloud of particle weighted approaching the filter law. However, the recursive nature of the filter leads to a degeneration of the cloud induced by an augmentation through time of the unconditional variance of its weights. In order to control this degeneration of the particle clouds the resampling process allows to limit this aspect by giving more importance to the significant weights. Our objective in this dissertation is not to make the basic algorithm of particle filter better, but to find out the best adaptive one for our case of study in this thesis work. More details about the changes done will be shown in the next sections of this chapter. After this discussion we will describe some of the known distribution used in the field.

N eff = 1 (w _ t (i) ) 2 i ! N th = 2N 3 x 0 ~p(x 0 ) i = 1,........, N w 0 (i) = p(y 0 \ x 0 (i) ) i = 1,........, N w _ 0 (i) = w 0 (i) w 0 ( j ) j=1 N ! w t (i) = p(y t \ x t (i) )w t!1 (i) i = 1,........, N w _ t (i) = w t (i) w t ( j ) j=1 N ! x t (i) { } i=1 N w t (i) = 1 N N eff = 1 (w _ t (i) ) 2 i ! < N th w t (i) = 1 N
P ^( X t \ Y t ) = w _ t (i) !(X t ! X t (i) ) i=1 N " w _ t (i) = w t (i) w t ( j ) j=1 N " Probabilities Time a.
Normal distribution The most used probability distribution to describe a physical situation is the normal distribution. The reason behind this statement is that most of the outputs from many processes are normally distributed. All normal distributions have the same general shape. However, they can differ in their mean value and their variation, regarding the situation studied. The normal distribution can be described mathematically as follows (equation 4.13):

(4.13)
Where,

• x is any value of the random variable,

• is the population standard deviation, • is the population mean. And by influencing the mean and the standard deviation we can have different representation of the probability distribution, however, the total area (probability) under each normal curve equals 1. b.

Lognormal distribution The log--normal distribution is a skewed distribution, which starts zero, rises to a maximum before falling more slowly to infinity (figure 4.3). It is connected to normal distribution: X is a log--normal distribution if ln(X) is a normal distribution. The normal distribution can be described mathematically as follows (equation 4.14 and 4.15): (4.14) And the parameters required to specify the function are: the average natural log transformation of the input data, and the variance of the natural--log transformation of the input data. They are defined as follows:

f (x) = 1 ! 2" e !( x!µ ) 2 2! 2 ! µ f (x) = 1 x! l 2" e !(ln x!µ l ) 2 2! l 2 µ l ! l 95 (4.15) Where,
• x is any value of the random variable,

• is the population standard deviation,

•
is the population mean. [START_REF] Hunter | Path and Travel Time Inference from GPS Probe Vehicle Data[END_REF] the author used this distribution to estimate the path/location and travel time using sparsely sampled GPS data.

Travel time parameters Distributions

In the previous section we skimmed through the particle sampling process where we choose a distribution for our particles. Which is an important process in the Monte Carlo approaches because it will affect the output of the particle filter. Regarding our work in this dissertation to estimate the travel time per road section is touching three aspects location or distance, time, and speed. Based on this three aspect we will discuss and try to define their distributions.

Speed distribution on a road section

µ l = ln µ 2 (! 2 + µ 2 ) ! l = ln( ! 2 µ 2 +1) ! µ
Making a good estimation of travel time need a good understanding of traffic dynamics. Especially in our case in this dissertation we will use an adaptive particle filter where vehicle's speed is one of the parameters that we will affect with particles approach. Thus defining the closed probability density distribution of speed is needed in order to give a good estimation of travel time. Our interest in this section is to define the speed distribution model per road section in an urban context.

We have to take into consideration that the driver selects the speed. Each driver has his/her own way of driving. Some of them respect the speed limits others not. Besides, there are other factors involved that can push the driver to not respect the regulations such as vehicle's capacity and power, road condition, driver ability and so on.

The speed distribution can provide answer to the issue discussed above. Where the distribution will show all the arrangement of speed values showing their observed or theoretical frequency of occurrence. The research done in this subject has shown that the speed distribution is normally distributed; however, the properties or the characteristics of the probability distribution function (pdf) on each urban road section can vary depending on the driver behavior (Figure 4.4). deviations These kinds of speed can be clearly noticed when we try to find out the speed profile in the road network (more details in chapter 5). The speed profiles are a graphical representation of speed features plotted by location. Besides, the use of speed profiles can help to analyze and evaluate the speed attitudes. The purpose behind this enlightenment is to show: how hard to estimate the right speed distribution that reflects the reality. As the Figure 4.6 shows that the driving behavior can be really complicated because of the people's interaction when using their vehicles between themselves and the use of speed on the urban road. Moreover, based on the figure 4.6 we can notice that the speed displacement of the male's speed graph cover in uniform way a large interval. After this brief discussion about the speed distribution it is clear that it is not easy to come out with a perfect distribution reflecting the reality but we will try to approach this reality. In order to determine the shape of the speed distribution, a common method to use is the histogram. Although the histogram method is widely used for data interpretation in many areas, it should be commented that the histogram method has a potential limitations because this method strongly depends on data origin, bin interval, and bin width [START_REF] Martinez | Computational Statistics Handbook with MATLAB[END_REF]. This issue point to the fact that the histogram should be well constructed. Besides, the histogram is very good to use to get brief information about the speed distribution and there are some cases when we don't have this issue of discontinuity of data. In the case when the characteristics of speed data are homogeneous which is the case for expressway in the urban areas then the speed probability density distribution can be conventionally described as normal distribution. However, the speed in urban networks can follow a bimodal distribution or polymodal distribution in this case there is no specific distribution function available [START_REF] Dey | Speed distribution curves under mixed traffic conditions[END_REF]. However, it seems from figure 4.6 that the appropriate distribution of the speed is a bimodal distribution, will conduct an analysis in chapter 5 based on the observed speed data from historical data Thus the appropriate way to estimate density function of the bimodal or polymodal distributions is the mixture model. The mixture model tries to cluster data into specific groups so that the data in the group have more similarity between each other [START_REF] Zhu | Microscopic traffic flow quality of service from the drivers' point of view[END_REF]. We can represent the mixture model by using any kind of probability density distribution. In general the most used distribution is the Gaussian mixture model due to its simplicity of the estimation process; moreover, it is used for computational, mathematics, and optimization operations [START_REF] Hastie | The Elements of Statistical Learning: Data Mining, Inference, and Prediction[END_REF]. The Gaussian mixture model can be defined in general as follows [START_REF] Hastie | The Elements of Statistical Learning: Data Mining, Inference, and Prediction[END_REF]: p(x \ µ 1 ,..., µ P , s 1 ,..., s P ,! 1 ,...,! P ) = ! i N i=1 P ! (µ i , s i "1 ) (4.16) Where (

) is a mixing proportion and each Gaussian distribution

N (µ i , s i !1
) has its own mean and s i !1 is the inverse variance which refers to the precision. For example in the case of bimodal model (figure 4.7) the value of P will be equal to 2. Besides, the bimodal distribution has two mixture components ( ! 1 and ! 2 ); the condition on these proportions is the sum is equal to one ! i i=1 P ! = 1 [119], [121]. ) . As consequence, the speed Gaussian mixture model in this case will be as follows:

! i ! i ! 0 µ i
p v (v \ µ 1 , µ 2 , s 1 , s 2 ,! 1 ,! 2 ) = ! 1 N (µ 1 , s 1 !1 ) + ! 2 N (µ 2 , s 2 !1 ) (4.17)
By using ! i i=1 P ! = 1the equation 4.17 become:

p v (v \ µ 1 , µ 2 , s 1 , s 2 ,! ) = (1! ! )N (µ 1 , s 1 !1 ) + ! N (µ 2 , s 2 !1 ) (4.18)
Where ! = ! 2 Moreover we will put the hypothesis that the speed distribution parameters will be define by two speeds of low--speed and high--speed regime as follows:

1. The low--speed regime is when we have a heavy traffic which mean either we have traffic jam situation or stop and go situation due to light traffic or road intersection or maybe just a dense traffic situation. The value of this kind of speed will be defined based on the study done on each road section where we find the min speed used on the concerned road section. We will note it as v min . 100 2. The high--speed regime v max is when we have fluid traffic no traffic jam. In order to define the value of that speed we will use our data to define the 85 th percentile speed. The hypothesis will be checked during the test phase in chapter 5. Definition 22: (85th percentile speed) is the speed at or below which 85 percent of vehicle travel in a road section.

Locations distribution on a road section

The probability density function of a vehicle's displacement on a road sections is a linear combination of normal distribution based on [START_REF] Laneurit | Accurate Vehicle Positioning on a Numerical Map[END_REF]. This aspect is due to the uncertainty of the traffic on the road section or to the different behaviors of the drivers (figure 4.8). Based on this analysis, it is clear that most of the cases the vehicle locations x follows a normal distribution on a road section. Moreover, the vehicle locations distribution is related to the speed evolution during the period !t when the vehicle passes by the road section. Thus the locations distribution is a normal distribution p(x) (as defined in 4.3).

Travel Time distribution on a road section

For the travel time probability distribution we will use the fact that travel time is related to the speed on the road section. Which means that the probability distribution of travel time is proportional to the speed probability distribution on the road section (equation 4. [START_REF] Nanthawichit | Application of Probe Vehicle Data for Realtime Traffic State Estimation and Shortterm Travel Time Prediction on a Freeway[END_REF]. [START_REF] Nanthawichit | Application of Probe Vehicle Data for Realtime Traffic State Estimation and Shortterm Travel Time Prediction on a Freeway[END_REF]) by using the fact that the travel time distribution is proportional to the speed distribution (defined in 4.4.2, equation 4.18) we have the following results:

Locations pd f p x (t) ! p v (v) and v = x t Thus p x (t) ! p v ( x v ) (4.
p x (t) = (1! ! )N ( x v min , µ 1 , s 1 !1 ) + N ( x v max , µ 2 , s 2 !1 ) (4.20)
Where the N ( x v , µ 1 , s 1 !1 ) will be defined as follows (equation 4.21):

N( x v , µ 1 , s 1 !1 ) = 1 (s !1 ) 2 2! exp( !µ(v ! x µ ) 2v 2 (s !1 ) 2 ) (4.21)
and, v min and v max are respectively low and high--speed regime when the traffic status on the road section is congested or fluid.

Travel time estimation using adaptive Monte Carlo approach

In this section we will expose the process adopted in order to create our adaptive method to estimate travel time [START_REF] Hadachi | An Application of the Sequential Monte Carlo to Increase the Accuracy of Travel Time Estimation in Urban Areas[END_REF]. As a remainder, our historical data has special features. The data used is a sparsely sampled GPS data where an interval of one minute between each successive GPS data point [START_REF] Hadachi | Practical Testing Application of Travel Time Estimation Using Applied Monte Carlo Method and Adaptive Estimation from Probes[END_REF]. Therefore, the data has a frequency of one minute between each GPS point which is not the case for normal GPS data received from a normal GPS receiver where data is received each second (illustration figure 4.9).

V 1 V 2 d 1 d 2 V 1 V 2 d 1 d 2
The fact that our estimation is only related to the travel time we can assume that our estimation process can be associated with the state equation as follows:

(4.22) Where Sp and Sk refer respectively to GPS coordinate of the PUMAS point and the first GPS data received, Vk is the speed of the car at the moment of receiving the GPS coordinates, tp and tk are respectively the time when the car was at the PUMAS point position and when we receive the GPS data, and finally U is a white state noise following a normal distribution that we add to the equation in order to represent to the imprecision of our parameters. Then our objective is to estimate tp : (4. [START_REF] Bolbol | Inferring hybrid transportation modes from sparse GPS data using a moving window SVM classification[END_REF] In our case we will process the unknown parameters of the equation by applying a defined model are known. Thus, we will inject our data directly by applying the particle process for each unknown parameters in order to simulate the uncertainty of our data. As a start, we will apply particles based on a normal distribution (Gaussian distribution) for which the mean is the value of the parameter and the total area under the normal curve is equal to 1. In our case, we choose a probability density with a fixed standard deviation ! that will make the particles evolve during the resampling stage following the equation below:

P(Y t / X t ) = 1 ! 2" exp( !(Y p !Y X t /X t!1 * ) 2 2! 2 ) (4.24)
Where Y p and Y X t /X t!1 * are respectively the observed positions of the PUMAS points and the observed positions of the data on the map. Thus our global particles equation will be as follows:

S p = S k (i) + V k (i) * (t p (i) ! t k ) +U (i) (4.
S p = S k + V k * (t p ! t k ) +U t p = S p !U ! S k V k + t k t p (i) = S p !U (i) ! S k (i) V k (i) + t k
Now we apply this formula to the first GPS data received and we call the estimated time of passage tp forward (tpf). Then we do the same for the second GPS data received after one minute and we call estimated time of passage tp backward (tpb) (figure 4.10).

t pf (i) = S p !U (i) ! S k (i) V k (i) + t k t pb (i) = S p !U (i) ! S k+1 (i) V k+1 (i) + t k+1 W 1 (i) = t pf (i) ! t k t k+1 ! t k W 2 (i) = t k+1 ! t pb (i) t k+1 ! t k W 1 (i) W 2 (i) t p = 1 2 (W 1 (i) * t pf (i) + W 2 (i) * t pb (i) ) i=1 N !
The algorithm will help us to estimate at what time the vehicle passed by the PUMAS points tpi (algorithm 1, figure 4.11) and then we can compute the travel time per PUMAS sections Tpj where j and i refer to the sections and PUMAS points respectively.

T P j = t p i+1 ! t p i (4.32) After obtaining our estimation we add the estimated delay time on the PUMAS zone due to traffic light duration as mentioned in [START_REF] Zhang | A Real--time urban traffic detection algorithm based on spatio--temporal OD matrix in vehicular sensor network[END_REF] when we detect a crossroad or the presence of traffic light in the itinerary of the vehicle; we can compute it using the following equation:

(4.33)
Where L is length of the PUMAS section, V is the limit speed in the PUMAS section concerned, and Sout is the number of vehicles that leave the PUMAS section during a given period of time [t, t+ t [. The filter estimator was created in such a way as to be adapted to our special historical database and in the next section we will explain our experimental process and then we will show our results.

D = L V * S out ! At time to.
Initialization. Define an initial state.

Generate N particles for ( S k , S k+1 ,V k ,V k+1 ,U ) Following p( S k ),p( S k+1 ),p( V k ),p(V k+1 ), p(U ).

Put

W (i) = 1 N
Sampling Importance Resampling (SIR).

For j=1 to M do Update the particles ( S k (i) , S k+1

(i) ,V k (i) ,V k+1 (i) ,U (i) )
For i=1 to N do Compute t pf (i ) and t pb (i ) .

Compute the weight W 1 (i) and W 2 (i) .

Normalize the weights W 1

(i) = W 1 (i) W 1 (i) i=1 N ! and W 2 (i) = W 2 (i) W 2 (i) i=1 N ! .
End.

Compute N eff 1 = 1 (W 1 (i) ) 2 i=1 N ! and N eff 2 = 1 (W 2 (i) ) 2 i=1 N ! . If N eff 1 ! N th (threshold) then Resampling t pf (i) ,W 1 (i) { } i=1 N .
Update the weights W 1 (i) .

Else If N eff 2 ! N th (threshold) then

Resampling t pb (i) ,W 2 (i) { } i=1 N .
Update the weights W 2 (i) .

End If. End If

Compute the estimation:

t p = 1 2 (W 1 (i) * t pf (i) + W 2 (i) * t pb (i) ) i=1 N ! .
End.

Travel time estimation using Monte Carlo method enhanced with measurements and road sections characteristics

In this part we will show how we made an enhancement to the previous algorithm. Some of the steps are similar but with some changes in the process and the equations used.

We keep the same state equation 4.22 as it was stated before with the same notations and meaning: (4.22) then after applying the particle with the same characteritics as it was shown before. Which means the particles follow a normal distribution (Gaussian distribution) for which the mean is the value of the parameter and the total area under the normal curve is equal to 1. In our case, we choose a probability density with a fixed standard deviation ! as before equation 4.25

P(Y t / X t ) = 1 ! 2" exp( !(Y p !Y X t /X t!1 * ) 2 2! 2 )
(4.24) Therefore, the expression with particles (i) will be as before equation 4.27: (4.26) after this step we apply as before this formula to the first GPS data received and we call the estimated time of passage tp forward (tpf). Then we do the same for the second GPS data received after one minute and we call estimated time of passage tp backward (tpb).

(4.27) (4.28) however this time we will detect all the PUMAS points between the two GPS data. Let's note j the number of PUMAS points detected. Thus the formula (equations 4.27 and 4.28) will become as follows:

t p j f (i) = S p j !U (i) ! S k (i) V k (i) + t k t p j b (i) = S p j !U (i) ! S k+1 (i) V k+1 (i) + t k+1 for j = 1,
S p = S k + V k * (t p ! t k ) +U t p (i) = S p !U (i) ! S k (i) V k (i) + t k t pf (i) = S p !U (i) ! S k (i) V k (i) + t k t pb (i) = S p !U (i) ! S k+1 (i) V k+1 (i) + t k+1 W 1, j (i) = t p j f (i) ! t k t k+1 ! t k W 2, j (i) = t k+1 ! t p j b (i) t k+1 ! t k for j = 1, 2, 3,..., P { } (4.35)
the next step will be defining the new weight where the road sections characteristics based on measurements introduced in the weight of the particles equations.

Based on the study done before on this chapter, we know the probability distribution of travel time of each road section on our network (section 4.4.4).

Thus the expression will be as follows (equation 4.36):

! 1 (i) = W 1, j (i) P x (t p j f (i) ) j=1 P ! ! 2 (i) = W 2, j (i) P x (t p j b (i) ) j=1 P ! (4.36) Where, p x (t) = (1! ! )N ( x v min , µ 1 , s 1 !1 ) + ! N ( x v max
, µ 2 , s 2 !1 ) (4.37) Finally the estimation is computed as before using the formula 4.38:

t p j = 1 2 (! 1 (i) t p j f (i) +! 2 (i) t p j b (i) )
i=1 N ! for j = 1, 2,3,...., P { } (4.38) now we have the estimation of the moment of passage on each PUMAS point detected on the path and we can conclude with the travel time estimation per road section using the equation stated before (equation 4.32) and we add also the notion delay at intersections using equation 4.33.

At time to. Initialization. Define an initial state.

Generate N particles for ( S k , S k+1 ,V k ,V k+1 ,U ) Following p( S k ),p( S k+1 ),p( V k ),p( V k+1 ), p(U ).

Put W (i) =

1 N

Sampling Importance Resampling (SIR).

For l=1 to M do Update the particles ( S k (i) , S k+1

(i) ,V k (i) ,V k+1 (i) ,U (i) )
For j=1 to P do For i=1 to N do Compute t p j f (i) and t p j b (i) .

Compute the weight W 1, j (i) and W 2, j (i) .

Normalize the weights W 1, j

(i) = W 1, j (i) W 1, j (i) i=1 N ! and W 2, j (i) = W 2, j (i) W 2, j (i) i=1 N ! . End.
End.

Generate P x (t p j f (i) ) and P x (t p j b (i) ) .

Compute ! 1 (i) and ! 2 (i) .

Normalize the weights ! 1

(i) = ! 1 (i) ! 1 (i) i=1 N ! and ! 2 (i) = ! 2 (i) ! 2 (i) i=1 N ! . Compute N eff 1 = 1 (! 1 (i) ) 2 i=1 N ! and N eff 2 = 1 (! 2 (i) ) 2 i=1 N ! . If N eff 1 ! N th (threshold) then Resampling t p j f (i) ,! 1 (i) { } i=1 N .
Update the weights ! 1

(i) . Else If N eff 2 ! N th (threshold) then Resampling t p j b (i) ,! 2 (i) { } i=1 N .
Update the weights ! 2 (i) .

End If. End If

Compute the estimation:

t p = 1 2 (! 1 (i) * t p j f (i) +! 2 (i) * t p j b (i) ) i=1 N ! . End.

Conclusion

To sum up, first we stated our problem statement where we defined exactly the problematic that we are dealing with. Then we gave an overview of the study on the parameters characterizing the traffic and their distributions regarding a road section approach. The study of those parameters was used later on the enhancement of the method proposed to estimate the travel time per road section or road section. Next, we presented our approach to estimate the travel time using a Monte Carlo method. Moreover, the approach was adapted to our case of study. Finally, we showed how we made and enhancement to the proposed method using the measurements and characteristics of the road sections in urban road network [START_REF] Hadachi | Increasing the Travel Time Accuracy in Arterial Networks using Particle Filter and Enhanced Map Matching[END_REF]. The next chapter will show all the details regarding the implementation of the whole system (software) plus the results of all what was done in this research work.

Chapter 5: Implementation, Results and Analysis

Introduction

The following chapter will present the implementation of the system. Furthermore, it will show and discuss the results of the experiments done using real world data. We should remind that the data used in our historical database is sampled with a rate of 60 seconds between each successive GPS data.

The results presented will be about each proposed algorithm. First, we will discuss the results of the map matching which include:

• A spatial map matching,

• Updated spatial map matching,

• Spatio--temporal map matching • A corrected spatio--temporal map matching. The second point will be the verification of the stated hypothesis about the speed distribution. Finally, we will show the results of travel time estimation using basic Monte Carlo Method and enhanced one.

Building the Digital Map

In this section we will describe the implementation done in order to extract the digital map and add the GIS information. This latter refer to the PUMAS points, PUMAS sections, road type, road orientation, road section's speed limit, etc.

Description and Implementation

As we said before in chapter 3 that we used OpenStreetMap (OSM) in order to extract the XML file (Raw OSM Data) containing the information about the map. The figure 5.1 shows the way the information extracted are written. For example the node contains its id and to each way or section is connected and its coordinates. Besides, it will have also the information about the ways or section, their id, connection id, etc. Figure 5

.2: Class Diagram of the Building Digital Map Process

The parser class has a lot of functionalities. It reads the OSM file (XML) and recovers the data using the function "parseOSM", stores the data in the database using the function "storeOSM" and transforms them into PUMAS Sections and Points PUMAS using the function "createMap". Finally, it starts the calculation of shortest paths through the method "calculateShortestPaths". Moreover, almost all the function inside the parser class uses some instances of the PUMASHandler class to handle some processes or events. The PUMASHandler class it contains all the information and dictionary of the new GIS information. Additionally, it helps the building of the new map with all the information needed.

Results

The results are shown as map illustration (figure 5.3). By building, the digital map we have all the information stored in the database. We have the information regarding the exact position of PUMAS point, which refer to the start and end of each road section. In addition to the PUMAS sections where know the length of each section, the starting and the ending PUMAS points defining the section, and also the speed limit on each section. Finally, we have the type of the PUMAS section if it is expressway or an urban road, plus the orientation of the road (one way or two ways). The road network contains 7739 PUMAS points and 18874 PUMAS sections.

Map--Matching

As discussed in chapter 3, the navigations system cannot have good performances sometimes in positioning the vehicles on a digital map of road network due to the urban canyons, streets with dense tree cover, and tunnels. In this section we will test the algorithm presented in chapter 3 and analyze the results.

Description and Implementation

In chapter 3 we described in details our method. Figure 5.4 shows the top--down analysis diagram where the map--matching function uses or calls other function in its process. For example, the function cap_threshold is the function that checks the condition on the speed of the sparsely sampled GPS data (speed condition details chapter 3 section 3.3.3.3.3). The functions are coded using SQL; therefore, they contain SQL queries. By receiving the raw data, the map_matching function sends an SQL query to start the mapping process with the information about the activation of the orientation_check process or not. Thus, the algorithm described in chapter 3 is running and processing the input data. Figure5.4: Top--Down Analysis of the SQL map matching function As we presented in chapter 3 during the process of map_matching we call the function that find out the shortest path between two sparsely sampled GPS data. In the previous section of this chapter we showed that the learning process of the finding shortest path is done when we are creating the digital map. The function that the map_matching uses to call the shortest pathfinder is the TDSPP_Calculator. This latter uses the class graph, class vertex, and class edge (

Test Strategy

The test strategy describes the nature of data used and the manner how the test will be done. In addition, we will state the criteria chosen in order to make the evaluation of the results.

Dataset Description

In this part we will define the data used in order to run the test. Road Network: In our experiment, we used the road network of Rouen city that we created in the previous section (figure 5.6). The network contains 7739 vertices and 18874 road sections. The figure 5.6 shows the created digital map that we use in our system. The gray segments are the road section and the one in color show an example of trajectory with colored quality information. Figure 5.6: Road Network of Rouen Test Data: the data was collected from the real world as it was described in chapter 2 section 2.5.5. We used those data that have GPS information with a frequency of one seconds. In order to make our tests we defined an experiments plan. In this plan we defined trajectories that will pass by the big axes and the small road in the city center. This will allow us to compare the output of the algorithms and the ground truth because we already know the exact trajectories.

Evaluation Approach

Ground Truth: the data collected from the real world field constitute the ground truth. Moreover, the trajectories are known and defined before doing the test. Thus all the data collected is from known trajectories and road sections. The data that we will use in this test is the GPS data with a frequency of one second collected from the field. Then we will use it to simulate our database sparsely sampled GPS data with a frequency of 60 seconds. These simulated data will be the input of our map--matching system.

Evaluation Criteria: in order to evaluate our map--matching approach (STC--Matching). We will check the running time and the matching quality. The running time is measured by the actual program execution time. The matching quality is measured using the accuracy metric defined as follows:

A num = Number data correctly matched
Total number of data

(5.1)
Where, number data correctly matched is the number of data matched to the right road section. The Total number of data (n) is the total number of data used in the test, which are all the available GPS positions.

Baselines: during the presentation of the results and the analysis, we chose to show the evolution of the idea that we had during working on this issue of map matching, till reaching the final method presented in the chapter 3. First approach that we adopted to deal with the problem was the spatial analysis approach (S--Matching). Then we added the temporal analysis to the method (ST--Matching). Next step was to take in to account the heading of the vehicle and the road orientation, then make correction of the raw data that was rejected during the process.

Experimental Results

S--Matching

Results

First test result that we are going to show is the accuracy results of the S--Matching approach. Figure 5.7 shows that we have 60% of the data were matched correctly to their concerned road sections. And 14% of the data was matched but to the wrong road sections. Finally 26% of the data was not matched at all.

Analysis

When we check the results closely we find out that there is some problem with the digital map. Which explains the unmatched results. The problems that we found is some missing nodes and sections on the digital map that they don't exit in the extracted XML file (figure 5

S--Matching after The Map Update (Sup--Matching)

Figure 5.10 show that we made an enhancement of the results. We have 65% of the data were correctly matched to the right sections and 19% of the data was unmatched. Then the matched incorrectly has increased, now it is 16%. Which mean that we saved some of the rejected data. In the next section we will show the results when we add the temporal analysis to the algorithm.

Results

The next result is the results of the spatio--temporal approach (ST--Matching approach). Figure 5.11 show that we have 89% of the data were matched correctly to the concerned road sections. And 3% of the data was matched but to the wrong road sections. Finally 9% of the data was unmatched at all.

65% 16%

Analysis

The temporal aspect add to the algorithm allow us to take into consideration the real path logic in the matching process. Thus we take into consideration trajectory logic between the sparsely sampled GPS data. However, we noticed that some of the data is matched to the wrong section. This problem is due to the fact the road orientation is in the opposite direction compared to the vehicle's heading received from the probes. The figure 5.12 illustrates clearly this problem related to the road orientation and the vehicle's heading.

94%

The results in table 5.2 shows the STC--Matching algorithm give good results compared to the others. Especially, compared to the ones that they used the same navigation systems. Moreover the running time of the process figure 5.15 is acceptable. The "Inf" notation in the graph means that we did not put a limit to the number of data processed. The number of candidates represents the number of GPS position injected into the system to be matched. Overall, the running time of the system is acceptable.

Figure 5.15: STC--Matching Running Time vs Number of candidates Now that we showed the results concerning the map--matching process, we will check our hypothesis stated about the speed distribution per road section.

Speed Distribution

In this section we will check the hypothesis stated in chapter 4 about the speed distribution.

Description

The test that we will conduct in this part is to try to found out if the speed follows a bimodal distribution on each road section.

Test Strategy 5.4.2.1 Dataset Description

Road Network: In our experiment, we will use the same network defined before in the map--matching test. The network contains 7739 vertices and 18874 road sections. Test Data: the data used in this test is the sparsely sampled GPS data available in our historical database. The data contain about ten millions GPS positions that was collected over one year.

Evaluation Approach

Evaluation Criteria: in this test analysis we will start by creating a histogram of the speeds detected in each road section in our road network. The histogram will help us to get an idea about the speed distribution.

Experimental Results

Results

The test ran on the historical database showed that almost all the speed histograms of each section follow a bimodal distribution. The figure 5.16 gives an overview of the results that we found after running the test.

Results

After running program on our simulated historical database we get the travel time estimation. Then we compute the percentage difference error with the travel time reference that we computed from the real--world field experiment (Table 5.3).

Analysis

Based on the results obtained it seems that the TT--MCM algorithm give interesting results by an average percentage difference error equal to 7% per road section.

Travel time estimation based on Monte Carlo method enhanced with measurements and road sections characteristics (TT--MCM--E)

Results

We will run the same process for the TT--MCM--E on our simulated historical database we get the travel time estimation Tp est!MCM !E . Next we compute the percentage difference error (Table 5.4). Table 5

Number of Erros % Difference Error's Intervals

The histogram has a shape of half Gaussian distribution with an average percentage difference error per road section equal to 2% and its standard deviation is 8%. Based on the description of the histogram there is a big chance that the errors will be in the area of ]0--10].

Analysis

The result seems to prove that the TT--MCM--E approach gives better results than the TT--MCM. However, in order to have a clear idea about the results we will conduct a different criterion in comparing the two methods.

Comparison of the Two Methods

Evaluation Criteria

In order to have more information about the performance of the two methods we will conduct a mean square error (MSE) evaluation. The MSE analysis is used to evaluate the error between a series of numbers found in a pair of same dimension vector arrays. For two distinct arrays X and Y, the general formula for the MSE equation is defined as follows:

MSE = [ (x i ! y i ) 2 i=1 n " ] 1/2 n (5.
3) Where,

• x i is the ith element in array X • y i is the ith element in array Y

• n is the number of elements in arrays X and Y Thus in our case the equation will be as follows:

MSE = [(Tp ref ! Tp est ) 2 ] 1/2 1
(5.4) We will define also the percentage MSE as follows:

PCTMSE = 100%*[ MSE Tp est ]
(5.5)

Results

132

The results will be represented in figure 5.21. The histogram gives an idea about the percentage of mean square errors of the two methods. On one hand, It is clear that the errors produced by the MCM approach are higher than the MCM--E.

Figure 5.21: Histogram of PCTMSE (%) of the two methods On the other hand, the MCM method produced almost a mean error of 32% and the MCM--E approach a mean of 8% (Table 5.5). Therefore, the MCM--E has a tendency to make less error per road section than the MCM method. The mean error does not give a clear idea about the performance of the two methods. For this reason will give the errors interval in order to know the MS error percentage per road sections. The TP--MCM approach has an interval error between 0% and 97% and the TP--MCM--E has an interval error between 0% and 34% (Table 5.6). Thus, the TP--MCM--E gives less error per road sections compared to the TP--MCM method. 5.21 it is clear that the TT--MCM--E method has the lowest percentage MS error per road section. Based on this it seems that the TT--MCM--E approach gives better results than the TT--MCM method. However, by checking the graph figure 5.21 and table 5.5 carefully, we found that in some cases the TT--MCM--E method misses sometimes the real results or produces more error than the MCM method. Which means that the problem is coming from the probability density function of travel time extracted from the historical database of the sparsely sampled data that we used. From the map (figure 5.23) it is clear that some section does not have enough data to learn about the travel time distribution per road section. Which explain the reaction of the TT--MCM--E approach and its results. Because, in some road sections either we don't have enough data or no data in order to give a realistic probability distribution of the travel time per road section that we use in MCM--E approach. As consequence, the weighting process in the particle filter affects bad quality weights to the particle. Thus, the travel time estimation is not good. Concerning the running time of the system is shown in figure 5. [START_REF] Arulampalam | A tutorial on particle filters for online nonlinear/non--gaussian bayesian tracking[END_REF]. We can see that the system is capable of running a lot of data without any problem.

MS ERROR (TP--MCM) (%) MS ERROR (TP--MCM--E) (%)

Conclusion

The results collected in this thesis work regarding the travel time estimation using the Monte Carlo Methods with an enhancement gave interesting and encouraging results. In addition, the approach to estimate the travel time is new and of Couse needs more test and enhancement. It is hard to do so, because of the use of sparsely sampled GPS data, which is already challenging. Moreover, filtering the data and the map--matching make the issue more complicated; because the good performance depends also on the good performance of the other components (filtering, map--matching, etc). Plus, to make good estimation we need important amount of data with good quality.

System Platform for project PUMAS

The fact that this thesis works was done within a project; the Creation of a friendly graphical interface where we can view all the information of the system was a need. The interface will allow viewing the results in a statistic and cartographic manner. The parameters interface is set by default; however, we are allowed to change the setting of the parameters as it is shown figure 5.25. The parameter window contains all the parameters that are used in the system and we can control and change them.

Conclusion

To sum up, in this chapter we presented the results of this thesis work. The chapter dealt with the implementation description, test strategy for each section, evaluation criteria for each proposed method. Each presented results was analyzed and discussed. In general the results obtained concerning the map matching are encouraging. However, there some issue where there is more work to be done; especially regarding the digital map and the GIS information, some of the problems was discussed in that section. For example, the map is not really representing the real world, some road sections are missing or some intersections. We did as we could an update of the digital map in order to reduce the errors. Besides, we tested the travel time estimation results and analyze them. The new approach presented is very interesting and promising. However, the approach depends on other information that we collect from the historical database, which mean we need a good data to get better performance. Finally at the end we presented the GUI developed during this thesis period for viewing the results in friendly way and easy to understand. The global results of this thesis work are a good start for the new approach and as we know there is nothing perfect from the first try. Thus, there some work to be done in the future to make the approach more robust.

Chapter 6: Conclusion and Perspectives 6.1 Conclusion

This thesis research work was conduct within the project PUMAS, which was an advantage for our research regarding the collection process of our data from the real world field and also in making our tests. The research done can be listed under the field of intelligent transportation systems. Besides, the output of this thesis was software that was used in the project. The software was designed in such manner to be integrated in any other design and also it is easy to add other modules to it or make changes. Our objective was to estimate travel time using sparsely sampled data in an urban context. The context and the nature of data used presented many challenges, which pushed us to conduct many other issues before treating our main goal. After a bibliography study about the subject in chapter 2 we come out that we need to investigate other sub subjects before estimating travel time per road section. Our research work in this thesis investigated four fields and they are as follows: building digital map with its specific geographic information system (GIS), map--matching problem, shortest path problem, and estimating travel time per road sections in a urban context.

Digital map and GIS information

During our research we faced the importance of creating the digital map for example in transportation planning and logistic, it is advantageous to use digital map incorporated with information such as transportation facilities data, speed limits, roadway indicator, and type of roads. All this information is very helpful to improve traffic algorithms and estimations. Thus, we extracted our digital map from OpenStreetMap (OSM) and we added our GIS information that contain all the information needed such as speed limit on each section, intersection, defining the roads directions and type, new features, etc. the digital map created in this thesis work can be used in any application for traffic purpose.

Map--matching problem

In our approach we were inspired by (Zhao,[START_REF] Isard | CONDENSATION --Conditional Density Propagation for Visual Tracking[END_REF] approach to define the area of interest and we defined a spatial analysis criteria by detecting the road section that has the highest probability that the GPS position should be matched to it in the digital map, without having to scan the whole map. Then we added temporal analysis criteria that we defined. Finally, we used [START_REF] Kim | Efficient use of the digital road map in various positionning for ITS[END_REF] method by applying an orthogonal projection on the GPS position into the road section concerned that have the highest score of the combination of spatial and temporal criteria. Moreover, we added the idea of road orientation and the vehicle's heading in order to enhance the map matching. The orientation informs us about the direction that the car is following making it easier to locate the road that has the same direction as car's heading. In some of the case we still have a non-matching cases. Therefore, we added a correction method [START_REF] Balasundaram | Location Prediction Mechanisms for Tracking Lost Unmanned Vehicles[END_REF] that make a new prediction of the defective data and then apply the whole process of map matching to the corrected data.

Time--dependent shortest path problem

The time--dependent shortest path problem given a departure and arrival time was one of our research interests. There are many solutions that has been developed for different types of graphs such as Dijkstra in the case of positive weights, Bellman in the general case, etc. However, these methods are time consuming regarding the computational process, which mean that they need enhancement and speed up. We adopted a new approach in a database context. In this new method we introduced a new step that we called a learning phase that we process on offline mode using a recursive Dijkstra and then when the method is called by the map matching on online status. Introducing this learning step at the level of the database enhanced the speed of finding the answer on online mode.

Travel time estimation per road sections

The use of sequential Monte Carlo approach to estimate travel time using sparsely sampled GPS data is certainly not new. However, the application of Monte Carlo methods on urban networks has not been found in the literature. Accurate travel time estimation is an important element for advanced traveler information systems and advanced traffic management systems as well as for all transport users. In urban networks, travel time estimation is challenging due to many reasons such as the fluctuations in traffic flow due to traffic signals and drivers behavior.

Travel time estimation using Monte Carlo method

Using this approach we adopted the Monte Carlo method to our case by defining the state equation of the case studied. The creation of the filter was done in such way to process and use the sparsely sampled GPS data. The filter gives us the ability to estimate the moment when the probe vehicle enters a road section and also when he exits the same road section. By considering these information it was easy for us to know how long the probe vehicle was in that section. Which means that we have the travel time of the probe vehicle in that specific road section.

Travel time estimation using Monte Carlo method enhanced with measurements and road sections characteristics

The enhancement of this approach was by changing the algorithm by injecting it with information concerning the measurements and characteristics of the concerned road section on the road network. This information was injected at the level of weighting process of the particles generated by the particle filter or Monte Carlo method. The weight injected is a probability density distribution of the time distribution on the road section learned from the historical database. This maneuver makes this approach original and new. Moreover, in order to have a results closed to reality we added in both methods (TT--MCM and TT--MCM--E) the notion of delay time at the level of road intersections. This aspect was added in order to illustrate the lost time at a traffic light or when we are changing road sections during our journey trajectory. In addition the results obtain are very encouraging to continue on the evolution and enhancing the approach presented in this thesis work. Besides, it can be an open window to solve other problematic in the domain of ITS and traffic management.

Perspectives

The travel time estimation is a small puzzle of the big image of traffic status. However, each small pawn constitutes the traffic chessboards that are very important. Travel time estimation is one of those pawns. The future work that can be done is to use the other pawns that will be discussed in the next sections.

Short--term agenda 6.2.1.1 Travel time in urban arterials

As a continuation of our research work it will be beneficial to use different sensors to make the estimation of travel time more precise. The traffic data from probe vehicles, loop detectors and camera detector sources have different levels of precision, which may result in inconsistency and sometimes even contradictory estimates. Data fusion is the processing tool and solution. This latter takes into account the quality of the data provided by each source with an aim of increasing the precision, reliability and robustness of the estimation. Another aspect that can be very interesting is the combination of the mathematical models and statistical models based on real world observation. This approach will help to increase the precision of the estimation and also build an understanding of the real world and its behaviors. This approach needs a large amount of data to be processed; however, nowadays with an advance in technology and research it is possible to afford the data needed. By building and making available a historical data of estimated travel time per road sections. The next step will be to understand the traffic behavior. In order to do so, for example we can introduce an artificial intelligence (AI) method. This latter technique seeks to understand natural intelligence and to build intelligent systems. There are many techniques that have been applied in the fields (Lee, 2009) [START_REF] Lee | Freeway Travel Time Forcast Using Artifical Neural Networks with Cluster Method[END_REF]. The most common method in the AI is Neural Network (ANN). The ANN have been applied in many fields like engineering management, science and also psychology and it helps to improve the solving process of the transportation problems [START_REF] Dougherty | A Review of Neural Networks Applied to Transport[END_REF] [START_REF] Dougherty | A Review of Neural Networks Applied to Transport[END_REF]. Moreover, the ANN capacity includes classification, detection, pattern recognition, adaptive filtering, data inversion, target tracking, estimation, modeling, etc. Besides, there is a statistical approach that is applied to estimation, prediction and modeling. As an illustration, we can take the work of [START_REF] Zhang | Short--term travel time prediction[END_REF] [START_REF] Zhang | Short--term travel time prediction[END_REF] where he used data from loop detectors and probe vehicles to create a linear model for travel time prediction.

Traffic jam detection in urban network

One of the aspects that characterize traffic is the appearance of congestion. Thus it is an important step after getting information about travel time to detect congestions in order to complete the picture about traffic status. Most of the approaches used in the literature are based on the speed as a metric to describe traffic situation. However, the speed in urban areas is influenced significantly by road condition and traffic lights. Thus, applying this approach in real world field is not a good idea. Which means using speed alone as a metric is not a good choice. From this point of view, it is important to define a new metric in order to detect the congestions. For example, as it was shown by (K. [START_REF] Zhang | A Real time urban traffic detection algorithm based on spatio--temporal OD matrix in vehicular sensor network[END_REF] [START_REF] Zhang | A Real time urban traffic detection algorithm based on spatio--temporal OD matrix in vehicular sensor network[END_REF] the use of traffic rate as a metric and applying a spatio--temporal OD matrix gave good results regarding traffic jam detection. Our idea will be to use what was developed regarding the travel time estimation and use it as an input for the OD matrix. By using an accurate representation of traffic status regarding spatio-temporal aspect (ex. Travel time) the results of the OD matrix should be better and closer to the reality. Another approach to detect traffic congestions is by using cooperative vehicles. Cooperative vehicle have been used to enhance traffic safety and management. Though by this approach we can get more accurate information about the traffic status using V2V communications. For example [START_REF] Bauza | Road Traffic Congestion Detection through Cooperative Vehicle--to--Vehicle Communication[END_REF] [START_REF] Bauza | Road Traffic Congestion Detection through Cooperative Vehicle--to--Vehicle Communication[END_REF] proposed a method to detect congestions by using a cooperative probe based on V2V communications and a fuzzy logic without the need of any infrastructure sensors deployment. The use of cooperative vehicle can help to detect the birth of congestions. Moreover, we can add the sharing information aspect through the V2V communication to avoid the phenomenon of traffic jams. Therefore, the approach presented may be promising for good work that can be done in this issue, which will help a lot to understand the urban traffic.

Long--term agenda

For a long--term perspective we have to take into consideration the implications and the impact of our research. All what is developed in transportation is a small pixel of the whole image. This image is our cities and metropolitan regions. Nowadays, managing our cities is an issue of concern of everybody such as regional officials, road administrators, urban planners and citizens; in order to make good decision about the future of our cities, they need correct information. For example, making decisions about building new freeways, transit service expansion, land use regulations are often expensive and controversial with long-term consequences. From this prospective we must attempt to understand how different alternatives might affect land use, transportation, and the environment over the next decades. Therefore as a project related to what was done in our research regarding understanding the traffic via travel time estimation and prediction, traffic jam detection, and traffic simulation or forecasting; we can add the idea of land use in the system. Then we have to study the relationship between the road traffic and the land use. As we know, when we create a new housing area for example, we are obliged to create new roads. As a consequence, a new flow of traffic will be injected in the road network of the city. Afterward by merging the land use model and the dynamic traffic simulation model, we can help to make decisions regarding the choice of the location and size of the land used. Another interesting research subject for our society is evacuation under emergency situation. Dynamic traffic simulation models are used to support decisions when planning an evacuation. Till now, understanding the traveller's behavior under emergency evacuation condition is still conducted by researchers. There are some models trying to model the situation like (Pel, 2011) [START_REF] Pel | Modelling Traveller Behavior under Emergency Evacuation Conditions[END_REF], but there is a lot of effort to be done regarding this issue in research.

Publications

Chapter 6 : 146 List of Figures FIGURE 1 . 1 : 22 FIGURE 1 . 2 : 25 FIGURE 2 . 1 : 29 FIGURE 2 . 2 : 30 FIGURE 2 . 3 : 31 FIGURE 2 . 4 : 33 FIGURE 2 . 5 : 40 FIGURE 2 . 6 : 42 FIGURE 2 . 7 : 44 FIGURE 2 . 8 : 47 FIGURE 2 . 9 : 48 FIGURE 2 . 10 : 51 FIGURE 2 . 11 : 52 FIGURE 3 . 1 : 59 FIGURE 3 . 2 : 60 FIGURE 3 . 3 : 62 FIGURE 3 . 4 : 63 FIGURE 3 . 5 : 65 FIGURE 3 . 6 : 68 FIGURE 3 . 7 : 69 FIGURE 3 . 8 : 70 FIGURE 4 . 1 : 88 FIGURE 4 . 2 : 93 FIGURE 4 . 3 : 95 FIGURE 4 . 4 : 96 FIGURE 4 . 5 : 97 FIGURE 4 . 6 : 97 FIGURE 4 . 7 : 99 FIGURE 4 . 8 : 100 FIGURE 4 . 9 : 101 FIGURE 4 . 10 : 103 FIGURE 4 . 11 : 105 FIGURE 4 . 12 : 108 FIGURE 5 . 1 : 112 FIGURE 5 . 2 : 113 FIGURE 5 . 3 : 114 FIGURE 5 . 4 : 115 FIGURE 5 . 5 : 116 FIGURE 5 . 6 :FIGURE 5 . 7 : 118 FIGURE 5 . 8 : 119 FIGURE 5 . 9 : 119 FIGURE 5 . 120 FIGURE 5 . 11 : 121 FIGURE 5 . 12 : 121 FIGURE 5 . 13 : 122 FIGURE 5 . 14 : 123 FIGURE 5 . 15 : 124 FIGURE 5 . 16 : 126 FIGURE 5 . 17 : 126 FIGURE 5 . 18 : 127 FIGURE 5 . 19 : 129 FIGURE 5 . 20 : 130 FIGURE 5 . 21 : 132 FIGURE 5 . 22 : 133 FIGURE 5 . 23 : 134 FIGURE 5 . 24 : 135 FIGURE 5 . 25 : 136 FIGURE 5 . 26 : 136 FIGURE 5 . 27 :

 614611221225212922302331243325402642274428472948210512115231593260336234633565366837693870418842934395449645974697479948100491014101034111054121085111252113531145411555116565711858119591195120511121512121513122514123515124516126517126518127519129520130521132522133523134524135525136526136527 FIGURE 1.1: V2I COMMUNICATION USED IN THE PROJE PUMAS ........................................................................... 22 FIGURE 1.2: SCHEMATIC OVERVIEW OF THE STRUCTURE OF THE DISSERTATION ................................................... 25 FIGURE 2.1: SCHEMATIC DIAGRAM FOR ILLUSTRATION ........................................................................................... 29 FIGURE 2.2: SCHEMATIC DIAGRAM FOR APR SYSTEM ILLUSTRATION .................................................................... 30 FIGURE 2.3: ROAD SECTION TRAVEL TIME COMPUTATION FOR BLUETOOTH APPROACH ....................................... 31 FIGURE 2.4: THE STUDY AREA AND DATASET IN GREATER LONDON [23] .............................................................. 33 FIGURE 2.5: EXAMPLE OF SCALE INTERACTIONS AND THEIR REPRESENTATION BY MODEL COUPLING [49] .......... 40 FIGURE 2.6: ARCHITECTURE OF THE MOBILE MILLENNIUM SYSTEM [52] ............................................................ 42 FIGURE 2.7: PENETRATION RATE (MAGNETIC LOOPS VS. VTLS) ........................................................................... 44 FIGURE 2.8: VIEW OF THE PUMAS SYSTEM VISION ................................................................................................ 47 FIGURE 2.9: AN OVERVIEW OF PUMAS SYSTEM ..................................................................................................... 48 FIGURE 2.10: THE EMBEDDED SYSTEM PUMAS BOX ............................................................................................ 51 FIGURE 2.11: ITINERARY SAMPLE RECONSTRUCTED FROM THE COLLECTED DATA .............................................. 52 FIGURE 3.1: GIS LAYERS ........................................................................................................................................... 59 FIGURE 3.2: PUMAS DIGITAL MAP, ADDED FEATURES ......................................................................................... 60 FIGURE 3.3: EXTRACTION & ENHANCEMENT PROCESS ........................................................................................... 62 FIGURE 3.4: VIEW OF THE DIGITAL MAP THROUGH THE PROCESS ......................................................................... 63 FIGURE 3.5: CHAIN STRUCTURE OF RAW DATA VALIDATION FOR A SPECIFIC FLOATING VEHICLE .......................... 65 FIGURE 3.6: MAP MATCHING SYSTEM ...................................................................................................................... 68 FIGURE 3.7: CANDIDATE PROJECTION POINTS FOR A SAMPLE PI ............................................................................. 69 FIGURE 3.8: AN EXAMPLE OF WRONG MATCHING ..................................................................................................... 70 FIGURE 4.1: ILLUSTRATION OF SPARSELY SAMPLED GPS DATA ON THE DIGITAL MAP ........................................ 88 FIGURE 4.2: PARTICLE FILTER PROCESS .................................................................................................................. 93 FIGURE 4.3: SEVERAL LOGNORMAL DISTRIBUTIONS WITH DIFFERENT MEAN AND VARIANCE ................................ 95 FIGURE 4.4: SPEED NORMAL PROBABILITY DISTRIBUTION .................................................................................... 96 FIGURE 4.5: EXAMPLE OF TWO PDF WITH SAME MEAN AND DIFFERENT STANDARD DEVIATIONS .......................... 97 FIGURE 4.6: SPEED PROFILE [ARONSON 06] ........................................................................................................... 97 FIGURE 4.7: EXAMPLE OF GAUSSIAN BIMODAL DISTRIBUTION ............................................................................... 99 FIGURE 4.8: THE PDF OF THREE DIFFERENT TRAFFIC STATUS FOR A ROAD SECTION WITH FOUR LANES [122] . 100FIGURE 4.9: ILLUSTRATION OF SPARSELY SAMPLED DATA ON THE MAP (GREEN SQUARES ARE THE PUMAS POINTS) ......................................................................................................................................................... 101 FIGURE 4.10: TP FORWARD AND TP BACKWARD ILLUSTRATION .......................................................................... 103 FIGURE 4.11: ESTIMATION FILTER ALGORITHM1 (N: NUMBER OF PARTICLES, M: NUMBER OF ITERATIONS) ..[START_REF] Zhang | A Real--time urban traffic detection algorithm based on spatio--temporal OD matrix in vehicular sensor network[END_REF]

Figure 1 . 1 :

 11 Figure 1.1: V2I Communication used in the project PUMAS 1.3.2 PUMAS Expectations The results awaited from the PUMAS project are the following: • Demonstrate the feasibility and added value of mixing conventional traffic data with probe data to generate travel times in a city context • Compare the floating cars data source approaches of dedicated fleet versus general public floating cars data. • Evaluate traffic based versus statistical algorithms and identify their best performance domains with a possibility of fusion 1.4 Contributions and RelevanceIn this section we will show the main contributions of this dissertation and also the scientific relevance of the approach and the methods used.1.4.1 ContributionsThe main contributions of this thesis can be summarized as follows:a. The estimation of travel time per road sections was done on urban road network, using sparsely sampled GPS data. Moreover, the estimation was based on the family of sequential Monte Carlo Method, more specifically on particle filter.

Figure 1 . 2 :

 12 Figure 1.2: Schematic overview of the structure of the dissertation

Figure 2 . 1 :

 21 Figure 2.1: Schematic diagram for illustrationRegarding the information collected from the loop detectors many extrapolation methods have been developed to estimate travel time[START_REF] Chu | Adaptive Kalman Filter Based Freeway Travel time Estimatio[END_REF],[START_REF] Van Lint | Improving A travel Time Estimation Algorithm by Using Dual Loop Detectors[END_REF].2.2.1.1 Half--Distance ApproachIn this approach the assumption is that the speed measured by a set of dual loop detectors (figure2.1) is valid to the half--distance on both sides. Therefore, the travel time between the two loops is defined as follows (equation 2.1):

Figure 2 . 2 :

 22 Figure 2.2: Schematic diagram for APR System Illustration 2.2.3 RadarThe radars have the ability to collect velocity, flows, and occupancy data when you place them along the side of roads. There are mainly implemented in highways rather than urban areas. Moreover, they are suitable with massive data collection; nevertheless, the collected data has low accuracy. Moreover, the accuracy data collected decreases in arterial environment. The radar uses vehicle speed S computed using the time difference ΔT corresponding to the vehicle reaching at the leading edges of two range bins. The distance D separating the range bins is known. The vehicle speed is given by equation 2.4:

  Figure 2.3: Road section travel time computation for Bluetooth approach

Figure 2 . 4 :

 24 Figure 2.4: The study area and dataset in Greater London [23] 2.2.7 High frequency GPS DataThe high frequency GPS insinuates when the probe vehicle has the ability to send GPS information every few second or each second (no more than 10 seconds). This aspect makes the data the most accurate regarding the itinerary and also the travel time per road section. It seems that using this kind of technology is the most accurate but still poses some problems with the map matching, especially close to the roundabouts or intersections. This will affect the localization on the map and also computing travel time[START_REF] Sen | Frequency of probe reports and variance of travel time estimates[END_REF]. Moreover, receiving this kind of data each second through the means of communication into the server is expensive. However, there some potential solution to this issue that Project PUMAS has treated.2.3 Travel Time Estimation/Prediction ModelsAvailable models can be categorized based on their way of computation to different kinds of statistical models, mathematical models, simulation models, and artificial intelligence models. Thanks to research, there are hybrid models too, where the hybrid models incorporate the combination of two or more the above cited models. For example the statistical models include Particle Filtering[START_REF] Arulampalam | A tutorial on particle filters for online nonlinear/non--gaussian bayesian tracking[END_REF], Monte Carlo Method[START_REF] Hongwei | Study on the Reliability of Travel Time in Transportation Network[END_REF], Kalman Filtering[START_REF] Yang | Travel time prediction using the GPS test vehicle and Kalman filtering techniques[END_REF], Bayes Analysis[START_REF] Casper | A General Model of Bayesian Travel Time Learning[END_REF], etc. The models that took advantage of research in the Artificial intelligence are mostly based on

Figure 2 . 6 :

 26 Figure 2.6: Architecture of the Mobile Millennium System [52]The system architecture is based on the concept of "Virtual Trip Lines" (VTLs). These are a kind of geographical markings stored directly at the client level; in our case it is the mobile phone.

Figure 2 . 8 :

 28 Figure 2.8: View of the PUMAS System VisionThe purpose of the PUMAS project is to create a platform of travel time information to towns and cities. The main objectives are: •Create a new generation of software producing journey times, matching the users expectations.• Participate in the emerging sustainable economy where public transport systems are an alternative to road networks by providing better information on traffic conditions.2.5.2 System ArchitectureTo view a system architecture there are many ways but we chose to show the functionality architecture of the system as it is illustrated in (Figure2.9). There are two components, the server and the embedded box in the cars named PUMAS Box. The PUMAS Box is capable of collecting information about probe vehicle journey. The Box performance can be resumed as follows:• The ability to gather data, the GPS position, travel time, traffic jam.• The ability to temporarily store and process data • The ability to store reference data (eg. Mapping)• The ability to communicate data to a server: GPRS or WiFi,• Power supply (cigarette lighter or installation)

Figure 2 . 9 :

 29 Figure 2.9: An Overview of PUMAS System

Figure 2 . 11 :

 211 Figure 2.11: Itinerary Sample Reconstructed from The Collected Data During this experiment the following equipment was used: • Three Citroen C3 LaRA with their embedded systems consisting of: PC with RT maps (software with a component based framework for rapid development of multi--modal applications), a PUMAS--BOX connected to the PC and communicating with the server, a fixed GPS, a color camera positioned at the windshield, a sparsely sample GPS box transmitter; which we used in order to

Figure 3 . 2 :

 32 Figure 3.2: PUMAS Digital Map, Added Features3.2.3 Context ModelAs it was stated in the section 3.2.2, the context model will complete the information needed to the digital map though the road model characteristics. Let's start by describing the two existing context models. The first one is the global context and the second one is the local context.

  the time of reception of the GPS data coming from the floating cars. For the purpose of checking the time step between GPS location ! ! ! of a specific floating ! ! car we will define two kinds of time steps (equation 3.1):

Figure 3 . 5 :

 35 Figure 3.5: Chain structure of raw data Validation for a specific floating vehicle. The graph shows how the computation structure is built and in each cell we will find the out put of this equation ℱ ℎ ! ! + Τ ! ! ! and then we apply the rule

Figure 3 . 8 :

 38 Figure 3.8: An example of wrong matching Definition 9: (Transfer probability function) the transfer probability for a given projection candidate and for two successive sparsely sampled GPS data and is the likelihood that the true path from to follows the shortest path through to . The transfer probability function will be expressed as follows (equation 3.6):

Definition 10 :

 10 (Orientation check function) this function checks the orientation between the sparsely sampled GPS data and the PUMAS section selected orientation

Definition 14 :

 14 (Travel time constraint function) is the time needed to go from the source position c k .t to the destination or target c k+1 .t . The function will be defined as follows: h(c i!i+1 .T ) = c k+1 .t " c k .t . In other words this function represents the travel time that the probe vehicle did to go through the two positions. Definition 15: (Travel time per road section function) this function computed the travel time needed to cross it. The formula is a basic one based on the length of the road section and the speed limit on the concerned road section. This latter information we get from the digital map. f (e i .t) = e i .lenght e i .V l . (3.18) Definition 16: (Cost function) clearly the cost function will be related to two other functions defined early that are related to the departure time and arrival time. The cost function will give a sense to the constraints by an accumulated cost associated to the estimated travel path or formally (equation 3.19):

Definition 19 :

 19 (Data time distance function) is the function that computes the time distance between the GPS position on the edge and the end or start point of the edge. We will define as follows: T DS (c k ) = f (e k .t)* L(c k ) e k .lenght (3.21).

Figure 4 . 1 :

 41 Figure 4.1: Illustration of Sparsely Sampled GPS Data on the Digital Map.The issue is to estimate the travel time between two successive sparsely sampled GPS data. The process start by detecting all the road sections which means find out all the PUMAS points between the two successive sparsely GPS data. Moreover this process can be done successfully when we apply all the processes described in chapter 3. After determining the PUMAS points the remaining step is to estimate the moment of passage through those virtual position (PUMAS points) then it is easy to find out the travel time estimation per road sections. Our approach to solve the problem will be based on the family of sequential Monte Carlo Methods (MCM). These methods are interesting for us due to their

2 .

 2 Measurement update t> to Calculate for and Normalize 3. Re--sampling for each t> to (a) Take N samples with replacement from where the probability to take sample i is . This step is called Sampling Importance Re-sampling (SIR) or Bayesian bootstrap. (b) Only re--sample when and set

93 4 . 2 Figure4. 2 :

 422 Figure4.2: Particle Filter ProcessAfter this remainder (figure4.2) of some generalities about the particle filter based on the Monte Carlo methods. This approach allows us to construct recursively a cloud of particle weighted approaching the filter law. However, the recursive nature of the filter leads to a degeneration of the cloud induced by an augmentation through time of the unconditional variance of its weights. In order to control this degeneration of the particle clouds the resampling process allows to limit this aspect by giving more importance to the significant weights. Our objective in this dissertation is not to make the basic algorithm of particle filter better, but to find out the best adaptive one for our case of study in this thesis work. More details about the changes done will be shown in the next sections of this chapter. After this discussion we will describe some of the known distribution used in the field.

Figure 4 . 3 :

 43 Figure 4.3: Several lognormal distributions with different mean and variance Galton and McAlister 1897 did the first article in the literature where they initiated the study of the distribution in order to use the geometric mean as an estimation of location. It seams that this distribution give interesting results for example in[START_REF] Hunter | Path and Travel Time Inference from GPS Probe Vehicle Data[END_REF] the author used this distribution to estimate the path/location and travel time using sparsely sampled GPS data.4.4 Travel time parameters DistributionsIn the previous section we skimmed through the particle sampling process where we choose a distribution for our particles. Which is an important process in the Monte Carlo approaches because it will affect the output of the particle filter. Regarding our work in this dissertation to estimate the travel time per road section is touching three aspects location or distance, time, and speed. Based on this three aspect we will discuss and try to define their distributions.4.4.1 Speed distribution on a road section

Figure 4 . 4 :

 44 Figure 4.4: Speed Normal Probability DistributionThis kind of distribution allows us to characterize the speed using two features the mean and the standard deviation. Another aspect of the distribution is when we have the same mean but different standard deviations (Figure4.5). This issues discussed will be check in chapter 5.

Figure 4 . 5 :

 45 Figure 4.5: Example of two pdf with same mean and different standarddeviations These kinds of speed can be clearly noticed when we try to find out the speed profile in the road network (more details in chapter 5). The speed profiles are a graphical representation of speed features plotted by location. Besides, the use of speed profiles can help to analyze and evaluate the speed attitudes. The purpose behind this enlightenment is to show: how hard to estimate the right speed distribution that reflects the reality. As the Figure4.6 shows that the driving behavior can be really complicated because of the people's interaction when using their vehicles between themselves and the use of speed on the urban road. Moreover, based on the figure 4.6 we can notice that the speed displacement of the male's speed graph cover in uniform way a large interval.

Figure 4 . 6 :

 46 Figure 4.6: Speed Profile [Aronson 06]After this brief discussion about the speed distribution it is clear that it is not easy to come out with a perfect distribution reflecting the reality but we will try to approach this reality. In order to determine the shape of the speed distribution, a common method to use is the histogram. Although the histogram method is widely used for data interpretation in many areas, it should be commented that the histogram method has a potential limitations because this method strongly depends on data origin, bin interval, and bin width[START_REF] Martinez | Computational Statistics Handbook with MATLAB[END_REF]. This issue point to the fact that the histogram should be well constructed. Besides, the histogram is very good to use to get brief information about the speed

Figure 4 . 7 :

 47 Figure 4.7: Example of Gaussian Bimodal Distribution In the urban network due to the traffic jam phenomena a single distribution cannot be appropriate to the situation. Thus the speed distribution needs two separate regimes as a mixture of two different Gaussian or normal density distribution. From this point, the first mixture component representing the low-speed regime can be formulated as N (µ 1 , s 1 !1 ) and the second mixture component showing the high--speed regime can be represented by N(µ 2 , s 2 !1) . As consequence, the speed Gaussian mixture model in this case will be as follows:p v (v \ µ 1 , µ 2 , s 1 , s 2 ,! 1 ,! 2 ) = ! 1 N (µ 1 , s 1 !1 ) + ! 2 N (µ 2 , s 2 !1 ) (4.17)

Figure 4 . 8 :

 48 Figure 4.8: the pdf of GPS locations [122]Based on this analysis, it is clear that most of the cases the vehicle locations x follows a normal distribution on a road section. Moreover, the vehicle locations

Figure 4 . 9 :

 49 Figure 4.9:Illustration of Sparsely Sampled Data on the Map (green squares are the PUMAS points)

Figure 4 .

 4 Figure 4.10:tp--forward and tp--backward illustrationMoreover we attribute a weight to each estimated tpf and tpb. The weight function was defined in such a way to take into account the accuracy of the estimation by using a time distance notion. These equations are:

Figure 4 . 11 :

 411 Estimation filter algorithm1 (N: Number of particles, M: Number of iterations) [129]

Figure 4 . 12 :

 412 Figure 4.12: Estimation filter algorithm2 (M number of iterations, P number of PUMAS points, N number of particles) [132]

Figure 5 . 3 :

 53 (a) Extraction and reconstruction of the digital map, (b) is the new map with the PUMAS points in red and the PUMAS section linking the PUMAS sections 5.

  Figure5.4: Top--Down Analysis of the SQL map matching functionAs we presented in chapter 3 during the process of map_matching we call the function that find out the shortest path between two sparsely sampled GPS data. In the previous section of this chapter we showed that the learning process of the finding shortest path is done when we are creating the digital map. The function that the map_matching uses to call the shortest pathfinder is the TDSPP_Calculator. This latter uses the class graph, class vertex, and class edge (Figure5.5). The class Edge represents the arcs of our graph. Then the class vertex is the node of our graph. Finally the class graph is set of vertices and edges constructing the whole graph.

Figure 5 . 5 :

 55 Figure 5.5: Class Diagram of the TDSPP_Calculator 5.3.2 Test StrategyThe test strategy describes the nature of data used and the manner how the test will be done. In addition, we will state the criteria chosen in order to make the evaluation of the results.5.3.2.1 Dataset DescriptionIn this part we will define the data used in order to run the test. Road Network: In our experiment, we used the road network of Rouen city that we created in the previous section (figure5.6). The network contains 7739 vertices and 18874 road sections. The figure5.6 shows the created digital map that we use in our system. The gray segments are the road section and the one in color show an example of trajectory with colored quality information.

Figure 5 . 7 :

 57 Figure 5.7: S--Matching Results

Figure 5 . 8 :Figure 5 . 9 :

 5859 Case of missing node in the OSM map, (white node exist, black node does not exist) ((a) digital map of the system, (b) Google map 2012) Another problem detected with the digital map in some case we have a bad fusion of OpenStreetMap road sections, which affect the creation of the PUMAS Sections in the digital map used (figure 5.9). For example in figure 5.9 we can see the creation of two road section in the circled road; however, in reality it is only one road section. Example of bad fusion between OSM data and creation of PUMAS sections ((a) digital map of the system, (b) Google map 2012) Thus we made an update of the digital map in order to fix these issues by adding the missing nodes and fixing this fusion problem in the creation of the PUMAS sections.

120

 120

Figure 5 .

 5 Figure 5.10: S--Matching results after updating the map 5.3.3.2 ST--Matching 5.3.3.2.1 ResultsThe next result is the results of the spatio--temporal approach (ST--Matching approach). Figure5.11 show that we have 89% of the data were matched correctly to the concerned road sections. And 3% of the data was matched but to the wrong road sections. Finally 9% of the data was unmatched at all.

n=4476 121 Figure 5 . 11 :

 121511 Figure 5.11: ST--Matching results5.3.3.2.2 AnalysisThe temporal aspect add to the algorithm allow us to take into consideration the real path logic in the matching process. Thus we take into consideration trajectory logic between the sparsely sampled GPS data. However, we noticed that some of the data is matched to the wrong section. This problem is due to the fact the road orientation is in the opposite direction compared to the vehicle's heading received from the probes. The figure5.12 illustrates clearly this problem related to the road orientation and the vehicle's heading.

Figure 5

 5 Figure 5.12: Example of the orientation problem

84 5

 84 In order to have a clear view of the results we will outline the percentage difference error in a histogram (Figure5.19).

Figure 5 . 19 :

 519 Figure 5.19: Histogram of Percentage Difference Error Frequency of The TT--MCMThe histogram has a shape of half Gaussian distribution with an average percentage difference error per road section equal to 7% and the standard deviation equal to 13.57%.5.5.3.1.2 AnalysisBased on the results obtained it seems that the TT--MCM algorithm give interesting results by an average percentage difference error equal to 7% per road section.

. 4 :

 4 Sample of The Percentage Difference Error of The TT--MCMsame we will represent the results of the percentage difference error in a histogram representation (Figure 5.20).

Figure 5 . 20 :

 520 Figure 5.20: Histogram of the Percentage Difference Error Frequency of the TT--MCM--E

Table 5 . 5 :

 55 Figure 5.21: Histogram of PCTMSE (%) of the two methodsOn the other hand, the MCM method produced almost a mean error of 32% and the MCM--E approach a mean of 8% (Table5.5). Therefore, the MCM--E has a tendency to make less error per road section than the MCM method. Table5.5: Sample MSE Analysis of TT--MCE and TT--MCM--E

Figure 5 . 22 :Figure 5 . 23 :

 522523 Figure 5.22: Example of %MSE vs Road sections with error problemTo understand the source of this issue illustrated in figure5.22. We will show the speed data that we have in our historical database and it's importance per road section. This action will give us the impact on the probability density function of travel time per road section because we use the speed information to extract it.

Figure 5 . 24 :

 524 Figure 5.24: Number of processed Data vs running time 5.5.4 ConclusionThe results collected in this thesis work regarding the travel time estimation using the Monte Carlo Methods with an enhancement gave interesting and encouraging results. In addition, the approach to estimate the travel time is new and of Couse needs more test and enhancement. It is hard to do so, because of the use of sparsely sampled GPS data, which is already challenging. Moreover, filtering the data and the map--matching make the issue more complicated; because the good performance depends also on the good performance of the other components (filtering, map--matching, etc). Plus, to make good estimation we need important amount of data with good quality.5.6 System Platform for project PUMASThe fact that this thesis works was done within a project; the Creation of a friendly graphical interface where we can view all the information of the system was a need. The interface will allow viewing the results in a statistic and cartographic manner. The parameters interface is set by default; however, we are allowed to change the setting of the parameters as it is shown figure5.25. The parameter window contains all the parameters that are used in the system and we can control and change them.

  Figure 5.25: Software Parameter window view The graph representation is using layer in order to have a view of the map. For example figure 5.26 show the PUMAS sections and the PUMAS points on the map.

Figure 5 . 26 :

 526 Figure 5.26: View of the software with PUMAS sections and PUMAS point's layers Through the interface we can view a specific trajectory and we can get all the information regarding the travel time estimation, section ID, speed, etc by clicking on the concerned road section. The figure 5.27 shows an example of a trajectory.

Figure 5 . 27 :

 527 Figure 5.27: Software View with information in the small window on the left about a specific trajectory 5.7 ConclusionTo sum up, in this chapter we presented the results of this thesis work. The chapter dealt with the implementation description, test strategy for each section, evaluation criteria for each proposed method. Each presented results was analyzed and discussed. In general the results obtained concerning the map matching are encouraging. However, there some issue where there is more work to be done; especially regarding the digital map and the GIS information, some of the problems was discussed in that section. For example, the map is not really representing the real world, some road sections are missing or some intersections. We did as we could an update of the digital map in order to reduce the errors. Besides, we tested the travel time estimation results and analyze them. The new approach presented is very interesting and promising. However, the approach depends on other information that we collect from the historical database, which mean we need a good data to get better performance. Finally at the end we presented the GUI developed during this thesis period for viewing the results in friendly way and easy to understand. The global results of this thesis work are a good start for the new approach and as we know there is nothing perfect from the first try. Thus, there some work to be done in the future to make the approach more robust.

  Speed Distribution ................................................................................................................................. 125 5.5 Travel Time Estimation ....................................................................................................................... 127 5.6 System Platform for project PUMAS .............................................................................................. 135 5.7 Conclusion ................................................................................................................................................. 137

	5.4
	8

TABLE 3 .

 3

1: OPERATOR TABLE .................................................................................................................................................. 73

TABLE 3 .2: TIME--DEPENDENT SHORTEST PATH CLASSIFICATION AFTER [86]

 3 ............................................................ 77

TABLE 5 .1: RESULTS SUMMARY OF THE MAP

 5

--MATCHING ALGORITHM ............................................................. 123

TABLE 5 .2: THE PERFORMANCE OF SOME EXISTING MAP MATCHING ALGORITHMS AND OURS

 5

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

[START_REF] Dougherty | A Review of Neural Networks Applied to Transport[END_REF]

TABLE 5 .3: SAMPLE OF THE PERCENTAGE DIFFERENCE ERROR OF

 5

TT--MCM TABLE ....................................... 129

TABLE 5 .4: SAMPLE OF THE PERCENTAGE DIFFERENCE ERROR OF

 5

THE TT--MCM--E TABLE ............................ 130

TABLE 5 .5: SAMPLE MSE ANALYSIS OF TT--MCE AND

 5

TT--MCM--E ................................................................... 132

TABLE 5 .6: MINIMUM AND MAXIMUM MS ERROR PER ROAD SECTIONS

 5

............................................................... 133 Chapter 1: Introduction 1.1 General view and Background

Table 3 . 1: Operator Table True True True True The

 3 table above shows the condition when the intersection rule should be true.

  : c 1 .cape ! c 2 .cape ! c 3 .cape ! ... ! c n .cape P : s 1 .cape ! s 2 .cape ! s 3 .cape ! ... ! s n .cape

	Correction Step
	This process of correction aims to change the concerned position	by a
	predicted position	knowing and	. Many researches have been done

T

Table 3 .2: Time--dependent Shortest Path Classification after [86]

 3

	Characteristic	Variants
	Network properties	• FIFO network
		• Periodic network: cost and delay follow a
		periodic patterns
		• Zero delay arcs: no delay taken into
		consideration
	Waiting cost	• With memory: waiting cost depends on
		waiting period
		• Without memory: cost is independent from
		waiting time
	Waiting constraints	• Forbidden waiting
		• Allowed waiting
		• Bounded waiting: waiting allowed but
		bounded.

Table 5 .2: The performance of some existing map matching algorithms and ours Map Matching algorithms Navigation Sensors Test Environments

 5

	Matched
	Correctly

Table 5 .3: Sample of the Percentage Difference Error of TT--MCM Table Section ID %Difference Error TT--MCM

 5

	18	20
	19	0
	20	0
	23	8.10
	26	24.11
	82	5.88
	83	33.33

Table 5 .6: minimum and maximum MS Error per road sections Methods MS Error (TP--MCM) MS Error (TP--MCM--E) min

 5

		0%	0%
	max	97%	34%
	5.5

.3.3.3 Discussion of MSE Analysis

  By checking the average MSE and PCTMSE in table 5.5 and figure

  • Amnir Hadachi, Christele Lecomte, Stephane Mousset and Abdelaziz Bensrhair,"An Application of the Sequential Monte Carlo to Increase the Accuracy of Travel Time Estimation in Urban Areas", 14th International IEEE Conference on Intelligent Transportation Systems, Washington, DC, USA. October 5--7, 2011. • Amnir HADACHI, Stéphane MOUSSET, Abdelaziz BENSRHAIR, "Practical Testing Application of Travel Time Estimation Using Applied Monte Carlo Method and Adaptive Estimation from Probes", IEEE INTELLIGENT VEHICLES SYMPOSIUM, Alcalá de Henares, Spain, June 3--7, 2012. • Amnir Hadachi, Stephane Mousset, Christele Lecomte and Abdelaziz Bensrhair," Travel Time Estimation Using Cooperative Probe Vehicles", The 6th International Symposium on signal, Image, Video and Communications, Valenciennes, France on July 4--6, 2012. • Amnir Hadachi, Stephane Mousset, Abdelaziz Bensrhair, "Increasing the Travel Time Accuracy in Urban Arterial Networks using Particle Filter and Enhanced Map Matching." Submitted to the IEEE ITS Transactions Journal 2012.

& & &

& & &

Acknowledgments

support, patience, and guidance over the thesis period.

The following graph (Figure 3.3) shows the extraction process and building of the new digital map with the added characteristics (illustration figure 3.4).

Figure 3.3: Extraction & Enhancement Process

First step is to import the Open Street Map data using "PgRouting" protocol, which allows as the extract the nodes and road sections. With these data we can constitute the digital map. Then at the level of our server using "PostGreSQL" and "PostGIS" queries we launch what we call PUMAS kits that allows adding the new characteristics (PUMAS points, PUMAS sections, PUMAS zones) to the extracted digital map. PgRouyting and PostGreSql are packages containing all the functions that we can use to create a routing database; Load routing data, Import satellite images, or add information to the map. Moreover, it contains also the database server features in order to run and maintain the GIS information and the digital map data. (3.15) Thus the shortest path problem will be as follows (equation 3.16):

The representation above illustrates one unit of data with the requirement that the unit reaches the destination passing the arcs (i,j) at minimum total cost. The fact that SSP is a linear program, then all the solution is solvable. Thus it is easy to add the time dependence aspect to our formula (equation 3.16) by introducing extra variable t v , which is the time of arrival at node v. The tool created using OSM--PgRouting allow us to import from the XML file all the tags that we need such as the node points and tag way, corresponding to the sections, the number of lanes on a section, the section is that a way or not (road section orientation) and the speed limit. These attributes are essential because later we used them in the map--matching process and the calculation of the shortest paths and calculation of travel time estimation per road section. Moreover, the calculation of the shortest path at the level of database context is done during the process of creating the map with its GIS information. The following figure 5.2 shows the classes implemented in order to do this task.

Another problem that we detected due to the road section orientation is illustrated in figure 5.13. The figure shows in red the road that was chosen by the mapping as the trajectory of the probe. But, it is not the right path and the right one is in green, which the system should have chosen.

Figure 5.13: Orientation problem in the matching process In order to reduce the rejected data due to the problem discussed above and also the wrong matching we will add the orientation aspect and a correction step to the algorithm (STC--Matching) as it was described in chapter 3.

STC--Matching

Results

The result illustrated in the figure 5.14 show the final result of the algorithm proposed in this section. We succeed to make the matching process better. We have to take into consideration that some of the problem are due to the digital map missing data.

Analysis

The results obtained are satisfying to continue in our work for the next step of estimating the travel time. Of course there is always more enhancement that we can do. Besides, the 2% of wrong matching is not that significant compared to the amount of data used, which will not affect our results.

Conclusion

After we tested the Map--matching algorithm proposed in this thesis. The outputs show good results and encouraging. The table 5.1 resumes all the results regarding all the algorithms approaches regarding the map matching process. During the testing process we found out that the good functioning of the map-matching algorithm depends not only on the robustness of the algorithm but also on other factor such as a good GIS digital map and a good extraction algorithm.

Analysis

Based on the results the bimodal distribution is the closed probability distribution that can describe the speed distribution in reality. Thus, our hypothesis is confirmed.

Travel Time Estimation

In this section we will conduct our test regarding the two approaches that we presented in chapter 4. First we will present the results of the travel time estimation using Monte Carlo Method (TT--MCM). Next we will show the results of the travel time estimation based on the Monte Carlo Method enhanced with measurements and road section's characteristics (TT--MCM--E).

Description and Implementation

In order to run the process and get the travel time estimation per road section. The function that estimates the travel time has to call another function that compute the estimation of the moment of passage through the PUMAS points.

The moment of passage is computed using two different methods (TT--MCM and TT--MCM--E). The TT--MCM approach uses the distance function and the shortest path function (TDSPP_Calculator). Concerning the TT--MCM--E approach needs the same functions as TT--MCM plus the road section's distribution function that is used in the process. The function road section characteristics uses the speed data saved in the historical database in order to create the travel time distributions for each road section. The figure 5.18 shows the top--down analysis of the implementation. Test Data: In order to make our test we used the GPS data (one second frequency) that was described and used for the map--matching test. The same data collected from the experiment described in chapter 2.

Evaluation Approach

Ground Truth: we simulated our historical data using the same data used for the map--matching test. As it was explained before, we changed the receiving frequency of GPS information from one second to one minute. This yielded data similar to our historical database, but with the advantage of the travel time reference collected from the real--world field. The real world reference data will allow us to validate our results coming from the two estimation methods. Evaluation Criteria: to evaluate the two methods, we will check the running time and the estimation errors. The running time is measured by the actual program execution time. The estimation errors is measured using the percentage difference error metric defined as follows: Baseline: to present the results we will process each method alone. In addition we will discuss the results of each method.

Experimental Results

Travel time estimation based on Monte Carlo method (TT--MCM)