research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:chita
TitleEfficient Models for Timetable Information in Public Transportation Systems
Bibtex cite IDRACTI-RU1-2008-40
Journal ACM Journal of Experimental Algorithmics
Year published 2008
Volume 12
Number 2.4
Pages 1-39
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 modeled as a node in the graph, while in the timedependent approach the graph contains only one node per station. Both approaches have been recently considered for (a simplified version of) the earliest arrival problem, but little is known about their relative performance. Thus far, there are only theoretical arguments in favor of the time-dependent approach. In this paper, we provide the first extensive experimental comparison of the two approaches. Using several real-world data sets, we evaluate the performance of the basic models and of several new extensions towards realistic modeling. Furthermore, new insights on solving bicriteria optimization problems in both models are presented. The time-expanded approach turns out to be more robust for modeling more complex scenarios, whereas the time-dependent approach shows a clearly better performance.
Pyrga, Evangelia
Schulz, Frank
Wagner, Dorothea
Zaroliagis, Christos
J23-PSWZ-ACM-JEA-Vol12-N2.4-2008.pdf (main file)
Publication ID488