Analysis and improvement of map-matching methods for GPS trajectories in urban environments

This thesis investigates potential improvements to Spatial-Temporal Matching (ST-Matching) algorithm for matching the GPS trajectories to road networks. While this algorithm is effective, it presents some limitations in computational efficiency and the accuracy of the results, especially in dense environments with relatively high sampling intervals. To address this, the thesis proposes four modifications to the original algorithm: a dynamic buffer, an adaptive observation probability, a redesigned temporal scoring function, and a behavioral analysis to account for the historical mobility patterns. The enhancements were assessed using real-world data from the urban area of Milan, and through newly defined evaluation metrics to be applied in the absence of ground truth. The results of the experiment show significant improvements in performance efficiency and path quality across various metrics. Dynamic buffer is capable of removing a noticeable amount of unnecessary computational cost particularly when the accuracy of the data is relatively high. The new temporal score creates more realistic and topologically consistent paths with fewer loops and roundabouts. In case of low frequency data, although efficiency of the algorithm was still improved, reconstructed paths were mostly similar to those produced by the original algorithm. Path reconstruction using low frequency GPS data is still a challenging task, potentially requiring algorithmic adaptation, or integration of more contextual or historical data in future work.

Questa tesi esplora potenziali miglioramenti all'algoritmo ST-Matching per l'associazione delle traiettorie GPS alla rete stradale. Sebbene l’algoritmo sia efficace, presenta alcune limitazioni in termini di efficienza computazionale e accuratezza dei risultati, soprattutto quando le tracce GPS hanno intervalli di campionamento relativamente ampi. Per affrontare queste problematiche, la tesi propone quattro modifiche all’algoritmo originale: un buffer dinamico, una probabilità di osservazione adattiva, una nuova funzione temporale e un'analisi comportamentale basata su pattern di mobilità storici. L'algoritmo di mathing modificato è stato applicato a dati reali provenienti dall’area urbana di Milano e successivamente valutato con mediante un insieme di metriche nuove. I risultati mostrano miglioramenti significativi in termini di efficienza e di qualità del percorso. Il buffer dinamico consente di ridurre sensibilmente i costi computazionali superflui, in particolare quando l’accuratezza dei dati è elevata. La nuova funzione temporale genera percorsi più realistici e topologicamente coerenti, con meno loop e segmenti improbabili. Nel caso di dati GPS a bassa frequenza, sebbene l’efficienza dell’algoritmo sia stata comunque migliorata, i percorsi ricostruiti risultano per lo più simili a quelli prodotti dall’algoritmo originale. La ricostruzione di percorsi con dati GPS a bassa frequenza di campionamento rimane una sfida aperta, che potrebbe richiedere dei nuovi adattamenti all'algoritmo o l'integrazione di informazioni contestuali o storiche in lavori futuri.