Cos'è il map matching? Agganciare le tracce GPS alla rete stradale

Il map matching è il passaggio, poco visibile ma indispensabile, che trasforma una nuvola di punti GPS imprecisi in un percorso pulito lungo strade reali. Senza map matching, la dashboard di una flotta mostra camion che attraversano gli edifici, un modello tariffario assicurativo non distingue un'autostrada da una strada secondaria e una corsa in ride sharing sembra un tracciato tirato a caso. Con il map matching, ogni punto diventa una posizione su un tratto noto del grafo stradale, con la direzione di marcia e la distanza lungo l'arco.

In questa guida vediamo cos'è il map matching, perché il GPS grezzo non basta, come funzionano gli algoritmi e dove si usa nei sistemi in produzione.

Cosa fa il map matching

Nella forma più semplice, il map matching riceve due input. Il primo è una sequenza di fix GPS in ordine di tempo: latitudine, longitudine, timestamp e spesso anche velocità e direzione. Il secondo è una rete stradale su cui si può calcolare un percorso, di solito OpenStreetMap trasformato in un grafo di archi e nodi. In uscita, ogni fix è agganciato a un arco preciso del grafo, con la sua posizione lungo l'arco e i metadati del tratto.

Il risultato è una polilinea che segue le strade vere, più l'elenco dei tratti stradali effettivamente percorsi. Proprio quell'elenco rende possibili le analisi successive: limiti di velocità per tratto, classe della strada, numero di svolte, paese e regione attraversati e distanza esatta per arco, invece della distanza in linea d'aria tra un fix e l'altro.

Una traccia da sola ti dice più o meno dove è andato un dispositivo. Una traccia abbinata alla rete ti dice quali strade ha usato.

Perché il GPS grezzo non basta

Il GPS di uno smartphone ha in genere una precisione di circa 4,9 metri a cielo aperto, e la precisione cala vicino a edifici, ponti e alberi. Nella telemetria reale tre problemi strutturali peggiorano ancora le cose.

Canyon urbani. Nei centri città densi, i palazzi alti bloccano la vista diretta dei satelliti e riflettono il segnale sulle facciate di vetro. Il ricevitore vede una copia ritardata del segnale (multipath) e calcola una posizione che può cadere a un isolato di distanza, spesso su una strada parallela.

Deriva all'accensione. Quando un dispositivo si accende senza dati di assistenza, può impiegare decine di secondi per agganciare abbastanza satelliti e ottenere un fix affidabile. I primi punti di una traccia sono quindi spesso i meno precisi, proprio quando un veicolo esce da un parcheggio o da un deposito.

Campionamento rado. I tracker IoT a batteria spesso registrano un fix ogni 30 secondi o ogni minuto, per risparmiare energia. In autostrada significa più di un chilometro tra un punto e l'altro, e la linea retta tra i due raramente coincide con il percorso reale. Il matcher deve colmare il vuoto calcolando un percorso sul grafo, non tracciando una linea.

Messi insieme, questi errori fanno sì che un sistema che prende i fix grezzi come verità produca, senza accorgersene, distanze sbagliate, strade sbagliate e fatture sbagliate.

Come funziona il map matching

L'approccio più usato in produzione è il modello di Markov nascosto (Hidden Markov Model) reso popolare da Newson e Krumm nel 2009. Il grafo stradale diventa un insieme di stati nascosti (su quale arco si trova davvero il dispositivo) e la traccia GPS una serie di osservazioni imprecise di quegli stati. Il matcher si basa su due probabilità.

Probabilità di emissione. Per ogni fix, l'algoritmo cerca gli archi candidati entro un raggio di ricerca, di solito tra 25 e 200 metri. Poi assegna a ciascuno un punteggio: quanto è plausibile che la posizione vera sia su quell'arco, dato il fix osservato. Il punteggio è di solito una distribuzione gaussiana sulla distanza perpendicolare tra il fix e l'arco.

Probabilità di transizione. Per ogni coppia di fix consecutivi, l'algoritmo valuta ogni coppia di archi candidati: quanto è plausibile passare dal primo al secondo nel tempo trascorso. Per farlo calcola un percorso sul grafo tra i candidati e confronta la sua lunghezza con la distanza ortodromica tra i fix. Le differenze vengono penalizzate, quindi gli spostamenti impossibili (oltre un fiume, contromano in un senso unico, a velocità che quella strada non consente) ottengono punteggi bassissimi.

L'algoritmo di Viterbi trova poi, in un solo passaggio sull'intera traccia, la sequenza di archi più probabile. Sia OSRM sia Valhalla offrono matcher HMM pronti per la produzione basati su questo approccio. Entrambi gestiscono anche tracce rade, interruzioni nel tempo e punti di rottura in cui il dispositivo ha lasciato la rete stradale.

Dove si usa il map matching

Il map matching lavora dietro le quinte e quasi mai ha un'interfaccia, ma regge una lunga serie di prodotti.

• Telemetria delle flotte. Le flotte di camion e furgoni registrano un fix ogni pochi secondi. Il map matching trasforma questo flusso in chilometri per tratto, per autista, per veicolo e per regione, e alimenta buste paga, controllo del carburante e verifica dei percorsi.
• Analisi dello stile di guida. Una frenata brusca o un eccesso di velocità hanno senso solo se conosci il limite del tratto su cui si trovava l'autista. Per questo serve l'arco abbinato, non il fix grezzo.
• Ricostruzione delle corse nel ride sharing. Quando un passeggero contesta una tariffa, la piattaforma ricostruisce la corsa dal log GPS dell'autista. Una traccia abbinata alla rete dà una polilinea verificabile lungo strade vere e una distanza che regge a una contestazione.
• Assicurazioni per viaggio. Le polizze a chilometro e quelle basate sullo stile di guida richiedono chilometri precisi per ogni viaggio e il tipo di strade percorse. Piccoli errori di chilometraggio si sommano su tutto il portafoglio, quindi la distanza di ogni viaggio deve essere solida.
• Tracciamento di dispositivi IoT. Container, monopattini elettrici e attrezzature a noleggio inviano fix radi. Il map matching li collega in viaggi con distanze corrette, anche quando tra un fix e l'altro passano minuti.
• Analisi del traffico stradale. Comuni e gestori autostradali usano le tracce abbinate per stimare i flussi, trovare i tratti congestionati e studiare la ripartizione modale senza installare sensori.

Problemi tipici in produzione

In una demo il map matching sembra semplice. Con dati reali e grandi volumi si complica.

Tracce rade. Quando i fix distano più di un chilometro, il matcher deve scegliere un solo percorso tra di loro. Se esistono due percorsi ragionevoli, a volte vince quello sbagliato. Allargare la finestra dei candidati aiuta, ma allunga molto i tempi di calcolo.

Tratti fuori strada. I veicoli lasciano spesso la rete: parcheggi, strade private, traghetti, sterrati. Un matcher semplice li forza sulla strada più vicina e produce chilometri fantasma. I matcher di produzione riconoscono i punti di rottura e restituiscono un vuoto non abbinato invece di tirare a indovinare.

Strade parallele. Un'autostrada con la sua complanare, una superstrada a carreggiate separate o una griglia urbana fitta producono candidati con punteggi quasi uguali. A decidere sono la direzione e la velocità, quando sono disponibili.

Tracce su più giorni. Un veicolo che resta parcheggiato di notte produce due viaggi separati, non una traccia con un buco di 12 ore. Dividere l'input in viaggi prima del matching costa di solito meno ed è più preciso di un unico enorme passaggio di Viterbi.

Privacy. Una traccia abbinata è un registro ad alta risoluzione di dove si trovava una persona e quando. Per il GDPR e normative simili è un dato personale. Conservazione, tempi di cancellazione e registri degli accessi devono essere adeguati alla sensibilità del dato, e l'aggregazione va fatta il prima possibile nella pipeline.

Il map matching in MapAtlas

La Map Matching API di MapAtlas riceve una sequenza di fix GPS e restituisce una polilinea agganciata alla rete stradale. Per ogni punto trovi l'ID dell'arco, i metadati del tratto e un punteggio di affidabilità dell'abbinamento. Gestisce tracce rade, riconosce i punti di rottura nei tratti fuori strada e copre i casi più comuni (telemetria delle flotte, ricostruzione delle corse, tracciamento IoT) senza che tu debba gestire un tuo cluster OSRM o Valhalla.

Funziona bene insieme alla Directions API di MapAtlas, quando vuoi confrontare un percorso storico abbinato con il percorso ottimale. E con la Geocoding API di MapAtlas, quando devi trasformare l'inizio e la fine di un viaggio in indirizzi leggibili per una dashboard o per la ricevuta di un cliente.

Una traccia abbinata alla rete è solo una polilinea. Ma è la polilinea che permette a ogni sistema successivo, dalla fatturazione all'analisi alla conformità, di concordare su quale strada si trovava davvero un dispositivo.