License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2009.2148
URN: urn:nbn:de:0030-drops-21481
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2148/
Go to the corresponding OASIcs Volume Portal

Berger, Annabell ; Delling, Daniel ; Gebhardt, Andreas ; Müller-Hannemann, Matthias

Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected

pdf-format:
BergerAnnabell.2148.pdf (0.3 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{berger_et_al:OASIcs:2009:2148,
  author =	{Annabell Berger and Daniel Delling and Andreas Gebhardt and Matthias M{\"u}ller-Hannemann},
  title =	{{Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected}},
  booktitle =	{9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-11-8},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{12},
  editor =	{Jens Clausen and Gabriele Di Stefano},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2148},
  URN =		{urn:nbn:de:0030-drops-21481},
  doi =		{10.4230/OASIcs.ATMOS.2009.2148},
  annote =	{Keywords: Timetable information, multi-criteria search, time-dependent networks, arc flags, contraction}
}

Keywords: Timetable information, multi-criteria search, time-dependent networks, arc flags, contraction
Freie Schlagwörter (englisch): Timetable information, multi-criteria search, time-dependent networks, arc flags, contraction
Collection: 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)
Issue Date: 2009
Date of publication: 25.11.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI