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.2007.1171
URN: urn:nbn:de:0030-drops-11717
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/1171/
Go to the corresponding OASIcs Volume Portal

Bruera, Francesco ; Cicerone, Serafino ; D'Angelo, Gianlorenzo ; Di Stefano, Gabriele ; Frigioni, Daniele

15. Maintenance of Multi-level Overlay Graphs for Timetable Queries

pdf-format:
07001.BrueraFrancesco.Paper.1171.pdf (0.2 MB)

Abstract

In railways systems the timetable is typically represented as a
weighted digraph on which itinerary queries are answered by
shortest path algorithms, usually running Dijkstra's algorithm.
Due to the continuously growing size of real-world graphs, there
is a constant need for faster algorithms and many techniques have
been devised to heuristically speed up Dijkstra's algorithm. One
of these techniques is the multi-level overlay graph, that
has been recently introduced and shown to be experimentally
efficient, especially when applied to timetable information.

In many practical application major disruptions to the normal
operation cannot be completely avoided because of the complexity
of the underlying systems. Timetable information
update after disruptions is considered one of the weakest points
in current railway systems, and this determines the need for an
effective online redesign and update of the shortest paths
information as a consequence of disruptions.

In this paper, we make a step forward toward this direction by
showing some theoretical properties of multi-level overlay graphs
that lead us to the definition of a new data structure for the
dynamic maintenance of a multi-level overlay graph of a given
graph G while weight decrease or weight increase operations are
performed on G. Our solution is theoretically faster than the
recomputation from scratch and allows fast queries.

BibTeX - Entry

@InProceedings{bruera_et_al:OASIcs:2007:1171,
  author =	{Francesco Bruera and Serafino Cicerone and Gianlorenzo D'Angelo and Gabriele Di Stefano and Daniele Frigioni},
  title =	{{15. Maintenance of Multi-level Overlay Graphs for Timetable Queries}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Christian Liebchen and Ravindra K. Ahuja and Juan A. Mesa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2007/1171},
  URN =		{urn:nbn:de:0030-drops-11717},
  doi =		{10.4230/OASIcs.ATMOS.2007.1171},
  annote =	{Keywords: Timetable Queries, Speed-up techniques for shortest paths, Dynamic maintenance of shortest paths}
}

Keywords: Timetable Queries, Speed-up techniques for shortest paths, Dynamic maintenance of shortest paths
Collection: 7th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'07)
Issue Date: 2007
Date of publication: 06.11.2007

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