@article{RiedmuellerLindner2025, author = {Riedm{\"u}ller, Stephanie and Lindner, Niels}, title = {Column Generation for Periodic Timetabling}, arxiv = {http://arxiv.org/abs/2510.12466}, year = {2025}, abstract = {Periodic timetabling for public transportation networks is typically modelled as a Periodic Event Scheduling Problem (PESP). Solving instances of the benchmark library PESPlib to optimality continues to pose a challenge. As a further approach towards this goal, we remodel the problem by a time discretization of the underlying graph and consider arc-based as well as path-based integer programming formulations. For the path-based case, we use cycles on the graph expansion of the operational lines as variables and, therefore, include more of the problem inherent structure into the model. A consequence is the validity of several known inequalities and a lower bound on the LP-relaxation, that is the best known to date. As an extension we integrate passenger routing into the new model. The proposed models have an advantage in the linear programming relaxation, on the one hand, but have an increased problem size, on the other hand. We define the corresponding pricing problems for the use of column generation to handle the size. Both models are practically tested on different problem instances.}, language = {en} } @inproceedings{LoebelLindner2025, author = {L{\"o}bel, Fabian and Lindner, Niels}, title = {A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing}, volume = {137}, booktitle = {25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)}, editor = {Sauer, Jonas and Schmidt, Marie}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, isbn = {978-3-95977-404-8}, issn = {2190-6807}, doi = {10.4230/OASIcs.ATMOS.2025.2}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-247580}, pages = {2:1 -- 2:19}, year = {2025}, abstract = {We offer a geometric perspective on the problem of integrated periodic timetabling and passenger routing in public transport. Inside the space of periodic tensions, we single out those regions, where the same set of paths provides shortest passenger routes. This results in a polyhedral subdivision, which we combine with the known decomposition by polytropes. On each maximal region of the common refinement, the integrated problem is solvable in polynomial time. We transform these insights into a new geometry-driven primal heuristic, integrated tropical neighborhood search (ITNS). Computationally, we compare implementations of ITNS and the integrated (restricted) modulo network simplex algorithm on the TimPassLib benchmark set, and contribute better solutions in terms of total travel time for all but one of the twenty-five instances for which a proven optimal solution is not yet known.}, language = {en} } @article{vanLieshoutLindner2025, author = {van Lieshout, Rolf and Lindner, Niels}, title = {A Compact Cycle Formulation for the Multiperiodic Event Scheduling Problem}, arxiv = {http://arxiv.org/abs/2507.17566}, year = {2025}, abstract = {The Periodic Event Scheduling Problem (PESP) is a fundamental model in periodic timetabling for public transport systems, assuming a common period across all events. However, real-world networks often feature heterogeneous service frequencies. This paper studies the Multiperiodic Event Scheduling Problem (MPESP), a generalization of PESP that allows each event to recur at its own individual period. While more expressive, MPESP presents new modeling challenges due to the loss of a global period. We present a cycle-based formulation for MPESP that extends the strongest known formulation for PESP and, in contrast to existing approaches, is valid for any MPESP instance. Crucially, the formulation requires a cycle basis derived from a spanning tree satisfying specific structural properties, which we formalize and algorithmically construct, extending the concept of sharp spanning trees to rooted instances. We further prove a multiperiodic analogue of the cycle periodicity property. Our new formulation solves nearly all tested instances, including several large-scale real-world public transport networks, to optimality or with small optimality gaps, dramatically outperforming existing arc-based models. The results demonstrate the practical potential of MPESP in capturing heterogeneous frequencies without resorting to artificial event duplication.}, language = {en} } @misc{TeschBorndoerfer2025, author = {Tesch, Alexander and Bornd{\"o}rfer, Ralf}, title = {Mathematische Optimierung in der OP-Planung}, volume = {5}, journal = {OP-Management up2date}, number = {1}, publisher = {Thieme}, doi = {10.1055/a-2322-2124}, pages = {21 -- 34}, year = {2025}, abstract = {Deutsche Krankenh{\"a}user sehen sich derzeit mit enormen Schwierigkeiten konfrontiert. Ungef{\"a}hr jede 2. Klinik muss drastische Sparmaßnahmen ergreifen, was auch die Allgemeinversorgung beeintr{\"a}chtigt. Die Gr{\"u}nde daf{\"u}r sind vielschichtig: stark gestiegene Sach- und Personalkosten bei gleicher Finanzierung, teilweiser Patientenr{\"u}ckgang, starke regionale Unterschiede in der Versorgung, Fachkr{\"a}ftemangel und fehlende Investitionen in Kern- und Zukunftsbereiche, insbesondere der Digitalisierung. Das belastet die Haushalte der Kliniken. Insbesondere die Digitalisierung und die Anwendung von Methoden der k{\"u}nstlichen Intelligenz und der mathematischen Optimierung k{\"o}nnten eine Schl{\"u}sselrolle spielen, um die komplexen Krankenhausprozesse mit Kennzahlen qualitativ zu bewerten und zu verbessern. In diesem Artikel stellen wir vier Praxisprobleme aus der OP-Planung vor und benennen welche Entscheidungen, Nebenbedingungen und Zielkriterien mit mathematischen Entscheidungsmodellen dargestellt und optimiert werden k{\"o}nnen. Hierzu erl{\"a}utern wir das erweiterte Potenzial einer umfassenden Anwendung von mathematischer Optimierung im OP-Bereich.}, language = {de} } @article{MaristanydelasCasasSedenoNodaBorndoerfer2025, author = {Maristany de las Casas, Pedro and Sede{\~n}o-Noda, Antonio and Bornd{\"o}rfer, Ralf}, title = {New Dynamic Programming Algorithm for the Multiobjective Minimum Spanning Tree Problem}, volume = {173}, journal = {Computers \& Operations Research}, arxiv = {http://arxiv.org/abs/2306.16203}, doi = {10.1016/j.cor.2024.106852}, pages = {106852}, year = {2025}, abstract = {The Multiobjective Minimum Spanning Tree (MO-MST) problem is a variant of the Minimum Spanning Tree problem, in which the costs associated with every edge of the input graph are vectors. In this paper, we design a new dynamic programming MO-MST algorithm. Dynamic programming for a MO-MST instance leads to the definition of an instance of the One-to-One Multiobjective Shortest Path (MOSP) problem and both instances have equivalent solution sets. The arising MOSP instance is defined on a so called transition graph. We study the original size of this graph in detail and reduce its size using cost dependent arc pruning criteria. To solve the MOSP instance on the reduced transition graph, we design the Implicit Graph Multiobjective Dijkstra Algorithm (IG-MDA), exploiting recent improvements on MOSP algorithms from the literature. All in all, the new IG-MDA outperforms the current state of the art on a big set of instances from the literature. Our code and results are publicly available.}, language = {en} } @article{MasingLindnerBortoletto2025, author = {Masing, Berenike and Lindner, Niels and Bortoletto, Enrico}, title = {Computing All Shortest Passenger Routes with a Tropical Dijkstra Algorithm}, volume = {14}, journal = {EURO Journal on Transportation and Logistics}, arxiv = {http://arxiv.org/abs/2412.14654}, doi = {10.1016/j.ejtl.2025.100163}, year = {2025}, abstract = {Given a public transportation network, which and how many passenger routes can potentially be shortest paths, when all possible timetables are taken into account? This question leads to shortest path problems on graphs with interval costs on their arcs and is closely linked to multi-objective optimization. We introduce a Dijkstra algorithm based on polynomials over the tropical semiring that computes complete or minimal sets of efficient paths. We demonstrate that this approach is computationally feasible by employing it on the public transport network of the city of Wuppertal and instances of the benchmarking set TimPassLib, and we evaluate the resulting sets of passenger routes.}, language = {en} } @misc{EbertSchlechteSchwartz2025, author = {Ebert, Patricia and Schlechte, Thomas and Schwartz, Stephan}, title = {Scheduling for German Road Inspectors}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-101999}, year = {2025}, abstract = {For the yearly over 500,000 vehicle inspections of the German Federal Logistics and Mobility Office (BALM), crew rosters must be scheduled to efficiently achieve Germany's road inspection control targets. For that, we present a model to solve the respective duty scheduling and crew rostering problem in order to obtain duty rosters that comply with numerous legal regulations while maximizing the 'control success' to achieve the control targets. We formulate the Template Assignment Problem, which can be modelled as a large scale mixed-integer linear program. Here, feasible combinations of control topics are assigned to the duties using a hypergraph approach. The model is used in production by BALM, and we prove its effectiveness on a number of real-world instances.}, language = {en} } @article{GrimmHoogervorstBorndoerfer2025, author = {Grimm, Boris and Hoogervorst, Rowan and Bornd{\"o}rfer, Ralf}, title = {A Comparison of Two Models for Rolling Stock Scheduling}, volume = {59}, journal = {Transportation Science}, number = {5}, arxiv = {http://arxiv.org/abs/2312.09697}, doi = {10.1287/trsc.2024.0505}, year = {2025}, abstract = {A major step in the planning process of passenger railway operators is the assignment of rolling stock, that is, train units, to the trips of the timetable. A wide variety of mathematical optimization models have been proposed to support this task, which we discuss and argue to be justified in order to deal with operational differences between railway operators, and hence different planning requirements, in the best possible way. Our investigation focuses on two commonly used models, the composition model and the hypergraph model, that were developed for Netherlands Railways (NS) and DB Fernverkehr AG (DB), respectively. We compare these models in two distinct problem settings, an NS setting and DB-light setting and consider different model variants to tune the models to these settings. We prove that in both of these settings, the linear programming bounds of the two models are equally strong as long as a number of reasonable assumptions are met. However, through a numerical evaluation on NS and DB-light instances, we show that the numerical performance of the models strongly depends on the instances. Although the composition model is the most compact and fastest model for the NS instances, an adjusted version of this model grows quickly for the DB-light instances and is then outperformed by the considered hypergraph model variants. Moreover, we show that a depot-extended version of the hypergraph model is able to combine strengths of both models and show good performance on both the NS and DB-light instances.}, language = {en} } @article{BortolettoLindnerMasing2025, author = {Bortoletto, Enrico and Lindner, Niels and Masing, Berenike}, title = {The Tropical and Zonotopal Geometry of Periodic Timetables}, volume = {73}, journal = {Discrete \& Computational Geometry}, doi = {10.1007/s00454-024-00686-2}, pages = {719 -- 763}, year = {2025}, abstract = {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.}, language = {en} } @inproceedings{LindnerLiebchen2025, author = {Lindner, Niels and Liebchen, Christian}, title = {Incremental Heuristics for Periodic Timetabling}, booktitle = {Operations Research Proceedings 2023}, editor = {Voigt, Guido and Fliedner, Malte and Haase, Knut and Br{\"u}ggemann, Wolfgang and Hoberg, Kai and Meissner, J{\"o}rn}, publisher = {Springer Nature Switzerland}, address = {Cham}, doi = {10.1007/978-3-031-58405-3_59}, pages = {461 -- 467}, year = {2025}, abstract = {We present incremental heuristics for the Periodic Event Scheduling Problem (PESP), the standard mathematical tool to optimize periodic timetables in public transport. The core of our method is to solve successively larger subinstances making use of previously found solutions. Introducing the technical notion of free stratifications, we formulate a general scheme for incremental heuristics for PESP. More practically, we use line and station information to create heuristics that add lines or stations one by one, and we evaluate these heuristics on instances of the benchmarking library PESPlib. This approach is indeed viable, and leads to new incumbent solutions for six PESPlib instances.}, language = {en} } @article{MaristanydelasCasasSedenoNodaBorndoerferetal.2025, author = {Maristany de las Casas, Pedro and Sede{\~n}o-Noda, Antonio and Bornd{\"o}rfer, Ralf and Huneshagen, Max}, title = {K-Shortest Simple Paths Using Biobjective Path Search}, volume = {17}, journal = {Mathematical Programming Computation}, arxiv = {http://arxiv.org/abs/2309.10377}, doi = {10.1007/s12532-025-00276-0}, pages = {349 -- 384}, year = {2025}, abstract = {In this paper we introduce a new algorithm for the k-Shortest Simple Paths (K-SSP) problem with an asymptotic running time matching the state of the art from the literature. It is based on a black-box algorithm due to Roditty and Zwick (2012) that solves at most 2k instances of the Second Shortest Simple Path (2-SSP) problem without specifying how this is done. We fill this gap using a novel approach: we turn the scalar 2-SSP into instances of the Biobjective Shortest Path problem. Our experiments on grid graphs and on road networks show that the new algorithm is very efficient in practice.}, language = {en} }