{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T08:58:41Z","timestamp":1781341121464,"version":"3.54.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T00:00:00Z","timestamp":1687478400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T00:00:00Z","timestamp":1687478400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC-2046\/1, project ID: 390685689"],"award-info":[{"award-number":["EXC-2046\/1, project ID: 390685689"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Zuse-Institut Berlin"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Oper. Res. Forum"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The optimization of periodic timetables is an indispensable planning task in public transport. Although the periodic event scheduling problem (PESP) provides an elegant mathematical formulation of the periodic timetabling problem that led to many insights for primal heuristics, it is notoriously hard to solve to optimality. One reason is that for the standard mixed-integer linear programming formulations, linear programming relaxations are weak, and the integer variables are of pure technical nature and in general do not correlate with the objective value. While the first problem has been addressed by developing several families of cutting planes, we focus on the second aspect. We discuss integral forward cycle bases as a concept to compute improved dual bounds for PESP instances. To this end, we develop the theory of forward cycle bases on general digraphs. Specifically for the application of timetabling, we devise a generic procedure to construct line-based event-activity networks and give a simple recipe for an integral forward cycle basis on such networks. Finally, we analyze the 16 railway instances of the benchmark library PESPlib, match them to the line-based structure, and use forward cycle bases to compute better dual bounds for 14 out of the 16 instances.<\/jats:p>","DOI":"10.1007\/s43069-023-00229-0","type":"journal-article","created":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T21:50:28Z","timestamp":1687557028000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Forward and Line-Based Cycle Bases for Periodic\u00a0Timetabling"],"prefix":"10.1007","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7201-2412","authenticated-orcid":false,"given":"Berenike","family":"Masing","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8337-4387","authenticated-orcid":false,"given":"Niels","family":"Lindner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Patricia","family":"Ebert","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,6,23]]},"reference":[{"issue":"4","key":"229_CR1","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1137\/0402049","volume":"2","author":"P Serafini","year":"1989","unstructured":"Serafini P, Ukovich W (1989) A mathematical model for periodic scheduling problems. SIAM J Discret Math 2(4):550\u2013581","journal-title":"SIAM J Discret Math"},{"key":"229_CR2","doi-asserted-by":"publisher","first-page":"100552","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 (2020a) Separation of cycle inequalities in periodic timetabling. Discret Optim 35:100552","journal-title":"Discret Optim"},{"key":"229_CR3","unstructured":"Lindner N, Reisch J (2020) Parameterized complexity of periodic timetabling. Technical Report 20-15, Zuse Institute Berlin"},{"key":"229_CR4","unstructured":"Odijk MA (1994) Construction of periodic timetables, part 1: a cutting plane algorithm. Technical Report 94-61, TU Delft"},{"key":"229_CR5","unstructured":"Goerigk M (2012) PESPlib \u2013 a benchmark library for periodic event scheduling. http:\/\/num.math.uni-goettingen.de\/~m.goerigk\/pesplib\/"},{"key":"229_CR6","unstructured":"Nachtigall K (1996) Cutting planes for a polyhedron associated with a periodic network. Technical Report 112-96\/17, Deutsches Zentrum f\u00fcr Luft- und Raumfahrt"},{"issue":"1","key":"229_CR7","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 (2009) Integral cycle bases for cyclic timetabling. Discret Optim 6(1):98\u2013109","journal-title":"Discret Optim"},{"key":"229_CR8","first-page":"2190","volume-title":"8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS\u201908), volume 9 of OpenAccess Series in Informatics (OASIcs), Dagstuhl, Germany","author":"C Liebchen","year":"2008","unstructured":"Liebchen C, Swarat E (2008) The second chvatal closure can yield better railway timetables. In: Fischetti M, Widmayer P (eds) 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS\u201908), volume 9 of OpenAccess Series in Informatics (OASIcs), Dagstuhl, Germany. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, ISSN, pp 2190\u20136807"},{"key":"229_CR9","first-page":"2190","volume-title":"20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020), volume 85 of OpenAccess Series in Informatics (OASIcs), pages 5:1\u20135:18, Dagstuhl, Germany","author":"N Lindner","year":"2020","unstructured":"Lindner N, Liebchen C (2020) Determining all integer vertices of the PESP polytope by flipping arcs. In: Huisman D, Zaroliagis CD (eds) 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020), volume 85 of OpenAccess Series in Informatics (OASIcs), pages 5:1\u20135:18, Dagstuhl, Germany. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, ISSN, pp 2190\u20136807"},{"key":"229_CR10","doi-asserted-by":"crossref","unstructured":"Lindner N, Liebchen C (2021) Timetable merging for the periodic event scheduling problem. Technical Report 21-06. Zuse Institute Berlin","DOI":"10.1016\/j.ejtl.2022.100081"},{"key":"229_CR11","volume-title":"22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022), volume 106 of Open Access Series in Informatics (OASIcs), pages 3:1\u20133:19, Dagstuhl","author":"E Bortoletto","year":"2022","unstructured":"Bortoletto E, Lindner N, Masing B (2022) 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 106 of Open Access Series in Informatics (OASIcs), pages 3:1\u20133:19, Dagstuhl. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Germany"},{"key":"229_CR12","volume-title":"21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021), volume 96 of Open Access Series in Informatics (OASIcs), pages 2:1\u20132:14, Dagstuhl","author":"N Lindner","year":"2021","unstructured":"Lindner N, Liebchen C, Masing B (2021) Forward cycle bases and periodic timetabling. In: M\u00fcller-Hannemann M, Perea F (eds) 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021), volume 96 of Open Access Series in Informatics (OASIcs), pages 2:1\u20132:14, Dagstuhl. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Germany"},{"issue":"4","key":"229_CR13","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 KA (2009) Cycle bases in graphs characterization, algorithms, complexity, and applications. Comput Sci Rev 3(4):199\u2013243","journal-title":"Comput Sci Rev"},{"key":"229_CR14","unstructured":"Liebchen C (2006) Periodic timetable optimization in public transport. PhD thesis, Technische Universit\u00e4t Berlin"},{"key":"229_CR15","doi-asserted-by":"crossref","unstructured":"Liebchen C, M\u00f6hring RH (2007) The modeling power of the periodic event scheduling problem: railway timetables - and beyond. In Geraets, F., Kroon, L., Sch\u00f6bel, A., Wagner, D., and Zaroliagis, C.D., editors, Algorithmic Methods for Railway Optimization, Lecture Notes in Computer Science, pages 3\u201340, Berlin, Heidelberg. Springer","DOI":"10.1007\/978-3-540-74247-0_1"},{"issue":"3","key":"229_CR16","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.dam.2006.06.007","volume":"155","author":"C Liebchen","year":"2007","unstructured":"Liebchen C, Rizzi R (2007) Classes of cycle bases. Discret Appl Math 155(3):337\u2013355","journal-title":"Discret Appl Math"},{"key":"229_CR17","unstructured":"Liebchen C, Peeters L (2002) On cyclic timetabling and cycles in graphs. Technical report, Technische Universit\u00e4t Berlin"},{"issue":"2","key":"229_CR18","doi-asserted-by":"publisher","first-page":"241","DOI":"10.7151\/dmgt.1200","volume":"23","author":"PM Gleiss","year":"2003","unstructured":"Gleiss PM, Leydold J, Stadler PF (2003) Circuit bases of strongly connected digraphs. Discussiones Mathematicae Graph Theory 23(2):241","journal-title":"Discussiones Mathematicae Graph Theory"},{"issue":"1","key":"229_CR19","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/0095-8956(87)90061-X","volume":"42","author":"P Seymour","year":"1987","unstructured":"Seymour P, Thomassen C (1987) Characterization of even directed graphs. Journal of Combinatorial Theory, Series B 42(1):36\u201345","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"229_CR20","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, Third Edition. The MIT Press, 3rd edition"},{"issue":"2","key":"229_CR21","doi-asserted-by":"publisher","first-page":"1291","DOI":"10.1287\/ijoc.2021.1101","volume":"34","author":"C Helmberg","year":"2022","unstructured":"Helmberg C, Hofmann T, Wenzel D (2022) Periodic event scheduling for automated production systems. INFORMS J Comput 34(2):1291\u20131304","journal-title":"INFORMS J Comput"},{"key":"229_CR22","unstructured":"W\u00fcnsch G (2008) Coordination of traffic signals in networks. PhD thesis, Technische Universit\u00e4t Berlin"},{"key":"229_CR23","doi-asserted-by":"crossref","unstructured":"Bornd\u00f6rfer R, Lindner N, Roth S (2020b) A concurrent approach to the periodic event scheduling problem. J Rail Trans Plann Manag 15:100175. Best Papers of RailNorrk\u00f6ping 2019","DOI":"10.1016\/j.jrtpm.2019.100175"},{"key":"229_CR24","unstructured":"Goerigk M, Liebchen C (2017) An improved algorithm for the periodic timetabling problem. In ATMOS, volume59 of OASICS 12:1\u201312:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"issue":"2","key":"229_CR25","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1137\/0216026","volume":"16","author":"JD Horton","year":"1987","unstructured":"Horton JD (1987) A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J Comput 16(2):358\u2013366","journal-title":"SIAM J Comput"},{"key":"229_CR26","unstructured":"de Pina J (1995) Applications of shortest path methods. PhD thesis, University of Amsterdam"},{"key":"229_CR27","doi-asserted-by":"crossref","unstructured":"Hariharan R, Kavitha T, Mehlhorn K (2006) A faster deterministic algorithm for minimum cycle bases in directed graphs. In Bugliesi, M., Preneel, B., Sassone, V., and Wegener, I., editors, Automata, Languages and Programming, pages 250\u2013261, Berlin, Heidelberg. Springer Berlin Heidelberg","DOI":"10.1007\/11786986_23"},{"key":"229_CR28","doi-asserted-by":"crossref","unstructured":"Amaldi E, Iuliano C, Jurkiewicz T, Mehlhorn K, Rizzi R (2009) Breaking the o(m2n) barrier for minimum cycle bases. p 301\u2013312","DOI":"10.1007\/978-3-642-04128-0_28"},{"key":"229_CR29","doi-asserted-by":"crossref","unstructured":"Liebchen C, Proksch M, Wagner FH (2008) Performance of algorithms for periodic timetable optimization. volume 600, pages 151\u2013180, Berlin, Heidelberg. Springer Berlin Heidelberg. Book Title: Computer-aided Systems in Public Transport Series Title: Lecture Notes in Economics and Mathematical Systems","DOI":"10.1007\/978-3-540-73312-6_8"},{"key":"229_CR30","unstructured":"IBM (2019) IBM CPLEX optimizer 12.10 user\u2019s manual. https:\/\/www.ibm.com\/products\/ilog-cplex-optimization-studio\/cplex-optimizer"}],"container-title":["Operations Research Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-023-00229-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s43069-023-00229-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-023-00229-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,24]],"date-time":"2024-09-24T14:09:22Z","timestamp":1727186962000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s43069-023-00229-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,23]]},"references-count":30,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,9]]}},"alternative-id":["229"],"URL":"https:\/\/doi.org\/10.1007\/s43069-023-00229-0","relation":{},"ISSN":["2662-2556"],"issn-type":[{"value":"2662-2556","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,23]]},"assertion":[{"value":"27 January 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 June 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}},{"value":"The authors declare no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"53"}}