Identify the Most Trafficked Roads Using Sequence Alignment Algorithms

Abstract

Kartlegging og behandling av trafikkdata bidrar til å skape bedre og mer bærekraftige transportalternativer. Denne oppgaven undersøker bruken av sekvenssammenstillingsalgoritmer for å sammenligne GPS-spor med mål om å kartlegge trafikk. Likhet i GPS-spor er et mye undersøkt emne, men algoritmer for sekvenssammenstilling har ikke blitt testet for dette formålet før. I denne studien er tre sekvenssammenstillingsalgoritmer implementert for å sammenligne GPS-spor for å identifisere den mest trafikkerte veien i en by. Algoritmene sender ut overlappende del-spor som tildeles en poengsum basert på hyppighet og lengde. Resultatet ble bevist å bestå av hyppige del-spor som dekket de travleste gatene i byen Porto.

The mapping and processing of traffic data contribute to creating better and more sustainable transportation alternatives. This thesis investigates the use of sequence alignment algorithms for comparing trajectories with the goal of mapping traffic. Trajectory similarity is an extensively researched topic, yet sequence alignment algorithms have not been tested for this purpose before. In this study, three sequence alignment algorithms are implemented to compare trajectories to identify the most trafficked road in a city. The algorithms output overlapping sub-trajectories that are assigned a score based on frequency and length. The result was proved to consist of frequent sub-trajectories that covered the busiest streets in the city of Porto.