La route que votre GPS croit suivre

Un mardi matin de juillet, un téléphone au fond d'une poche de veste a enregistré une voiture qui remontait l'Unter den Linden à Berlin et n'a gardé que trois points : 52.5164, 13.3777 à la porte de Brandebourg ; 52.5170, 13.3900, environ 830 m plus à l'est ; 52.5175, 13.3950, encore 340 m plus loin. Trois points au-dessus de Mitte. Quiconque connaît Berlin peut nommer la rue à partir de cette description. La trace, elle, n'en est pas capable, car une position brute ne transporte que du bruit et rien d'autre, et la rue n'existe dans la réponse que si vous l'y mettez.

Cette opération s'appelle le map matching, et c'est l'étape qui transforme un fil d'Ariane de positions en itinéraire. Réussissez-la et chaque consommateur en aval de la trace cesse de deviner : les estimations de vitesse s'accrochent aux rues, et les rejeux virage par virage deviennent des trajets qu'un véhicule aurait pu faire légalement. Échouez-la et la trace affirmera discrètement une rue que le véhicule n'a jamais touchée. Ce tutoriel fait suivre une trace à travers toute la chaîne, de trois points bruts à une route résolue, et consacre autant de place aux endroits où la chaîne casse.

Trois points incapables de nommer leur propre rue

# the pocket GPS log, exactly as recorded
52.5164,13.3777
52.5170,13.3900
52.5175,13.3950

Placez les trois points, reliez-les par des lignes, et le dessin ressemble à un trajet : environ 830 m de déplacement, puis 340 m de plus, vers l'est en quittant Mitte. Un dessin, c'est tout ce que c'est. Entre les points consignés se cache près d'une minute de conduite que le journal n'a jamais vue, et la ligne qui traverse ce trou est une interpolation, pas le relevé de quoi que ce soit.

En aval, un dessin échoue aux questions que les gens posent réellement à une trace. Sur quelle rue passait ce segment ? Une autorité routière qui compte le trafic rue par rue, ou un coursier payé au kilomètre hors de la ville, a besoin de l'identité de la rue, et une coordonnée n'en transporte aucune. Le véhicule roulait-il vers l'est ? La ligne le suggère ; les données ne l'ont jamais dit. Chaque segment tracé correspondait-il à une conduite légale ? Seul le graphe routier peut répondre, car sur d'autres traces, dans d'autres villes, la ligne dessinée traversera des places et des socles où aucun véhicule n'a le droit de passer, et rien dans les coordonnées ne vous avertira.

La route est un état caché, et la trace est la preuve

Le map matching a un modèle mental limpide, et il vaut mieux le tenir en tête avant de lancer quoi que ce soit. Pour chaque point consigné, listez les routes candidates : les rues situées dans un rayon de quelques dizaines de mètres autour du point, là où il pourrait se trouver de façon plausible une fois le bruit pris en compte. Au premier point, près de la porte de Brandebourg, la liste honnête des candidates compte plusieurs rues : l'Unter den Linden qui file vers l'est, la Straße des 17. Juni qui court vers l'ouest en direction du tunnel du Tiergarten, et la Behrenstraße, un pâté de maisons plus au sud, en parallèle.

Les transitions notent les paires. La paire qui survit est celle où le chemin dans le graphe routier entre deux candidates a une longueur proche de l'écart à vol d'oiseau entre les points observés. Les chaînes qui exigent de se téléporter au-dessus de la Spree ou de faire demi-tour à contresens du graphe obtiennent un mauvais score, et le matcher parcourt toute la séquence d'un coup, en gardant la chaîne de routes candidates qui explique le mieux la trace de bout en bout. Cette idée a une version formelle bien connue : des modèles de Markov cachés décodés par l'algorithme de Viterbi, et chaque plateforme de routage sérieuse que vous utilisez déjà en embarque une variante.

Si le map matching marche du tout, c'est que les routes contraignent le déplacement bien plus étroitement que le bruit GPS ne peut l'étaler. Le bruit se mesure ici en mètres. Les alternatives sont séparées par des rues. Sur notre trace, le second point, à 52.5170, 13.3900, pourrait appartenir à l'Unter den Linden ou à la Dorotheenstraße, un ou deux pâtés plus au nord. Le troisième point continue vers l'est avec la dérive typique du boulevard, et les distances dans le graphe routier ne s'alignent que pour l'une des deux. Un GPS en poche est bien plus bruité que la plupart des gens ne l'imaginent. Ce qui sauve la trace, c'est la sévérité de la géométrie routière, que le matcher lui emprunte.

Faire passer la trace par le matching

everymap --api-key $KEY match-route --trace "52.5164,13.3777;52.5170,13.3900;52.5175,13.3950" --transport car

Cette commande unique est tout le pipeline. La CLI everymap, issue du projet everymap-rs que nous publions sous licence MIT, reçoit la trace, demande des candidates et des transitions au fournisseur, et renvoie le chemin résolu sur le graphe routier. Dans cette exécution, la ligne résolue suit l'Unter den Linden, direction est depuis la Pariser Platz, l'identité de la route étant portée par la géométrie elle-même. Faites un géocodage inversé de la ligne résolue si vous avez besoin du nom de rue comme étiquette à destination des humains.

Soyons honnêtes sur ce qu'est cet exemple, car il s'agit du cas facile. Trois points, bien espacés, déjà posés près du boulevard, avec des alternatives séparées d'un pâté de maisons entier : le matcher gagne parce que la géométrie concorde avec elle-même. L'enregistrement en poche produit bel et bien des trous de ce genre, environ 830 m et 340 m dans ce journal, ce qui veut dire que tout le tronçon entre les points a été de l'inférence. Cela a marché parce que les routes sont éloignées. Les échecs commencent exactement là où les alternatives sont proches.

Le matching perd exactement là où les routes se rapprochent

Là où une route court en deux moitiés à sens unique séparées de quelques mètres, les deux moitiés figurent dans la liste des candidates avec des scores presque identiques. Le matcher en choisit une, et chaque franchissement de médiane par la trace peut retourner le verdict : la liste de virages reconstruite fait alors pousser des demi-tours que le chauffeur n'a jamais faits.

Les voies de desserte et les bretelles d'autoroute dupliquent la géométrie de la chaussée qu'elles desservent. Une trace échantillonnée toutes les quelques secondes ne peut pas distinguer de manière fiable un accotement d'une bretelle, et le matcher, servi avec des candidates aussi proches, reporte parfois la bretelle.

Dans un quadrillage dense, un pâté de Manhattan ou de Kreuzberg, un seul point a une douzaine de candidates à distance quasi égale, et le bruit de cap fait basculer la correspondance de rue en rue. L'échec ressemble à un conducteur glissant de côté à travers le damier urbain plutôt qu'à obéir aux carrefours.

Les tunnels méritent leur propre paragraphe. À l'ouest de la porte de Brandebourg, le tunnel du Tiergarten fait passer la route sous le parc et avale le récepteur pendant plus d'un kilomètre. La trace se tait, puis réapparaît de l'autre côté. Sur ce trou, le matcher doit choisir entre la route du tunnel, qui est presque certainement là où se trouvait le véhicule, et le réseau de surface, qui offre de nombreuses chaînes candidates plausibles pour le même déplacement. L'itinéraire de surface peut gagner au score brut, parce qu'il n'est bâti qu'avec de vraies routes tandis que le tunnel n'apporte qu'une supposition sûre d'elle à chaque extrémité. La sortie honnête, ici, c'est « très probablement le tunnel, avec une faible confiance », et tous les moteurs ne proposent pas la moitié faible-confiance.

Travailler avec le matcher plutôt que contre lui

Échantillonnez plus vite que votre mode de défaillance. Un point toutes les quelques secondes lève l'ambiguïté de l'essentiel de la liste ci-dessus sans aucun nouveau modèle, parce que les transitions reçoivent des indices plus denses à exploiter.

Donnez le cap et la vitesse quand l'appareil les a. Le score de transition consomme les deux, et un cap épingle le sens de circulation sur toute route à double sens.

Demandez la confiance, et fiez les tronçons peu sûrs à une file de relecture plutôt que directement dans votre tableau de bord. Un champ de confiance que vous ignorez ne coûte rien ; un match cru les yeux fermés dans un tunnel coûte une enquête plus tard.

Acceptez la limite structurelle : un matcher ne peut choisir qu'au sein des routes du graphe qu'on lui a donné. Quand une correspondance revient gravement fausse, l'algorithme est d'ordinaire innocent et le graphe est le suspect : la voie de service manquante, le sens unique périmé, la bretelle parallèle jamais numérisée. Corrigez les données avant de régler le décodeur, sinon vous passerez une saison à calibrer un modèle contre une carte qui ment.

La route que votre GPS croit suivre est une inférence, accompagnée d'un score de confiance que beaucoup de moteurs traitent comme optionnel. Quand l'inférence échoue, lisez l'échec au lieu de le jeter. Il nomme l'endroit exact où la carte et le monde se sont séparés.