Robust Routing in Urban Public Transportation: How to Find Reliable Journeys Based on Past Observations

Abstract : We study the problem of robust routing in urban public transportation networks. In order to propose solutions that are robust for typical delays, we assume that we have past observations of real traffic situations available. In particular, we assume that we have "daily records" containing the observed travel times in the whole network for a few past days. We introduce a new concept to express a solution that is feasible in any record of a given public transportation network. We adapt the method of Buhmann et al. [Buhmann et al., ITCS 2013] for optimization under uncertainty, and develop algorithms that allow its application for finding a robust journey from a given source to a given destination. The performance of the algorithms and the quality of the predicted journey are evaluated in a preliminary experimental study. We furthermore introduce a measure of reliability of a given journey, and develop algorithms for its computation. The robust routing concepts presented in this work are suited specially for public transportation networks of large cities that lack clear hierarchical structure and contain services that run with high frequencies.
Type de document :
Communication dans un congrès
Daniele Frigioni and Sebastian Stiller. ATMOS - 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems - 2013, Sep 2013, Sophia Antipolis, France. Schloss Dagstuhl―Leibniz-Zentrum fuer Informatik, 33, pp.27--41, 2013, OpenAccess Series in Informatics (OASIcs). 〈10.4230/OASIcs.ATMOS.2013.27〉
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00871734
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 10 octobre 2013 - 11:59:10
Dernière modification le : vendredi 11 octobre 2013 - 13:32:38
Document(s) archivé(s) le : vendredi 7 avril 2017 - 08:57:17

Fichier

4.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Katerina Böhmová, Matús Mihalák, Tobias Pröger, Rastislav Srámek, Peter Widmayer. Robust Routing in Urban Public Transportation: How to Find Reliable Journeys Based on Past Observations. Daniele Frigioni and Sebastian Stiller. ATMOS - 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems - 2013, Sep 2013, Sophia Antipolis, France. Schloss Dagstuhl―Leibniz-Zentrum fuer Informatik, 33, pp.27--41, 2013, OpenAccess Series in Informatics (OASIcs). 〈10.4230/OASIcs.ATMOS.2013.27〉. 〈hal-00871734〉

Partager

Métriques

Consultations de la notice

129

Téléchargements de fichiers

430