Two Approaches for Time-Table Information : a Comparison of Models and Performance
Evangelia Pyrga, Frank Schulz, Dorothea Wagner, Christos Zaroliagis · KOPS (University of Konstanz) · 2003
We consider two approaches that model timetable information in public transportation systems as shortest-path problems in weighted graphs. In the time-expanded approach every event at a station, e.g., the departure of a train, is modelled as a node in the graph, while in the time-dependent approach the graph contains only one node per station. Train connections without intermediate stops correspond to edges. There is one edge for each single connection in the time-expanded model; in contrast, a couple of trains belong to the same edge in the time-dependent model. Both approaches have been recently considered for the earliest arrival problem. In this paper, we compare, on the one hand, the approaches with respect to more realistic modelling of real-world requirements. On the other hand, we evaluate their performance in an experimental study using real-world data.The time-expanded approach turns out to be more robust for modelling more complex scenarios, whereas the time-dependent approach shows a clearly better performance.As a conclusion the combination of both approaches seems promising.