2026-07-20T04:51:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4752 2024-03-06T10:29:39Z ddc:004 open_access

Engineering Graph-Based Models for Dynamic Timetable Information Systems Cionini, Alessio D'Angelo, Gianlorenzo D'Emidio, Mattia Frigioni, Daniele Giannakopoulou, Kalliopi Paraskevopoulos, Andreas Zaroliagis, Christos 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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alessio Cionini and Gianlorenzo D'Angelo and Mattia D'Emidio and Daniele Frigioni and Kalliopi Giannakopoulou and Andreas Paraskevopoulos and Christos Zaroliagis 2014 Is Part Of OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2014.46 urn:nbn:de:0030-drops-47522 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.46 eng https://creativecommons.org/licenses/by/3.0/legalcode