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: https://drops.dagstuhl.de/opus/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
| 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: | 19.09.2014 |
