L'éco-routage est une méthode de navigation du véhicule qui sélectionne les trajets vers une destination minimisant la consommation de carburant, la consommation d'énergie ou les émissions de polluants. C'est l'une des techniques qui tentent de réduire les coûts d'exploitation et l'empreinte environnementale du véhicule. Ce travail passe en revue les méthodes actuelles d'éco-routage et propose une nouvelle méthode pour pallier leurs insuffisances. La plupart des méthodes actuelles attribuent à chaque route du réseau routier un coût constant qui représente la consommation du véhicule ou la quantité de polluants émis. Un algorithme de routage optimal est ensuite utilisé pour trouver le chemin qui minimise la somme de ces coûts. Différentes extensions sont considérées dans la littérature. L'éco-routage contraint permet d'imposer des limites sur le temps de trajet, la consommation d'énergie et les émissions de polluants. L'éco-routage dépendant du temps permet le routage sur un graphique avec des coûts qui sont fonction du temps. L'éco-routage adaptatif permet de mettre à jour la solution d'éco-routage au cas où elle deviendrait invalide en raison d'un développement inattendu sur la route. Il existe des méthodes d'éco-routage optimales publiées qui résolvent l'éco-routage dépendant du temps ou l'éco-routage contraint ou l'éco-routage adaptatif. Chacun vient avec des frais généraux de calcul considérablement plus élevés par rapport à l'éco-routage standard et, à la connaissance de l'auteur, aucune méthode publiée ne prend en charge la combinaison des trois: éco-routage adaptatif dépendant du temps contraint. On soutient dans ce travail que les coûts d'acheminement sont incertains en raison de leur dépendance au trafic immédiat autour du véhicule, du comportement du conducteur et d'autres perturbations. Il est en outre soutenu que puisque ces coûts sont incertains, il y a peu d'avantages à utiliser un routage optimal car l'optimalité de la solution ne tient que tant que les coûts de routage sont corrects. Au lieu de cela, une méthode d'approximation est proposée dans ce travail. La charge de calcul est plus faible car la solution n'est pas requise pour être optimale. Cela permet l'éco-routage adaptatif dépendant du temps contraint. / Eco-routing is a vehicle navigation method that selects those paths to a destination that minimize fuel consumption, energy consumption or pollutant emissions. It is one of the techniques that attempt to lower vehicle's operational cost and environmental footprint. This work reviews the current eco-routing methods and proposes a new method designed to overcome their shortcomings. Most current methods assign every road in the road network some constant cost that represents either vehicle's consumption there or the amount of emitted pollutants. An optimal routing algorithm is then used to find the path that minimizes the sum of these costs. Various extensions are considered in the literature. Constrained eco-routing allows imposing limits on travel time, energy consumption, and pollutant emissions. Time-dependent eco-routing allows routing on a graph with costs that are functions of time. Adaptive eco-routing allows updating the eco-routing solution in case it becomes invalid due to some unexpected development on the road. There exist published optimal eco-routing methods that solve either the time-dependent eco-routing, or constrained eco-routing, or adaptive eco-routing. Each comes with considerably higher computational overhead with respect to the standard eco-routing and, to author's best knowledge, no published method supports the combination of all three: constrained time-dependent adaptive eco-routing. It is argued in this work that the routing costs are uncertain because of their dependence on immediate traffic around the vehicle, on driver's behavior, and other perturbations. It is further argued that since these costs are uncertain, there is little benefit in using optimal routing because the optimality of the solution holds only as long as the routing costs are correct. Instead, an approximation method is proposed in this work. The computational overhead is lower since the solution is not required to be optimal. This enables the constrained time-dependent adaptive eco-routing.

Satellite positioning measurements are never perfectly unbiased. Due to multiple types of errors affecting the signal transmission through an open space and urban areas each positioning measurement contains certain degree of uncertainty. Satellite signal receivers also do not receive the signal continuously, but the localization information is received discretely. Sampling rate and positioning error provide uncertainty towards the various positioning algorithms used in localization, logistics and in intelligent transport systems applications. This thesis examines the effect of positioning error and sampling rate on geometric and topological map matching algorithms and on the precision of route tracking within these algorithms. Also the effects of the different network density on the performance of the algorithms are evaluated. It also creates the platform for simulation and evaluation of map matching algorithms. Map matching is the process of attaching the initial positioning measurement to the network. A number of authors presented their algorithms during past decades, which shows how complex topic the map matching is, mostly due to the changing environmental and network conditions. Geometric and topological map matching algorithms are chosen, modelled and simulated and their response to the different input combinations is evaluated. Also the recommendations for possible ITS applications are carried out in terms of proposed requirements of the receiver. The results confirm general expectation that the map matching overall improves the initial position error and that map matching serves as a form of error mitigation. Also the correlation between the increase of the original positioning error and the increase of the map matching error is universal for all the algorithms in the thesis. But the comparison of the algorithm also showed large differences between the topological and geometric algorithms and their ability to cope with distorted input data. Whereas topological algorithms were clearly performing better in scenarios with smaller initial error and smaller sampling rate, geometric matching proves to be more effective in heavily distorted or very sparsely sampled data set. That is caused mostly by the ability to easily leave the wrongly mapped position which is in these situations comparative advantage of simple geometric algorithms. Following work should concentrate on involving even more algorithms into the comparison, which would produce more valuable results. Also the simulation  of the errors using the error magnitude simulation with known an improved error modelling could increase the generalization of the results.

Cette thèse présente la fusion multi-capteurs par un réseau Bayésien appliqué au problème de localisation d'un véhicule sur une carte. La mise en correspondance d'une estimation sur un segment de route ou Road-matching consiste à trouver le segment sur lequel le véhicule roule et la position de ce véhicule sur ce segment. Plusieurs algorithmes utilisent la fusion des estimations données par l'odométrie et le GPS pour traiter le problème du road-matching. Cependant, une simple combinaison du GPS et de l'odométrie ne permet pas de se localiser de manière précise et sans interruption de service. La précision et la continuité de service peuvent être améliorées si on utilise des informations cartographiques qui permettent en particulier de contraindre les positions possibles aux seuls segments correspondants à des voies de circulation autorisées.\\ Dans de nombreux cas, lorsqu'un véhicule se trouve devant des situations ambiguës comme les routes parallèles, les jonctions de routes,... plusieurs auteurs cherchent à sélectionner le segment le plus probable. Cette phase est souvent une source d'erreurs. Dans cette thèse nous proposons de traiter tous les segments candidats jusqu'à la levée de l'ambiguïté. \\ Le problème de la localisation devient encore plus compliqué quand il s'agit d'une localisation multi-véhicules pour une navigation autonome des véhicules suiveurs. Pour un train de véhicules dont seul le premier est piloté par un opérateur humain et dont les véhicules suiveurs sont en mode autopilotage, une géo-localisation précise d'ordre centimétrique de chaque véhicule est plus que nécessaire pour les modules de contrôle pour le suivi de trajectoire du véhicule de tête. \\ Un train de véhicule peut être vu comme la généralisation du modèle de réseau Bayésien pour la localisation d'un véhicule sur une carte. Nous dupliquons le réseau autant de fois qu'on a de véhicule. Nous rajoutons des liens de connexions entre les véhicules afin de concevoir le train de véhicule.\\ Le filtre de Kalman et sa version étendue sont très utilisés en robotique, principalement pour traiter le problème de la non linéarité. Cependant, la linéarisation du système autour de l'estimée courante peut introduire des erreurs sur la moyenne et la covariance calculées \textit{a posteriori} et peut même dans d'autres cas faire diverger le filtre. \\ La transformation du système non linéaire d'un véhicule sous forme chaînée permet de représenter son équation cinématique sous forme linéaire. Par conséquent, cette transformation nous évite de faire appel aux méthodes d'inférence approximatives.

abstract: A volunteered geographic information system, e.g., OpenStreetMap (OSM), collects data from volunteers to generate geospatial maps. To keep the map consistent, volunteers are expected to perform the tedious task of updating the underlying geospatial data at regular intervals. Such a map curation step takes time and considerable human effort. In this thesis, we propose a framework that improves the process of updating geospatial maps by automatically identifying road changes from user-generated GPS traces. Since GPS traces can be sparse and noisy, the proposed framework validates the map changes with the users before propagating them to a publishable version of the map. The proposed framework achieves up to four times faster map matching performance than the state-of-the-art algorithms with only 0.1-0.3% accuracy loss. / Dissertation/Thesis / Masters Thesis Computer Science 2017

In this thesis the Hidden Markov Model (HMM) is used in the process of map matching to investigate the accuracy for road segment map matching. A few HMM algorithms using a Global Navigation Satellite System (GNSS) receiver, odometer and gyroscope sensors are presented. The HMM algorithms are evaluated on four accuracy metrics. Two of these metrics have been seen in previous literature and captures road map match accuracy. The other have not been seen before and captures road segment accuracy. In the evaluation process a dataset is created by simulation to achieve positional ground truth for each sensor measurement. The accuracy distribution for different parts of the map matched trajectory is also evaluated. The result shows that HMM algorithms presented in previous literature, falls short to capture the accuracy for road segment map matching. The results further shows that by using less noisy sensors, as odometer and gyroscope, the accuracy for road segment map matching can be increased.

Les informations contenues dans les cartes routières numériques revêtent une importance grandissante dans le domaine des véhicules intelligents. La prise en compte d’environnements de plus en plus complexes a augmenté le niveau de précision exigé des informations cartographiques. Les cartes routières numériques, considérées ici comme des bases de données géographiques, contiennent des informations contextuelles sur le réseau routier, facilitant la compréhension correcte de l’environnement. En les combinant avec les données provenant des capteurs embarqués, une représentation plus fine de l’environnement peut être obtenue, améliorant grandement la compréhension de contexte du véhicule et la prise de décision. La performance des différents capteurs peut varier grandement en fonction du lieu considéré, ceci étant principalement dû à des facteurs environnementaux. Au contraire, une carte peut fournir ses informations de manière fiable, sans être affectée par ces éléments extérieurs, mais pour cela, elle doit reposer sur un autre élément essentiel : une source de localisation. Le secteur automobile utilise les systèmes de localisation globale par satellite (GNSS) à des fins de localisation absolue, mais cette solution n’est pas parfaite, étant soumise à différentes sources d’erreur. Ces erreurs sont elles aussi dépendantes de l’environnent d’évolution du véhicule (par exemple, des multi-trajets causés par des bâtiments). Nous sommes donc en présence de deux systèmes centraux, dont les performances sont d´dépendantes du lieu considéré. Cette étude se focalise sur leur dénominateur commun : la carte routière numérique, et son utilisation en tant qu’outil d’évaluation de leur performance. L’idée développée durant cette thèse est d’utiliser la carte en tant que canevas d’apprentissage, pour stocker des informations géoréférencées sur la performance des diésèrent capteurs équipant le véhicule, au cours de trajets répétitifs. Pour cela, une localisation robuste, relative à la carte, est nécessaire au travers d’une méthode de map-matching. La problématique principale réside dans la différence de précision entre la carte et le positionnement GNSS, créant des situations ambigües. Durant cette thèse, un algorithme de map-matching a été conçu pour gérer ces ambigüités en fournissant des hypothèses multiples lorsque nécessaire. L’objectif est d’assurer l’intégrité de l’algorithme en retournant un ensemble d’hypothèses contenant l’hypothèse correcte avec une grande probabilité. Cet algorithme utilise les capteurs proprioceptifs dans une approche de navigation à l’estime aidée d’informations cartographiques. Une procédure d’évaluation de cohérence, utilisant le GNSS comme information redondante de positionnement est ensuite appliquée, visant à isoler une hypothèse cohérente unique qui pourra ainsi être utilisée avec confiance dans le processus d’écriture dans la carte. L’utilisation de la carte numérique en écriture/lecture a été évaluée et la procédure complète d’écriture a été testée sur des données réelles, enregistrées par des véhicules expérimentaux sur route ouverte. / The information stored in digital road maps has become very important for intelligent vehicles. As intelligent vehicles address more complex environments, the accuracy requirements for this information have increased. Regarded as a geographic database, digital road maps contain contextual information about the road network, crucial for a good understanding of the environment. When combined with data acquired from on-board sensors, a better representation of the environment can be made, improving the vehicle’s situation understanding. Sensors performance can vary drastically depending on the location of the vehicle, mainly due to environmental factors. Comparatively, a map can provide prior information more reliably but to do so, it depends on another essential component: a localization system. Global Navigation Satellite Systems (GNSS) are commonly used in automotive to provide an absolute positioning of the vehicle, but its accuracy is not perfect: GNSS are prone to errors, also depending greatly on the environment (e.g., multipaths). Perception and localization systems are two important components of an intelligent vehicle whose performances vary in function of the vehicle location. This research focuses on their common denominator, the digital road map, and its use as a tool to assess their performance. The idea developed during this thesis is to use the map as a learning canvas, to store georeferenced information about the performance of the sensors during repetitive travels. This requires a robust localization with respect to the map to be available, through a process of map-matching. The main problematic is the discrepancy between the accuracy of the map and of the GNSS, creating ambiguous situations. This thesis develops a map-matching algorithm designed to cope with these ambiguities by providing multiple hypotheses when necessary. The objective is to ensure the integrity of the result by returning a hypothesis set containing the correct matching with high probability. The method relies on proprioceptive sensors via a dead-reckoning approach aided by the map. A coherence checking procedure using GNSS redundant information is then applied to isolate a single map-matching result that can be used to write learning data with confidence in the map. The possibility to handle the digital map in read/write operation has been assessed and the whole writing procedure has been tested on data recorded by test vehicles on open roads.

La navigation dans les environnements contraints tels que les zones portuaires ou les zones urbainesdenses est souvent exposée au problème du masquage des satellites GPS. Dans ce cas, le recours auxcapteurs proprioceptifs est généralement la solution envisagée pour localiser temporairement le véhiculesur une carte. Cependant, la dérive de ces capteurs met rapidement en défaut le système de navigation.Pour localiser le véhicule, on utilise dans cette thèse, un magnétomètre pour la mesure du cap dans unrepère absolu, un capteur de vitesse et une carte numérique du réseau de routes.Dans ce contexte, le premier apport de ce travail est de proposer la mise en correspondance desmesures de cap avec la carte numérique (map matching) pour localiser le véhicule. La technique proposéefait appel à un filtre particulaire défini dans le domaine circulaire et à un préfiltrage circulairedes mesures de cap. On montre que cette technique est plus performante qu’un algorithme de map matchingtopologique classique et notamment dans le cas problématique d’une jonction de route en Y. Ledeuxième apport de ce travail est de proposer un filtre circulaire multi-modèles CIMM défini dans uncadre bayésien à partir de la distribution circulaire de von Mises. On montre que l’intégration de cettenouvelle approche dans le préfiltrage et l’analyse des mesures de cap permet d’améliorer la robustesse del’estimation de la direction pendant les virages ainsi que d’augmenter la qualité du map matching grâce àune meilleure propagation des particules du filtre sur le réseau de routes. Les performances des méthodesproposées sont évaluées sur des données synthétiques et réelles. / Navigation in constrained areas such as ports or dense urban environments is often exposed to theproblem of non-line-of-sight to GPS satellites. In this case, proprioceptive sensors are generally used totemporarily localize the vehicle on a map. However, the drift of these sensors quickly cause the navigationsystem to fail. To localize the vehicle, a magnetometer is used in this thesis for heading measurementunder an absolute reference together with a velocity sensor and a digital map of the road network.In this context, the first contribution of this work is to provide a matching of the vehicle’s headingwith the digital map (map matching) to localize the vehicle. The proposed technique uses a particle filterdefined in the circular domain and a circular pre-filtering on the heading measurements. It is shown thatthis technique is more efficient than a conventional topological map matching algorithm, particularly inambiguous cases like a Y-shape road junction. The second contribution of this work is to propose a circularmultiple model filter CIMM defined in a Bayesian framwork from the von Mises circular distribution.It is shown that the integration of this new approach in the pre-filtering and analysis of the heading observationsimproves the robustness of the heading’s estimation during cornering and increases the mapmatching’s quality through a better propagation of the particles on the road network. The performancesof the proposed methods are evaluated on synthetic and real data.

Die zuverlässige Ortung von Fahrgästen und Fahrzeugen bildet die Grundlage für Anwendungen im Öffentlichen Personenverkehr (ÖPV) im Rahmen intelligenter Verkehrssysteme. Unter den gegebenen Systembedingungen stoßen funkbasierte Ortungssysteme auf Grund von Abschattungen oder Mehrwegeausbreitungen an ihre Grenzen. Zusätzliche Ortungsinformationen liefern Beschleunigungssensoren. Diese Arbeit entwirft Methoden zur Nutzung dieser Sensorinformationen zur Stützung von Navigationsfunktionen im ÖPV. Ein wesentlicher Gegenstand dieser Arbeit ist der vertiefte Vergleich von theoretisch vorhandenen und praktisch messbaren Fahrzeugsignalen mit den durch die nutzende Person beeinflussten Signalen einer mobilen Sensorplattform (zum Beispiel Smartphone, entsprechend ausgestattetes Nutzermedium). Darauf aufbauend wird ein neues Verfahren zur Schätzung von Bewegungsmodus (d.h. Verkehrsmittelwahl) und -zustand (detaillierte Bewegungsform, z. B. Kurvenfahrt) entwickelt. Dazu wird ein geschichtetes Bewegungszustandsmodell entworfen, welches die verschiedenen in einer ÖPV-Umgebung zu betrachtenden Bewegungszustände und -modi definiert und miteinander verbindet. Dieses Modell ist Grundlage für den in der Arbeit entwickelten und genutzten Algorithmus zur Bewegungszustandserkennung. Anhand von Beispielmessungen von Fahrzeug- (Dresdner Messstraßenbahn, Bus der DVB AG) und Personenbewegungen wird dieses Vorgehen auf seine Anwendbarkeit hin untersucht. Die erstellten Klassifikatoren werden mit dem in dieser Arbeit entwickelten Ansatz wahrscheinlichkeitsbasierter Güteschranken bewertet. Als Teil der Laborumgebung der Professur „Informationstechnik für Verkehrssysteme“ an der TU Dresden zur originalgetreuen Wiederholung von verkehrstelematischen Messfahrten für Sensor- und Softwaretests wird die Reproduktion von Beschleunigungssignalen umgesetzt und diskutiert. Konkrete Beispiele zur Stützung von Navigationsfunktionen im ÖPV auf Basis von Beschleunigungssignalen werden ebenfalls dargestellt.

I storstadsregionerna blir trafikläget allt mer ansträngt för vart år som går. Inflyttningen fortsätter i oförändrad takt och fler människor måste försöka samsas om samma utrymme. Situationen på vägarna börjar bli ohållbar och det måste till att dessa problem löses snart för att utvecklingen i regionerna inte ska stagnera. Möjligheter för ytterligare utbyignationer finns dock i en begränsad grad och man måste börja se till andra lösningar. Inom området för intelligenta transportsystem(ITS) erbjuds många nya tillämpningar där man med ny teknik försöker hitta lösningar till dagens trafikproblem. Ett led i detta är att samla in och distribuera information om restider på vägarna, för att försöka fördela trafiken mer jämt över hela vägnätet. Det finns olika metoder för att hämta in den här typen av information, men den här rapporten fokuserar sig vid att beskriva system baserat på Floating Car Data(FCD). Arbetet som beskrivs i rapporten har i huvudsak analyserat fyra olika restidsuppskattnings-modeller och jämfört dessa med varandra. Modellerna baserar sina beräkningar på observationer från oidentifierade fordon, dvs att observationerna inte har någon identitetsstämpel som kan kopplas till ett specifikt fordon. Två av modellerna betraktar länkarna som en helhet och utför beräkningarna med detta som grund, medan de två andra delar upp varje länk i mindre segment vilket skapar möjlighet för en större noggrannhet. Modellerna testades inledningsvis på simulerad data baserat på trafikmätningar i Göteborgstrakten. Alla beräkningar begränsades ner till länknivå och inte hela vägnät. Detta p.g.a. att det initialt var för komplicerat att skapa en map- matchingmetod som skulle krävas för genomföra beräkningar på olika länkar samtidigt. Efter genomförda tester på simulerad data prövades modellerna även på en reella datamängd hämtad från projektet Probe i Stockholmsområdet. Resultaten från de utförda testerna visar på att det inte skiljer sig nämnvärt i restidsuppskattningarna mellan de olika modellerna. Sträckan som valdes att analyseras i de simulerade fallen, påverkades inte av några större störningar eller flödesvariationer. Det resulterade i att alla modellerna genererade likvärdiga restider. Även i fallet med den reella datamängden, som innehöll större flödesvariationer över tiden, kunde de olika modellernas uppskattningar inte skiljas åt nämnvärt. Slutsatsen är att trafiken i allmänhet inte har så kraftiga förändringar i flödet över tiden, att det krävs särskilt avancerade modeller för att beräkna restider på länknivå. I alla fall inte om man bortser från incidenter. De framräknade restiderna och den information som dessa ger, bör främst användas för direkt trafikstyrning för att uppnå önskat resultat. Människor förlitar sig mer till sina egna erfarenheter i kända områden, så information av den här typen lämpar sig mer som hjälpmedel för den enskilde individen vid resor i okänd trafik.

<p>I storstadsregionerna blir trafikläget allt mer ansträngt för vart år som går. Inflyttningen fortsätter i oförändrad takt och fler människor måste försöka samsas om samma utrymme. Situationen på vägarna börjar bli ohållbar och det måste till att dessa problem löses snart för att utvecklingen i regionerna inte ska stagnera. Möjligheter för ytterligare utbyignationer finns dock i en begränsad grad och man måste börja se till andra lösningar. Inom området för intelligenta transportsystem(ITS) erbjuds många nya tillämpningar där man med ny teknik försöker hitta lösningar till dagens trafikproblem. Ett led i detta är att samla in och distribuera information om restider på vägarna, för att försöka fördela trafiken mer jämt över hela vägnätet. Det finns olika metoder för att hämta in den här typen av information, men den här rapporten fokuserar sig vid att beskriva system baserat på Floating Car Data(FCD). </p><p>Arbetet som beskrivs i rapporten har i huvudsak analyserat fyra olika restidsuppskattnings-modeller och jämfört dessa med varandra. Modellerna baserar sina beräkningar på observationer från oidentifierade fordon, dvs att observationerna inte har någon identitetsstämpel som kan kopplas till ett specifikt fordon. Två av modellerna betraktar länkarna som en helhet och utför beräkningarna med detta som grund, medan de två andra delar upp varje länk i mindre segment vilket skapar möjlighet för en större noggrannhet. Modellerna testades inledningsvis på simulerad data baserat på trafikmätningar i Göteborgstrakten. Alla beräkningar begränsades ner till länknivå och inte hela vägnät. Detta p.g.a. att det initialt var för komplicerat att skapa en map- matchingmetod som skulle krävas för genomföra beräkningar på olika länkar samtidigt. </p><p>Efter genomförda tester på simulerad data prövades modellerna även på en reella datamängd hämtad från projektet Probe i Stockholmsområdet. Resultaten från de utförda testerna visar på att det inte skiljer sig nämnvärt i restidsuppskattningarna mellan de olika modellerna. Sträckan som valdes att analyseras i de simulerade fallen, påverkades inte av några större störningar eller flödesvariationer. Det resulterade i att alla modellerna genererade likvärdiga restider. Även i fallet med den reella datamängden, som innehöll större flödesvariationer över tiden, kunde de olika modellernas uppskattningar inte skiljas åt nämnvärt. </p><p>Slutsatsen är att trafiken i allmänhet inte har så kraftiga förändringar i flödet över tiden, att det krävs särskilt avancerade modeller för att beräkna restider på länknivå. I alla fall inte om man bortser från incidenter. De framräknade restiderna och den information som dessa ger, bör främst användas för direkt trafikstyrning för att uppnå önskat resultat. Människor förlitar sig mer till sina egna erfarenheter i kända områden, så information av den här typen lämpar sig mer som hjälpmedel för den enskilde individen vid resor i okänd trafik.</p>