|
This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies.
For more information visit Aigaion.nl. |  |
Type of publication: | Inproceedings |
Entered by: | chita |
Title | Engineering Graph-Based Models for Dynamic Timetable Information Systems |
Bibtex cite ID | RACTI-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 |
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 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. |
Authors | |
Topics
| =SEE CLASSIFICATION DIFFERENCE FROM OTHERS=
=SEE OWN CLASSIFICATION=
|
BibTeX | BibTeX |
RIS | RIS |
Attachments |
C67-ATMOS2014-Eng-GB-Models.pdf (main file) |
|
Publication ID | 1060 |
|
|