Abstract: 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 earliestarrival 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.
Abstract: 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 earliestarrival 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.
Abstract: We consider optimal itinerary problems in time-table information systems supporting a vast number of on-line queries. We exhibit two important extensions of the time-dependent approach to model realistic versions of the EarliestArrival and Minimum Number of Transfer problems, as well as of a combination of them, that could not be modeled by the original version of the time-dependent approach. We also provide heuristics that speed up implementations and present preliminary experimental results with real-world data.