{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T04:47:17Z","timestamp":1751518037110,"version":"3.38.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,9,20]],"date-time":"2024-09-20T00:00:00Z","timestamp":1726790400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,20]],"date-time":"2024-09-20T00:00:00Z","timestamp":1726790400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["05M20ZBM"],"award-info":[{"award-number":["05M20ZBM"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC-2046\/1, PID: 390685689"],"award-info":[{"award-number":["EXC-2046\/1, PID: 390685689"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The Periodic Event Scheduling Problem (PESP) is the standard mathematical tool for optimizing periodic timetables in public transport. A solution to a PESP instance consists of three parts: a periodic timetable, a periodic tension, and integer offset values. While the space of periodic tensions has received much attention in the past, we explore geometric properties of the other two components. The general aim of this paper is to establish novel connections between periodic timetabling and discrete geometry. Firstly, we study the space of feasible periodic timetables as a disjoint union of polytropes. These are polytopes that are convex both classically and in the sense of tropical geometry. We then study this decomposition and use it to outline a new heuristic for PESP, based on neighbourhood relations of the polytropes. Secondly, we recognize that the space of fractional cycle offsets is in fact a zonotope, and then study its zonotopal tilings. These are related to the hyperrectangle of fractional periodic tensions, as well as the polytropes of the periodic timetable space, and we detail their interplay. To conclude, we also use this new understanding to give tight lower bounds on the minimum width of an integral cycle basis.<\/jats:p>","DOI":"10.1007\/s00454-024-00686-2","type":"journal-article","created":{"date-parts":[[2024,9,20]],"date-time":"2024-09-20T14:03:02Z","timestamp":1726840982000},"page":"719-763","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Tropical and Zonotopal Geometry of Periodic Timetables"],"prefix":"10.1007","volume":"73","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2869-6498","authenticated-orcid":false,"given":"Enrico","family":"Bortoletto","sequence":"first","affiliation":[]},{"given":"Niels","family":"Lindner","sequence":"additional","affiliation":[]},{"given":"Berenike","family":"Masing","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,20]]},"reference":[{"issue":"2","key":"686_CR1","doi-asserted-by":"publisher","first-page":"167","DOI":"10.24033\/bsmf.2303","volume":"125","author":"R Bacher","year":"1997","unstructured":"Bacher, R., La Harpe, P.D., Nagnibeda, T.: The lattice of integral flows and the lattice of integral cuts on a finite graph. Bull. Soc. Math. Fr. 125(2), 167\u2013198 (1997)","journal-title":"Bull. Soc. Math. Fr."},{"key":"686_CR2","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/195","volume-title":"Combinatorial Reciprocity Theorems: An Invitation to Enumerative Geometric Combinatorics","author":"M Beck","year":"2018","unstructured":"Beck, M., Sanyal, R.: Combinatorial Reciprocity Theorems: An Invitation to Enumerative Geometric Combinatorics. American Mathematical Society, Providence (2018)"},{"key":"686_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511586507","volume-title":"Oriented Matroids, Encyclopedia of Mathematics and Its Applications","author":"A Bj\u00f6rner","year":"1999","unstructured":"Bj\u00f6rner, A., Las Vergnas, M., Sturmfels, B., White, N., Ziegler, G.M.: Oriented Matroids, Encyclopedia of Mathematics and Its Applications, 2nd edn. Cambridge University Press, Cambridge (1999)","edition":"2"},{"key":"686_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2019.100552","volume":"35","author":"R Bornd\u00f6rfer","year":"2020","unstructured":"Bornd\u00f6rfer, R., Hoppmann, H., Karbstein, M., Lindner, N.: Separation of cycle inequalities in periodic timetabling. Discret. Optim. 35, 100552 (2020)","journal-title":"Discret. Optim."},{"key":"686_CR5","volume":"15","author":"R Bornd\u00f6rfer","year":"2020","unstructured":"Bornd\u00f6rfer, R., Lindner, N., Roth, S.: A concurrent approach to the periodic event scheduling problem. J. Rail Transp. Plan. Manag. 15, 100175 (2020)","journal-title":"J. Rail Transp. Plan. Manag."},{"key":"686_CR6","unstructured":"Bortoletto, E., Lindner, N., Masing, B.: Tropical neighbourhood search: a new heuristic for periodic timetabling. In: D\u2019Emidio, M., Lindner, N. (eds.) 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022), Volume\u00a0106 of Open Access Series in Informatics (OASIcs), pp.\u00a03:1\u20133:19. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2022)"},{"key":"686_CR7","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.laa.2003.08.010","volume":"379","author":"G Cohen","year":"2004","unstructured":"Cohen, G., Gaubert, S., Quadrat, J.-P.: Duality and separation theorems in idempotent semimodules. Linear Algebra Appl. 379, 395\u2013422 (2004)","journal-title":"Linear Algebra Appl."},{"key":"686_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4171\/dm\/154","volume":"9","author":"M Develin","year":"2004","unstructured":"Develin, M., Sturmfels, B.: Tropical convexity. Doc. Math. 9, 1\u201327 (2004)","journal-title":"Doc. Math."},{"key":"686_CR9","first-page":"1439","volume":"289","author":"P Galashin","year":"2023","unstructured":"Galashin, P., Postnikov, A.: Purity and separation for oriented matroids. Mem. Am. Math. Soc. 289, 1439 (2023)","journal-title":"Mem. Am. Math. Soc."},{"key":"686_CR10","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2022.108549","volume":"407","author":"P Galashin","year":"2022","unstructured":"Galashin, P., Postnikov, A., Williams, L.: Higher secondary polytopes and regular plabic graphs. Adv. Math. 407, 108549 (2022)","journal-title":"Adv. Math."},{"key":"686_CR11","unstructured":"Goerigk, M.: PESPlib\u2014a benchmark library for periodic event scheduling (2012). https:\/\/timpasslib.aalto.fi\/pesplib.html"},{"key":"686_CR12","unstructured":"Goerigk, M., Liebchen, C.: An improved algorithm for the periodic timetabling problem. In: D\u2019Angelo, G., Dollevoet, T. (eds.) 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), Volume\u00a059 of OpenAccess Series in Informatics (OASIcs), pp.\u00a012:1\u201312:14. Schloss Dagstuhl \u2013 Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2017)"},{"issue":"5","key":"686_CR13","doi-asserted-by":"publisher","first-page":"1363","DOI":"10.1016\/j.cor.2012.08.018","volume":"40","author":"M Goerigk","year":"2013","unstructured":"Goerigk, M., Sch\u00f6bel, A.: Improving the modulo simplex algorithm for large-scale periodic timetabling. Comput. Oper. Res. 40(5), 1363\u20131370 (2013)","journal-title":"Comput. Oper. Res."},{"key":"686_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/978-3-642-31087-4_18","volume-title":"Advanced Research in Applied Artificial Intelligence","author":"P Gro\u00dfmann","year":"2012","unstructured":"Gro\u00dfmann, P., H\u00f6lldobler, S., Manthey, N., Nachtigall, K., Opitz, J., Steinke, P.: Solving periodic event scheduling problems with SAT. In: Jiang, H., Ding, W., Ali, M., Wu, X. (eds.) Advanced Research in Applied Artificial Intelligence. Lecture Notes in Computer Science, pp. 166\u2013175. Springer, Berlin, Heidelberg (2012)"},{"issue":"2","key":"686_CR15","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1137\/0216026","volume":"16","author":"JD Horton","year":"1987","unstructured":"Horton, J.D.: A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J. Comput. 16(2), 358\u2013366 (1987)","journal-title":"SIAM J. Comput."},{"key":"686_CR16","doi-asserted-by":"crossref","unstructured":"Joswig, M.: Essentials of Tropical Combinatorics. Graduate Studies in Mathematics, vol. 219. American Mathematical Society, Providence (2021)","DOI":"10.1090\/gsm\/219"},{"issue":"2","key":"686_CR17","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1515\/advgeom.2010.012","volume":"10","author":"M Joswig","year":"2010","unstructured":"Joswig, M., Kulas, K.: Tropical and ordinary convexity combined. Adv. Geom. 10(2), 333\u2013352 (2010)","journal-title":"Adv. Geom."},{"key":"686_CR18","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1016\/j.laa.2016.02.027","volume":"501","author":"M Joswig","year":"2016","unstructured":"Joswig, M., Loho, G.: Weighted digraphs and tropical cones. Linear Algebra Appl. 501, 304\u2013343 (2016)","journal-title":"Linear Algebra Appl."},{"issue":"4","key":"686_CR19","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.cosrev.2009.08.001","volume":"3","author":"T Kavitha","year":"2009","unstructured":"Kavitha, T., Liebchen, C., Mehlhorn, K., Michail, D., Rizzi, R., Ueckerdt, T., Zweig, K.A.: Cycle bases in graphs characterization, algorithms, complexity, and applications. Comput. Sci. Rev. 3(4), 199\u2013243 (2009)","journal-title":"Comput. Sci. Rev."},{"key":"686_CR20","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1007\/978-3-540-39658-1_64","volume-title":"Algorithms\u2013ESA 2003","author":"C Liebchen","year":"2003","unstructured":"Liebchen, C.: Finding short integral cycle bases for cyclic timetabling. In: Di Battista, G., Zwick, U. (eds.) Algorithms\u2013ESA 2003, pp. 715\u2013726. Springer, Berlin, Heidelberg (2003)"},{"key":"686_CR21","first-page":"29","volume-title":"Operations Research Proceedings","author":"C Liebchen","year":"2006","unstructured":"Liebchen, C.: Periodic timetable optimization in public transport. In: Waldmann, K.-H., Stocker, U.M. (eds.) Operations Research Proceedings, pp. 29\u201336. Springer, Berlin, Heidelberg (2006)"},{"issue":"4","key":"686_CR22","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1287\/trsc.1080.0240","volume":"42","author":"C Liebchen","year":"2008","unstructured":"Liebchen, C.: The first optimized railway timetable in practice. Transp. Sci. 42(4), 420\u2013435 (2008)","journal-title":"Transp. Sci."},{"key":"686_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-540-74247-0_1","volume-title":"Algorithmic Methods for Railway Optimization","author":"C Liebchen","year":"2007","unstructured":"Liebchen, C., M\u00f6hring, R.H.: The modeling power of the periodic event scheduling problem: railway timetables- and beyond. In: Geraets, F., Kroon, L., Schoebel, A., Wagner, D., Zaroliagis, C.D. (eds.) Algorithmic Methods for Railway Optimization. Lecture Notes in Computer Science, pp. 3\u201340. Springer, Berlin, Heidelberg (2007)"},{"key":"686_CR24","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.disopt.2008.09.003","volume":"6","author":"C Liebchen","year":"2009","unstructured":"Liebchen, C., Peeters, L.: Integral cycle bases for cyclic timetabling. Discret. Optim. 6, 98\u2013109 (2009)","journal-title":"Discret. Optim."},{"key":"686_CR25","unstructured":"Lindner, N., Liebchen, C.: New perspectives on PESP: T-partitions and separators. In: Cacchiani, V., Marchetti-Spaccamela, A. (eds.) 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) , Volume\u00a075 of OpenAccess Series in Informatics (OASIcs), pp.\u00a02:1\u20132:18. Schloss Dagstuhl \u2013 Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2019). ISSN: 2190-6807"},{"key":"686_CR26","unstructured":"Lindner, N., Liebchen, C.: Determining all integer vertices of the PESP polytope by flipping arcs. In: Huisman, D., Zaroliagis, C.D. (eds.) 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020), Volume\u00a085 of OpenAccess Series in Informatics (OASIcs), pp.\u00a05:1\u20135:18. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2020)"},{"key":"686_CR27","doi-asserted-by":"crossref","unstructured":"Lindner, N., Reisch, J.: An analysis of the parameterized complexity of periodic timetabling. J. Sched. 25, 157\u2013176 (2022)","DOI":"10.1007\/s10951-021-00719-1"},{"key":"686_CR28","unstructured":"Lindner, N., van Lieshout, R.: Benders decomposition for the periodic event scheduling problem. Technical report 21-29, ZIB, Takustr. 7, 14195 Berlin (2021)"},{"key":"686_CR29","doi-asserted-by":"crossref","unstructured":"Matos, G.P., Albino, L.M., Saldanha, R.L., Morgado, E.M.: Solving periodic timetabling problems with SAT and machine learning. Public Transp. 13(3), 625\u2013648 (2021)","DOI":"10.1007\/s12469-020-00244-y"},{"key":"686_CR30","unstructured":"Nachtigall, K.: Cutting planes for a polyhedron associated with a periodic network. DLR-Interner Bericht (1996)"},{"key":"686_CR31","volume-title":"Periodic network optimization and fixed interval timetables","author":"K Nachtigall","year":"1999","unstructured":"Nachtigall, K.: Periodic network optimization and fixed interval timetables. Deutsches Zentrum f\u00fcr Luft- und Raumfahrt e.V. LIDO-Berichts, Technical report (1999)"},{"key":"686_CR32","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/978-3-540-77903-2_71","volume-title":"Operations Research Proceedings 2007","author":"K Nachtigall","year":"2008","unstructured":"Nachtigall, K., Opitz, J.: A modulo network simplex method for solving periodic timetable optimisation problems. In: Kalcsics, J., Nickel, S. (eds.) Operations Research Proceedings 2007, pp. 461\u2013466. Springer, Berlin, Heidelberg (2008)"},{"key":"686_CR33","unstructured":"Nachtigall, K., Opitz, J.: Solving periodic timetable optimisation problems by modulo simplex calculations. In: Fischetti, M., Widmayer, P. (eds.) 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS\u201908), Volume\u00a09 of OpenAccess Series in Informatics (OASIcs). Schloss Dagstuhl \u2013 Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2008). ISSN: 2190-6807"},{"key":"686_CR34","unstructured":"Odijk, M.A.: Construction of periodic timetables, part 1: a cutting plane algorithm. Technical report 94-61, TU Delft (1994)"},{"issue":"6","key":"686_CR35","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1093\/imrn\/rnn153","volume":"2009","author":"A Postnikov","year":"2009","unstructured":"Postnikov, A.: Permutohedra, associahedra, and beyond. Int. Math. Res. Not. 2009(6), 1026\u20131106 (2009)","journal-title":"Int. Math. Res. Not."},{"key":"686_CR36","unstructured":"P\u00e4tzold, J., Sch\u00f6bel, A.: A matching approach for periodic timetabling. In: Goerigk, M., Werneck, R. (eds.) 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), Volume\u00a054 of OpenAccess Series in Informatics (OASIcs), pp.\u00a01:1\u20131:15. Schloss Dagstuhl \u2013 Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016). ISSN: 2190-6807"},{"key":"686_CR37","first-page":"211","volume-title":"Contemporary Mathematics","author":"J Richter-Gebert","year":"1994","unstructured":"Richter-Gebert, J., Ziegler, G.M.: Zonotopal tilings and the Bohne-Dress theorem. In: Barcelo, H., Kalai, G. (eds.) Contemporary Mathematics, vol. 178, pp. 211\u2013232. American Mathematical Society, Providence (1994)"},{"key":"686_CR38","volume-title":"Combinatorial Optimization-Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization-Polyhedra and Efficiency. Springer, Berlin, Heidelberg (2003)"},{"issue":"4","key":"686_CR39","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1137\/0402049","volume":"2","author":"P Serafini","year":"1989","unstructured":"Serafini, P., Ukovich, W.: A mathematical model for periodic scheduling problems. SIAM J. Discret. Math. 2(4), 550\u2013581 (1989)","journal-title":"SIAM J. Discret. Math."},{"key":"686_CR40","doi-asserted-by":"crossref","unstructured":"Stanley, R.P.: A zonotope associated with graphical degree sequences. In: Applied Geometry and Discrete Mathematics. The Victor Klee Festschrift 65th Birthday, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 4, pp. 555\u2013570 (1991)","DOI":"10.1090\/dimacs\/004\/42"},{"key":"686_CR41","doi-asserted-by":"crossref","unstructured":"Tutte, W.: Lectures on matroids. J. Res. Natl. Bur. Stand. Sect. B Math. Math. Phys. 69B(1 and 2), 1 (1965)","DOI":"10.6028\/jres.069B.001"},{"key":"686_CR42","doi-asserted-by":"crossref","unstructured":"Ziegler, G.M.: Lectures on Polytopes, Volume\u00a0152 of Graduate Texts in Mathematics. Springer, New York (1995). ISSN: 0072-5285","DOI":"10.1007\/978-1-4613-8431-1"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00686-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-024-00686-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-024-00686-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,17]],"date-time":"2025-03-17T14:58:02Z","timestamp":1742223482000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-024-00686-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,20]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["686"],"URL":"https:\/\/doi.org\/10.1007\/s00454-024-00686-2","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2024,9,20]]},"assertion":[{"value":"20 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 August 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}