{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T10:08:56Z","timestamp":1775038136304,"version":"3.50.1"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004966","name":"Fifth Framework Programme","doi-asserted-by":"publisher","award":["HPRN-CT-1999-00104(AMORE)"],"award-info":[{"award-number":["HPRN-CT-1999-00104(AMORE)"]}],"id":[{"id":"10.13039\/501100004966","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["IST-2002-001907(DELIS)FP6-021235-2(ARRIVAL)"],"award-info":[{"award-number":["IST-2002-001907(DELIS)FP6-021235-2(ARRIVAL)"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["WA 654\/1-12"],"award-info":[{"award-number":["WA 654\/1-12"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>\n            We consider two approaches that model timetable information in public transportation systems as shortest-path problems in weighted graphs. In the\n            <jats:italic>time-expanded<\/jats:italic>\n            approach, every event at a station, e.g., the departure of a train, is modeled as a node in the graph, while in the\n            <jats:italic>time-dependent<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.1145\/1227161.1227166","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"1-39","source":"Crossref","is-referenced-by-count":122,"title":["Efficient models for timetable information in public transportation systems"],"prefix":"10.1145","volume":"12","author":[{"given":"Evangelia","family":"Pyrga","sequence":"first","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Saarbrucken, Germany"}]},{"given":"Frank","family":"Schulz","sequence":"additional","affiliation":[{"name":"University of Karlsruhe, Karlsruhe, Germany"}]},{"given":"Dorothea","family":"Wagner","sequence":"additional","affiliation":[{"name":"University of Karlsruhe, Karlsruhe, Germany"}]},{"given":"Christos","family":"Zaroliagis","sequence":"additional","affiliation":[{"name":"CTI and University of Patras, Patras, Greece"}]}],"member":"320","published-online":{"date-parts":[[2008,6,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proc. 3rd Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS","volume":"92","author":"Brodal G. S.","year":"2003","unstructured":"Brodal, G. S. and Jacob, R. 2004. Time-dependent networks as models to achieve fast exact time-table queries. In Proc. 3rd Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS 2003). Electronic Notes in Theoretical Computer Science, vol. 92. Elsevier."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_3_1","volume-title":"A timetable information system by HaCon Ingenieurgesellschaft mbH","author":"HAFAS.","unstructured":"HAFAS. A timetable information system by HaCon Ingenieurgesellschaft mbH, Hannover, Germany. http:\/\/www.hacon.de\/hafas\/."},{"key":"e_1_2_1_4_1","volume-title":"Combinatorial Algorithms for Integrated Circuit Layout","author":"Lengauer T.","unstructured":"Lengauer, T. 1990. Combinatorial Algorithms for Integrated Circuit Layout. Wiley, New York."},{"key":"e_1_2_1_5_1","volume-title":"Angewandte Mathematik\u2014insbesondere Informatik","author":"M\u00f6hring R.","unstructured":"M\u00f6hring, R. 1999. Angewandte Mathematik\u2014insbesondere Informatik. Vieweg, Wiesbaden, Germany. 192--220."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/647258.720925"},{"key":"e_1_2_1_7_1","volume-title":"Proc. 2nd Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS","volume":"66","author":"M\u00fcller-Hannemann M.","year":"2002","unstructured":"M\u00fcller-Hannemann, M., Schnee, M., and Weihe, K. 2002. Getting train timetables into the main storage. In Proc. 2nd Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS 2002). Electronic Notes in Theoretical Computer Science, vol. 66. Elsevier, New York."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)E0349-G"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/79147.214078"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Orda A. and Rom R. 1991. Minimum weight paths in time-dependent networks. Networks 21.","DOI":"10.1002\/net.3230210304"},{"key":"e_1_2_1_11_1","unstructured":"Pallottino S. and Scutell\u00e0 M. G. 1998. Equilibrium and Advanced Transportation Modelling. Kluwer Academic Publ. Boston MA. Chapter 11."},{"key":"e_1_2_1_12_1","unstructured":"Pyrga E. Schulz F. Wagner D. and Zaroliagis C. 2004a. Experimental comparison of shortest path approaches for timetable information. In Algorithm Engineering and Experiments\u2014ALENEX 2004. SIAM 88--99."},{"key":"e_1_2_1_13_1","volume-title":"Proc. 3rd Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS","volume":"92","author":"Pyrga E.","year":"2003","unstructured":"Pyrga, E., Schulz, F., Wagner, D., and Zaroliagis, C. 2004b. Towards realistic modeling of time-table information through the time-dependent approach. In Proc. 3rd Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS 2003). Electronic Notes in Theoretical Computer Science, vol. 92. Elsevier, New York. 85--103."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/351827.384254"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/646680.702320"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064546.1103378"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1227166","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1227161.1227166","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:37Z","timestamp":1750278157000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1227166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":16,"alternative-id":["10.1145\/1227161.1227166"],"URL":"https:\/\/doi.org\/10.1145\/1227161.1227166","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}