Engineering a New Model for Dynamic Timetable Information Systems

Many efforts have been done in the last decade to model public transport timetables
in a graph theoretical framework. The aim is to represent
a timetable as a graph so that an optimal route or itinerary
is found by computing afterwards a shortest path in such a graph. One of the most used models is the so called time-expanded graph model. Its main
drawback is that if the timetable changes (e.g., due to a delay
occurring in the network), the graph needs to be topologically updated.

In this paper we propose a new model to represent the timetable
of a public transportation system as a graph. Its main advantage is that it
can be efficiently updated after a change in the timetable. In fact, it is
based on a compact representation that allows us to update the graph by changing
only few arc weights and does not require any topological modification.
We also conduct a comparative experimental study on real-world timetables
to assess the efficiency and practical applicability of the new model against
the classical and the reduced time-expanded models. The experiments show that the new model outperforms the other two models in query
and update times and also in space requirements.