Master Team Project: Transit Routing

While it is quite easy to find paths in street networks, incorporating transit data can be quite challenging. There are bus stops that have to be considered, but the bus does not stop all the time, so it may be better to walk. The right bus stops have to be found to use the right bus or metro and when changing trains, the algorithm should wait for an appropriate period of time so that the user does not miss the bus.

This team project implements a graph representation of a street network and public transport stations in two different ways: time expanded, where each node in the graph represents a specific time and place and edges have constant costs, and time dependent, where the time information is moved to the edges and their costs depend on the time they are travelled. Both approaches have their benefits and drawbacks, while time dependent graphs have only a fraction of the nodes compared to time expanded graphs, calculating the edge costs is more expensive and re-visiting the same node at a later time (i.e. differentiating between staying in the same bus vs. getting off the bus and waiting at the same station for another bus that may reach the goal faster) becomes more complicated.