Document Open Access Logo

Cheapest Paths in Public Transport: Properties and Algorithms

Authors Anita Schöbel, Reena Urban

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2020.13.pdf
  • Filesize: 0.51 MB
  • 16 pages

Document Identifiers

Author Details

Anita Schöbel
  • Technische Universität Kaiserslautern, Germany
  • Fraunhofer-Institute for Industrial Mathematics ITWM, Kaiserslautern, Germany
Reena Urban
  • Technische Universität Kaiserslautern, Germany

Cite As Get BibTex

Anita Schöbel and Reena Urban. Cheapest Paths in Public Transport: Properties and Algorithms. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/OASIcs.ATMOS.2020.13

Abstract

When determining the paths of the passengers in public transport, the travel time is usually the main criterion. However, also the ticket price a passenger has to pay is a relevant factor for choosing the path. The ticket price is also relevant for simulating the minimum income a public transport company can expect.
However, finding the correct price depends on the fare system used (e.g., distance tariff, zone tariff with different particularities, application of a short-distance tariff, etc.) and may be rather complicated even if the path is already fixed. An algorithm which finds a cheapest path in a very general case has been provided in [R. Euler and R. Borndörfer, 2019], but its running time is exponential. In this paper, we model and analyze different fare systems, identify important properties they may have and provide polynomial algorithms for computing a cheapest path.

Subject Classification

ACM Subject Classification
  • Applied computing → Transportation
Keywords
  • Public Transport
  • Fare Systems
  • Modeling
  • Cheapest Paths

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. H. Bast, D. Delling, A. V. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner, and R. F. Werneck. Route planning in transportation networks. In L. Kliemann and P. Sanders, editors, Algorithm Engineering: Selected Results and Surveys, volume 9220 of LNCS State of the Art, pages 19-80. 2016. Google Scholar
  2. R. Borndörfer, M. Karbstein, and M. E. Pfetsch. Models for fare planning in public transport. Technical report, ZIB, 2005. Google Scholar
  3. R. Borndörfer, M. Karbstein, and M.E. Pfetsch. Models for fare planning in public transport. Discrete Applied Mathematics, 160(18):2591-2605, 2012. Google Scholar
  4. D. Delling, , T. Pajor, and R.F. Werneck. Round-based public transit routing. Transportation Science, 49(3):591-604, 2015. Google Scholar
  5. D. Delling, J. Dibbelt, and T. Pajor. Fast and exact public transit routing with restricted Pareto sets. In Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments (ALENEX), pages 54-65, 2019. Google Scholar
  6. R. Euler and R. Borndörfer. A graph- and monoid-based framework for price-sensitive routing in local public transportation networks. In V. Cacchiani and A. Marchetti-Spaccamela, editors, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019), volume 75 of OpenAccess Series in Informatics (OASIcs), pages 12:1-12:15, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.ATMOS.2019.6.
  7. A. Galligari, M. Maischberger, and F. Schoen. Local search heuristics for the zone planning problem. Optimization Letters, 11:195-207, 2017. Google Scholar
  8. T. Gunkel, M. Müller-Hannemann, and M. Schnee. 16. Improved search for night train connections. In Christian Liebchen, Ravindra K. Ahuja, and Juan A. Mesa, editors, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07), volume 7 of OpenAccess Series in Informatics (OASIcs), Dagstuhl, Germany, 2007. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.ATMOS.2007.1178.
  9. H.W. Hamacher and A. Schöbel. On fair zone design in public transportation. In J.R. Daduna, I. Branco, and J.M.P. Paixao, editors, Computer-Aided Transit Scheduling, number 430 in Lecture Notes in Economics and Mathematical Systems, pages 8-22. Springer, Berlin, Heidelberg, 1995. Google Scholar
  10. H.W. Hamacher and A. Schöbel. Design of zone tariff systems in public transportation. OR, 52(6):897-908, 2004. Google Scholar
  11. S. Maadi and J.-D. Schmöcker. Theoretical evaluation on the effects of changes from a zonal to a distance-based fare structure. In Proceedings of CASPT'18, Brisbane. 2018. Google Scholar
  12. M. Müller-Hannemann and M. Schnee. Paying less for train connections with MOTIS. In Leo G. Kroon and Rolf H. Möhring, editors, 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05), volume 2 of OpenAccess Series in Informatics (OASIcs), Dagstuhl, Germany, 2006. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/OASIcs.ATMOS.2005.657.
  13. B. Otto and N. Boysen. Zone-based tariff design in public transportation networks. Networks, 69(4):349-366, 2017. Google Scholar
  14. P. Schiewe and A. Schöbel. Periodic timetabling with integrated routing: Towards applicable approaches. Transportation Science, to appear. Google Scholar
  15. R. Urban. Analysis and computation of cheapest paths in public transport. Master’s thesis, Technische Universität Kaiserslautern, 2020. Google Scholar
  16. D. Wagner and T. Willhalm. Speed-up techniques for shortest-path computations. In STACS 2007, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact