### Efficient models for timetable information in public transportation systemsEfficient models for timetable information in public transportation systems

Access Restriction
Subscribed

 Author Pyrga, Evangelia ♦ Schulz, Frank ♦ Wagner, Dorothea ♦ Zaroliagis, Christos Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2008 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Shortest path ♦ Itinerary query ♦ Public transportation system ♦ Timetable information Abstract We consider two approaches that model timetable information in public transportation systems as shortest-path problems in weighted graphs. In the $\textit{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 $\textit{time-dependent}$ 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. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2008-06-12 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 12 Page Count 39 Starting Page 1 Ending Page 39

#### Open content in new tab

Source: ACM Digital Library