Light Weight Public Transit Routing with GTFS Files

In agent-based transport models, it is necessary to determine the shortest path between an agent's current location and destination to simulate the agents' decision-making process. Algorithms for finding the shortest path on a network are well understood and applicable (Dijkstra). However, we must determine thousands of paths per agent for millions of agents in agent-based models. Therefore, determining the shortest paths is often the bottleneck of the simulation. The problem is especially prevalent in public transit decisions, where finding the shortest path depends on the weekday and time of day because of irregular schedules.

The goal of this thesis is to create a lightweight public transit router based on publicly available GTFS files (https://developers.google.com/transit/gtfs). A GTFS file parser is already available, and routing algorithms from existing libraries can be used. The focus of the thesis should be on searching the literature for applicable routing algorithms and methods to simplify the routing graph to obtain approximate solutions. The algorithms are then to be implemented and evaluated regarding runtime and accuracy of the resulting travel duration.

Necessary:

• Experience with Java or Kotlin
• Basic knowledge of shortest path algorithms (Dijkstra)

Helpfull:

• Experience with handling data tables (>= 100 k rows)