Le map matching est l'étape sans gloire mais essentielle qui transforme un nuage de points GPS bruités en un chemin propre le long de vraies routes. Sans lui, un dashboard de flotte montre des camions qui traversent des bâtiments, un modèle de tarification d'assurance ne sait pas distinguer une autoroute d'une rue secondaire, et une course VTC ressemble au plan de vol d'un pigeon ivre. Avec lui, chaque point devient une position sur un segment connu du graphe routier, avec le sens de circulation et la distance le long de l'arête attachés.
Ce guide explique ce qu'est réellement le map matching, pourquoi le GPS brut ne suffit pas, comment fonctionnent les algorithmes et où il apparaît dans les systèmes de production.
Ce qu'est vraiment le map matching
Dans sa forme la plus simple, le map matching prend deux entrées : une séquence ordonnée dans le temps de relevés GPS (latitude, longitude, horodatage, souvent vitesse et cap) et un réseau routier routable (typiquement OpenStreetMap, traité en un graphe d'arêtes et de nœuds). Il produit une sortie où chaque relevé est recalé sur une arête spécifique de ce graphe, avec une position précise le long de l'arête et les métadonnées du segment attachées.
Le résultat est une polyligne qui suit de vraies rues, plus une liste des segments routiers réellement parcourus. Cette deuxième sortie est ce qui débloque les analytics en aval : limites de vitesse par segment, classe de route, comptage de virages, attribution pays et région, et distance exacte par arête plutôt qu'une distance à vol d'oiseau entre relevés.
Une trace seule vous dit grossièrement où un appareil est allé. Une trace recalée vous dit quelles routes il a empruntées.
Pourquoi le GPS brut ne suffit pas
Le GPS grand public est précis à environ 5 mètres dans de bonnes conditions et 10 à 30 mètres sur un téléphone ou un tracker bas de gamme en usage normal. Trois problèmes structurels aggravent cela en télémétrie de production.
Canyons urbains. Dans les centres-villes denses, les immeubles élevés bloquent la vue directe des satellites et reflètent les signaux sur les façades vitrées. Le récepteur voit une copie retardée du signal (multitrajets) et calcule une position qui peut se retrouver à un pâté de maisons entier de l'emplacement réel, souvent sur une rue parallèle.
Dérive au démarrage à froid. Quand un appareil s'allume, il peut lui falloir 30 à 90 secondes pour acquérir suffisamment de satellites pour un relevé fiable. Les premiers points d'une trace sont souvent décalés de 50 mètres ou plus, ce qui est précisément le moment où un véhicule sort d'une place de parking ou d'un dépôt.
Échantillonnage clairsemé. Les trackers IoT sur batterie enregistrent souvent un relevé toutes les 30 secondes ou toutes les minutes pour économiser l'énergie. À vitesse autoroutière, cela représente plus d'un kilomètre entre points, et la ligne droite entre eux correspond rarement à l'itinéraire réel. Un matcher doit combler le trou en routant à travers le graphe, pas en traçant une ligne.
Cumulés, ces erreurs font que tout système qui prend les relevés bruts pour la vérité produira silencieusement des distances fausses, des routes fausses et une facturation fausse.
Comment fonctionne le map matching
L'approche dominante en production est la formulation par modèle de Markov caché popularisée par Newson et Krumm en 2009. Le graphe routier est modélisé comme un ensemble d'états cachés (sur quelle arête l'appareil se trouve réellement) et la trace GPS comme des observations bruitées de ces états. Deux probabilités pilotent le matcher.
Probabilité d'émission. Pour chaque relevé, l'algorithme trouve les arêtes candidates dans un rayon de recherche (typiquement 25 à 200 mètres) et note chacune par la plausibilité que la position vraie soit sur cette arête compte tenu du relevé observé. Le score est généralement une gaussienne sur la distance perpendiculaire entre le relevé et l'arête.
Probabilité de transition. Pour chaque paire de relevés consécutifs, l'algorithme note chaque paire d'arêtes candidates par la plausibilité de passer de la première à la seconde dans le temps écoulé. Cela nécessite de router à travers le graphe entre les candidats et de comparer la distance routière à la distance orthodromique entre relevés. Les écarts sont pénalisés, donc les sauts impossibles (à travers un fleuve, à contresens d'un sens unique, à des vitesses incompatibles avec la classe de route) sont écrasés.
L'algorithme de Viterbi trouve ensuite la séquence d'arêtes la plus probable sur l'ensemble de la trace en une seule passe. OSRM et Valhalla embarquent tous deux des matchers HMM de production basés sur cette approche, avec des extensions pour les traces clairsemées, les écarts temporels et les points de rupture où l'appareil a quitté le réseau.
Où apparaît le map matching
Le map matching est une capacité d'arrière-boutique qui n'a presque jamais d'UI, mais c'est la salle des machines derrière une longue liste de produits.
- Télémétrie de flotte. Les flottes de camions et de fourgons enregistrent un relevé toutes les quelques secondes. Le map matching convertit le flux en kilométrage par segment, par chauffeur, par véhicule et par région, ce qui alimente la paie, le rapprochement carburant et la conformité des tournées.
- Analytics de comportement de conduite. Les événements de freinage brusque et d'excès de vitesse n'ont de sens que si vous connaissez la limite de vitesse du segment sur lequel le chauffeur se trouvait. Cela exige l'arête recalée, pas seulement le relevé brut.
- Reconstruction de courses VTC. Quand un passager conteste une course, la plateforme reconstruit la course à partir du log GPS du chauffeur. Une trace recalée donne une polyligne de qualité audit le long de vraies rues et une distance défendable.
- Assurance au trajet. Les polices au kilomètre et basées sur le comportement ont besoin d'un kilométrage par trajet précis et d'une exposition par classe de route. Une erreur de 5 % sur le GPS brut, c'est la différence entre profit et perte sur tout un portefeuille.
- Suivi d'actifs IoT. Conteneurs de fret, trottinettes électriques et matériel de location envoient des relevés clairsemés. Le map matching les coud en trajets avec des distances correctes, même quand les relevés sont espacés de plusieurs minutes.
- Analytics d'usage routier. Les autorités urbaines et de péage utilisent les traces recalées pour estimer le flux, identifier les segments congestionnés et étudier la part modale sans installer de capteurs physiques.
Pièges en production
Le map matching paraît propre en démo et devient laid sous la charge réelle.
Traces clairsemées. Quand les relevés sont espacés de plus d'un kilomètre, le matcher doit s'engager sur un seul itinéraire entre eux. Si deux itinéraires raisonnables existent, le mauvais l'emportera de temps en temps. Augmenter la fenêtre de candidats aide, mais fait exploser le temps d'exécution.
Segments hors réseau. Les véhicules quittent régulièrement le réseau : parkings, routes privées, ferries, chemins de gravier. Un matcher naïf forcera ces points sur la route la plus proche et produira un kilométrage fantôme. Les matchers de production détectent les points de rupture et émettent des trous non recalés plutôt que de deviner.
Routes parallèles. Autoroute plus voie de service, route à chaussées séparées et grilles urbaines denses produisent toutes des candidats qui obtiennent des scores presque équivalents. Les signaux de cap et de vitesse (quand ils sont disponibles) sont ce qui départage.
Couture sur plusieurs jours. Un véhicule garé pour la nuit produit deux trajets distincts, pas une trace avec un trou de 12 heures. Découper l'entrée en trajets avant le matching est généralement plus rapide et plus précis qu'une seule grosse passe Viterbi.
Vie privée. Une trace recalée est un enregistrement à haute résolution de l'endroit où une personne se trouvait et quand. Ce sont des données personnelles au sens du GDPR et des régimes équivalents. Le stockage, la rétention et les logs d'accès doivent correspondre à la sensibilité, et l'agrégation devrait avoir lieu le plus tôt possible dans le pipeline.
Le map matching dans MapAtlas
L'API Map Matching de MapAtlas prend une séquence de relevés GPS et renvoie une polyligne recalée sur le réseau routier, avec des identifiants d'arête par point, des métadonnées de segment et un score de confiance sur chaque correspondance. Elle gère les traces clairsemées, la détection des points de rupture pour les segments hors réseau, et les cas de production courants (télémétrie de flotte, reconstruction de course, suivi IoT) sans vous obliger à héberger votre propre cluster OSRM ou Valhalla.
Elle s'associe naturellement à l'API Directions de MapAtlas quand vous avez besoin de comparer une tournée historique recalée à une tournée optimale, et à l'API Geocoding de MapAtlas quand vous devez convertir le début et la fin d'un trajet recalé en adresses lisibles pour un dashboard ou un reçu client.
Une trace recalée n'a rien de tape-à-l'œil. Ce n'est qu'une polyligne. Mais c'est la polyligne qui permet à chaque système en aval, de la facturation aux analytics à la conformité, de s'accorder sur la route où l'appareil se trouvait réellement.
Questions fréquemment posées
Qu'est-ce que le map matching ?
Le map matching est le processus qui consiste à prendre une séquence de points GPS bruités et à les aligner sur le réseau routier sous-jacent, de sorte que chaque relevé devienne une position sur un véritable segment de rue. Au lieu d'un nuage de points qui dérive à travers les bâtiments et les fleuves, vous obtenez une polyligne propre qui suit de vraies routes, avec l'identifiant du segment, le sens de circulation et la distance le long de chaque arête attachés à chaque point.
Pourquoi ne peut-on pas simplement afficher les points GPS bruts sur une carte ?
Le GPS brut est précis à environ 5 à 30 mètres en ciel dégagé, et bien pire dans les canyons urbains, les tunnels et les parkings. Les réflexions multitrajets sur les immeubles élevés, la dérive au démarrage à froid et les fréquences d'échantillonnage aussi basses qu'un relevé toutes les 30 secondes font que la trace se retrouve fréquemment hors de la route, saute entre des rues parallèles ou rate complètement des virages. Le map matching corrige ces trois problèmes en raisonnant sur le graphe routier au lieu de faire confiance à chaque relevé isolément.
Comment fonctionne le map matching par modèle de Markov caché ?
Un HMM traite le vrai segment de route à chaque pas de temps comme un état caché et le relevé GPS comme une observation bruitée de cet état. Chaque arête candidate proche d'un relevé reçoit une probabilité d'émission basée sur la distance, et chaque paire de candidats consécutifs reçoit une probabilité de transition basée sur la possibilité que le réseau routier autorise réellement ce déplacement à la vitesse observée. L'algorithme de Viterbi parcourt ensuite la trace et choisit la séquence d'arêtes la plus probable. OSRM et Valhalla embarquent tous deux des matchers HMM de production basés sur cette approche.
À quoi sert le map matching en production ?
Télémétrie de flotte, analytics de comportement de conduite, reconstruction de courses VTC, assurance basée sur l'usage et au trajet, suivi d'actifs IoT, et analytics d'usage routier dépendent tous du map matching. Partout où vous avez un flux de pings GPS et où vous avez besoin de savoir sur quelle route l'appareil se trouvait, quelle distance il a parcourue et quels virages il a pris, le map matching est l'étape qui convertit des points bruts en quelque chose qu'un système de facturation, un moteur de routage ou un dashboard peut exploiter.
