The Cheapest Ticket Problem in Public Transport

References

• Arkin E, Mitchell J, Piatko C (1991) Bicriteria shortest path problems in the plane. Proc. Third Canadian Conf. Comput. Geometry (Simon Fraser University, Vancouver), 153–156.Google Scholar
• Babel L, Kellerer H (2003) Design of tariff zones in public transportation systems: Theoretical results and heuristics. Math. Methods Oper. Res. 58(3):359–374.Crossref, Google Scholar
• Bast H, Delling D, Goldberg A, Müller-Hannemann M, Pajor T, Sanders P, Wagner D, Werneck R (2016) Route planning in transportation networks. Kliemann L, Sanders P, eds. Algorithm Engineering: Selected Results and Surveys. Lecture Notes in Computer Science, vol. 9220 (Springer, Cham, Switzerland), 19–80.Crossref, Google Scholar
• Blanco M, Borndörfer R, Hoàng N, Kaier A, Schlechte T, Schlobach S (2016) The shortest path problem with crossing costs. Technical report, Zuse Institute Berlin, Berlin.Google Scholar
• Blanco M, Borndörfer R, Hoàng N, Kaier A, Casas P, Schlechte T, Schlobach S (2017) Cost projection methods for the shortest path problem with crossing costs. D’Angelo G, Dollevoet T, eds. Proc. 17th Workshop Algorithmic Approaches Transportation Model., Optim., Systems. OpenAccess Series in Informatics, vol. 59 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 15:1–15:14.Google Scholar
• Borndörfer R, Hoppmann H, Karbstein M (2017) Passenger routing for periodic timetable optimization. Public Transport 9(1–2):115–135.Crossref, Google Scholar
• Borndörfer R, Karbstein M, Pfetsch M (2012) Models for fare planning in public transport. Discrete Appl. Math. 160(18):2591–2605.Crossref, Google Scholar
• Borndörfer R, Neumann M, Pfetsch M (2005) Models for fare planning in public transport. Technical report, Zuse Institute Berlin, Berlin.Google Scholar
• Delling D, Dibbelt J, Pajor T (2019) Fast and exact public transit routing with restricted Pareto sets. S Kobourov and H Meyerhenke, eds. Proc. 21st Workshop Algorithm Engrg. Experiments (Society for Industrial and Applied Mathematics, Philadelphia), 54–65.Google Scholar
• Delling D, Pajor T, Werneck R (2015) Round-based public transit routing. Transportation Sci. 49(3):591–604.Link, Google Scholar
• Dumitrescu I, Boland N (2003) Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem. Networks 42(3):135–153.Crossref, Google Scholar
• Euler R, Borndörfer R (2019) A graph- and monoid-based framework for price-sensitive routing in local public transportation networks. Cacchiani V, Marchetti-Spaccamela A, eds. Proc. 19th Sympos. Algorithmic Approaches Transportation Model., Optim., Systems. OpenAccess Series in Informatics, vol. 75 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 12:1–12:15.Google Scholar
• Fleishman D, Shaw N, Joshi A, Freeze R, Oram R (1996) Fare policies, strucutres, and technologies. Transit Cooperative Research Program Report 10, Transportation Research Board, Washington, DC.Google Scholar
• Galligari A, Maischberger M, Schoen F (2017) Local search heuristics for the zone planning problem. Optim. Lett. 11(1):195–207.Crossref, Google Scholar
• Garey M, Johnson D (1979) Computers and Intractability—A Guide to the Theory of NP-Completeness (H. W. Freeman and Company, San Francisco).Google Scholar
• Goerigk M, Knoth M, Müller-Hannemann M, Schmidt M, Schöbel A (2011) The price of robustness in timetable information. Caprara A, Kontogiannis S, eds. Proc. 11th Workshop Algorithmic Approaches Transportation Model., Optim., Systems. OpenAccess Series in Informatics, vol. 20 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 76–87.Google Scholar
• Goerigk M, Knoth M, Müller-Hannemann M, Schmidt M, Schöbel A (2014) The price of strict and light robustness in timetable information. Transportation Sci. 48(2):225–242.Link, Google Scholar
• Gunkel T, Müller-Hannemann M, Schnee M (2007) Improved search for night train connections. Liebchen C, Ahuja RK, Mesa JA, eds. Proc. Seventh Workshop Algorithmic Approaches Transportation Model., Optim., Systems. OpenAccess Series in Informatics, vol. 7 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 16:1–16:16.Google Scholar
• Hamacher H, Schöbel A (1995) On fair zone design in public transportation. Daduna J, Branco I, Paixao J, eds. Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 430 (Springer, Berlin), 8–22.Crossref, Google Scholar
• Hamacher H, Schöbel A (2004) Design of zone tariff systems in public transportation. Oper. Res. 52(6):897–908.Link, Google Scholar
• Hassin R (1992) Approximation schemes for the restricted shortest path problem. Math. Oper. Res. 17(1):36–42.Link, Google Scholar
• Jaffe J (1984) Algorithms for finding paths with multiple constraints. Networks 14(1):95–116.Crossref, Google Scholar
• Joksch H (1966) The shortest route problem with constraints. J. Math. Anal. Appl. 14(2):191–197.Crossref, Google Scholar
• Lo H, Yip C, Wan K (2003) Modeling transfer and non-linear fare structure in multi-modal network. Transportation Res. Part B: Methodological 37(2):149–170.Crossref, Google Scholar
• Lorenz D, Raz D (2001) A simple efficient approximation scheme for the restricted shortest path problem. Oper. Res. Lett. 28(5):213–219.Crossref, Google Scholar
• Maadi S, Schmöcker JD (2017) Optimal hyperpaths with non-additive link costs. Transportation Res. Procedia 23:790–808.Crossref, Google Scholar
• Maadi S, Schmöcker JD (2018) Theoretical evaluation on the effects of changes from a zonal to a distance-based fare structure. Proc. 15th Conf. Advanced Systems Public Transport TransitData, Brisbane, Australia. http://www.caspt.org/wp-content/uploads/2018/10/Papers/CASPT_2018_paper_123.pdf.Google Scholar
• Müller-Hannemann M, Schnee M (2006) Paying less for train connections with MOTIS. Kroon LG, Möhring RH, eds. Proc. Fifth Workshop Algorithmic Methods Models Optim. Railways. OpenAccess Series in Informatics, vol. 2 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany), 5:1–5:19.Google Scholar
• Otto B, Boysen N (2017) Zone-based tariff design in public transportation networks. Networks 69(4):349–366.Crossref, Google Scholar
• Schiewe P, Schöbel A (2020) Periodic timetabling with integrated routing: Toward applicable approaches. Transportation Sci. 54(6):1714–1731.Link, Google Scholar
• Schmöcker JD, Fonzone A, Maadi S, Belgiawan F (2016) Determining fare structures: Evidence and recommendations from a qualitative survey among transport authorities. Technical report, European Metropolitan Transport Authorities, Paris.Google Scholar
• Schöbel A, Urban R (2020) Cheapest paths in public transport: Properties and algorithms. Huisman D, Zaroliagis CD, eds. Proc. 20th Sympos. Algorithmic Approaches Transportation Modelling, Optim., Systems. OpenAccess Series in Informatics, vol. 85 (Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 13:1–13:16.Google Scholar
• Urban R (2020) Analysis and computation of cheapest paths in public transport. Unpublished master’s thesis, Technische Universität Kaiserslautern, Kaiserslautern, Germany.Google Scholar
• Wagner D, Willhalm T (2007) Speed-up techniques for shortest-path computations. Thomas W, Weil P, eds. Proc. Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 4393 (Springer, Berlin), 23–36.Google Scholar
• Yuan S, Varma S, Jue J (2005) Minimum-color path problems for reliability in mesh networks. Makki K, Knightly E, eds. Proc. IEEE 24th Annual Joint Conf. IEEE Comput. Comm. Soc., vol. 4 (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 2658–2669.Google Scholar