research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleEngineering Graph-Based Models for Dynamic Timetable Information Systems
Bibtex cite IDRACTI-RU1-2014-34
Booktitle 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems
Series OASIcs
Year published 2014
Volume 42
Pages 46-61
Organization ATMOS 2014
Keywords Timetabling,dynamic updates,queries,shortest paths
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 wellknown 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.
Cionini, Alessio
D'Angelo, Gianlorenzo
D'Emidio, Mattia
Frigioni, D.
Giannakopoulou, Kalliopi
Paraskevopoulos, Andreas
Zaroliagis, Christos
C67-ATMOS2014-Eng-GB-Models.pdf (main file)
Publication ID1060