OASIcs.ATMOS.2019.12.pdf
- Filesize: 0.53 MB
- 15 pages
Document
A Graph- and Monoid-Based Framework for Price-Sensitive Routing in Local Public Transportation Networks
Authors
Ricardo Euler 
,
-
Part of:
Volume:
19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-11-15
File
Document Identifiers
Author Details
Acknowledgements
We thank Niels Lindner and Pedro Maristany de las Casas for many fruitful discussions on the subject as well as MDV and InfraDialog GmbH for providing the data for this study.
Cite As Get BibTex
Ricardo Euler and Ralf Borndörfer. A Graph- and Monoid-Based Framework for Price-Sensitive Routing in Local Public Transportation Networks. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/OASIcs.ATMOS.2019.12
Abstract
We present a novel framework to mathematically describe the fare systems of local public transit companies. The model allows the computation of a provably cheapest itinerary even if prices depend on a number of parameters and non-linear conditions. Our approach is based on a ticket graph model to represent tickets and their relation to each other. Transitions between tickets are modeled via transition functions over partially ordered monoids and a set of symbols representing special properties of fares (e.g. surcharges). Shortest path algorithms rely on the subpath optimality property. This property is usually lost when dealing with complicated fare systems. We restore it by relaxing domination rules for tickets depending on the structure of the ticket graph. An exemplary model for the fare system of Mitteldeutsche Verkehrsbetriebe (MDV) is provided. By integrating our framework in the multi-criteria RAPTOR algorithm we provide a price-sensitive algorithm for the earliest arrival problem and assess its performance on data obtained from MDV. We discuss three preprocessing techniques that improve run times enough to make the algorithm applicable for real-time queries.
Subject Classification
ACM Subject Classification
- Mathematics of computing → Graph algorithms
- Applied computing → Transportation
Keywords
- shortest path
- public transit
- optimization
- price-sensitive
- raptor
- fare
- operations research
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Chris Barrett, Riko Jacob, and Madhav Marathe. Formal-Language-Constrained Path Problems. SIAM J. Comput., 30(3):809-837, May 2000. URL: https://doi.org/10.1137/S0097539798337716.
-
Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck. Route Planning in Transportation Networks. In Algorithm Engineering - Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 19-80. Springer, 2016.
- Annabell Berger and Matthias Müller-Hannemann. Subpath-Optimality of Multi-Criteria Shortest Paths in Time- and Event-Dependent Networks. Technical report, Institute of Computer Science, Martin-Luther-Universität Halle-Wittenberg, 2009. URL: http://wcms.uzi.uni-halle.de/download.php?down=10850&elem=2163494.
- Ralf Borndörfer, Ricardo Euler, Marika Karbstein, and Fabian Mett. Ein mathematisches Modell zur Beschreibung von Preissystemen im öV. Technical Report 18-47, ZIB, Takustr. 7, 14195 Berlin, 2018. URL: https://nbn-resolving.org//urn:nbn:de:0297-zib-70564.
- Daniel Delling, Julian Dibbelt, and Thomas Pajor. Fast and Exact Public Transit Routing with Restricted Pareto Sets. In 2019 Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX), pages 54-65, 2019. URL: https://doi.org/10.1137/1.9781611975499.5.
- Daniel Delling, Thomas Pajor, and Renato F. Werneck. Round-Based Public Transit Routing. Transportation Science, 49(3):591-604, 2015. URL: https://doi.org/10.1287/trsc.2014.0534.
- Yann Disser, Matthias Müller-Hannemann, and Mathias Schnee. Multi-criteria Shortest Paths in Time-dependent Train Networks. In Catherine C. McGeoch, editor, Proceedings of the 7th International Conference on Experimental Algorithms, WEA'08, pages 347-361, Berlin, Heidelberg, 2008. Springer-Verlag. URL: https://doi.org/10.1007/978-3-540-68552-4_26.
- Mehryar Mohri. Semiring Frameworks and Algorithms for Shortest-distance Problems. J. Autom. Lang. Comb., 7(3):321-350, January 2002. URL: http://dl.acm.org/citation.cfm?id=639508.639512.
- Matthias Müller-Hannemann and Mathias Schnee. Paying less for train connections with MOTIS. In Proceedings of the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways, volume 2 of OpenAccess Series in Informatics, page 657, January 2005. URL: https://doi.org/10.4230/OASIcs.ATMOS.2005.657.
-
U. Zimmermann. Linear and combinatorial optimization in ordered algebraic structures, volume 10 of Annaly of discrete mathematics. North-Holland, 1981.