author: Yoeri Otten
title: Adapting, analyzing and benchmarking transportation routing algorithms for realistic real-time environments
keywords: Transit routing, Analysis of algorithms, Graph algorithms, Benchmarking, Real-time data
topics: Algorithms and Data Structures , Case studies and Applications , Dependability, security and performance , Graphs
committee: Luís Ferreira Pires ,
Tom van Dijk
end: January 2021


There are many algorithms to find paths within a public transportation timetable, often relying upon preprocessing or complex data structures to speed up the process. While these algorithms have undergone many tests, there has not been a review with these algorithms with real-time realistic data. This makes it difficult to choose the most suitable algorithm necessary in most real-world scenarios. We compare several commonly used algorithms adapted for real-time data and test them in static and real-time environments to figure out which problems are encountered, and which algorithm(s) best adapt to those problems.