Delay-Robustness of Transfer Patterns in Public Transportation Route Planning

Abstract : Transfer pattern routing is a state-of-the-art speed-up technique for finding optimal paths which minimize multiple cost criteria in public transportation networks. It precomputes sequences of transfer stations along optimal paths. At query time, the optimal paths are searched among the stored transfer patterns, which allows for very fast response times even on very large networks. On the other hand, even a minor change to the timetables may affect many optimal paths, so that, in principle, a new computation of all optimal transfer patterns becomes necessary. In this paper, we examine the robustness of transfer pattern routing towards delay, which is the most common source of such updates. The intuition is that the deviating paths caused by typical updates are already covered by original transfer patterns. We perform experiments which show that the transfer patterns are remarkably robust even to large and many delays, which underlines the applicability and reliability of transfer pattern routing in realistic routing applications.
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.42--54, 2013, OpenAccess Series in Informatics (OASIcs). 〈10.4230/OASIcs.ATMOS.2013.42〉
Liste complète des métadonnées

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

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

Fichier

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

Identifiants

Collections

Citation

Hannah Bast, Jonas Sternisko, Sabine Storandt. Delay-Robustness of Transfer Patterns in Public Transportation Route Planning. 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.42--54, 2013, OpenAccess Series in Informatics (OASIcs). 〈10.4230/OASIcs.ATMOS.2013.42〉. 〈hal-00871735〉

Partager

Métriques

Consultations de la notice

158

Téléchargements de fichiers

365