License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2014.46
URN: urn:nbn:de:0030-drops-47522
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4752/
Cionini, Alessio ;
D'Angelo, Gianlorenzo ;
D'Emidio, Mattia ;
Frigioni, Daniele ;
Giannakopoulou, Kalliopi ;
Paraskevopoulos, Andreas ;
Zaroliagis, Christos
Engineering Graph-Based Models for Dynamic Timetable Information Systems
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 |
|
Collection: |
|
14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems |
|
Issue Date: |
|
2014 |
|
Date of publication: |
|
19.09.2014 |
