2026-07-23T00:19:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2148 2024-03-06T10:28:39Z ddc:004 open_access

Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected Berger, Annabell Delling, Daniel Gebhardt, Andreas Müller-Hannemann, Matthias Timetable information multi-criteria search time-dependent networks arc flags contraction Timetable information multi-criteria search time-dependent networks arc flags contraction Speeding up multi-criteria search in real timetable information systems remains a challenge in spite of impressive progress achieved in recent years for related problems in road networks. Our goal is to perform multi-criteria range queries, that is, to find all Pareto-optimal connections with respect to travel time and number of transfers within a given start time interval. This problem can be modeled as a path search problem in a time- and event-dependent graph. In this paper, we investigate two key speed-up techniques for a multi-criteria variant of \textsc{Dijkstra}'s algorithm --- arc flags and contraction --- which seem to be strong candidates for railway networks, too. We describe in detail how these two techniques have to be adapted for a multi-criteria scenario and explain why we can expect only marginal speed-ups (compared to observations in road networks) from a direct implementation. Based on these insights we extend traditional arc-flags to \emph{time-period flags} and introduce \emph{route contraction} as a substitute for node contraction. A computational study on real queries demonstrates that these techniques combined with goal-directed search lead to a speed-up of factor 13.08 over the baseline variant for range queries for a full day. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Annabell Berger and Daniel Delling and Andreas Gebhardt and Matthias Müller-Hannemann 2009 Is Part Of OASIcs, Volume 12, 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09) (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2009.2148 urn:nbn:de:0030-drops-21481 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2148 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode