Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Cionini, Alessio; D'Angelo, Gianlorenzo; D'Emidio, Mattia; Frigioni, Daniele; Giannakopoulou, Kalliopi; Paraskevopoulos, Andreas; Zaroliagis, Christos http://www.dagstuhl.de/oasics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-47522
URL:

; ; ; ; ; ;

Engineering Graph-Based Models for Dynamic Timetable Information Systems

pdf-format:


Abstract

Many efforts have been done in the last years to model public transport timetables in order to find optimal routes. The proposed models can be classified into two types: those representing the timetable as an array, and those representing it as a graph. The array-based models have been shown to be very effective in terms of query time, while the graph-based models usually answer queries by computing shortest paths, and hence they are suitable to be used in combination with speed-up techniques developed for road networks. In this paper, we focus on the dynamic behavior of graph-based models considering the case where transportation systems are subject to delays with respect to the given timetable. We make three contributions: (i) we give a simplified and optimized update routine for the well-known time-expanded model along with an engineered query algorithm; (ii) we propose a new graph-based model tailored for handling dynamic updates; (iii) we assess the effectiveness of the proposed models and algorithms by an experimental study, which shows that both models require negligible update time and a query time which is comparable to that required by some array-based models.

BibTeX - Entry

@InProceedings{cionini_et_al:OASIcs:2014:4752,
  author =	{Alessio Cionini and Gianlorenzo D'Angelo and Mattia D'Emidio and Daniele Frigioni and Kalliopi Giannakopoulou and Andreas Paraskevopoulos and Christos Zaroliagis},
  title =	{{Engineering Graph-Based Models for Dynamic Timetable Information Systems}},
  booktitle =	{14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{46--61},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-75-0},
  ISSN =	{2190-6807},
  year =	{2014},
  volume =	{42},
  editor =	{Stefan Funke and Mat{\'u}{\v{s}} Mihal{\'a}k},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4752},
  URN =		{urn:nbn:de:0030-drops-47522},
  doi =		{10.4230/OASIcs.ATMOS.2014.46},
  annote =	{Keywords: Timetabling, dynamic updates, queries, shortest paths}
}

Keywords: Timetabling, dynamic updates, queries, shortest paths
Seminar: 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Issue date: 2014
Date of publication: 2014


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