Multimodal Profile Queries

Route planning has many applications in the real world. We can use it for computing thebest journey for both road or public transportation networks. In the latter, the journeysare restricted by a schedule. The traveltime then depends on the departure time. To findthe shortest traveltime for a given departure time is called a time query, to find the short-est traveltime for all departure times is called a profile query. In this thesis, we developand evaluate algorithms that perform such profile queries for a multimodal network. Amultimodal network is a network that consists of several modes of transports.Some sequences of modes of transports are undesirable. For example, a user might notwant to take a taxi after exiting a train. This can be modeled by assigning labels to alledges of the subnetwork, and only to consider those paths as valid where the labels of theedges produce a word of a formal language.We develop two algorithms, named the Function and the Label Algorithm. We presentimprovements to both algorithms and evaluate them on real world data. We achieve aspeedup of up to one order of magnitude to a hypothetical algorithm that knows eachrelevant departure time in advance and performs a multimodal, time-dependent general-ization of Dijkstra’s Algorithm for each of them.