@inproceedings{MasingLindnerLiebchen2023, author = {Masing, Berenike and Lindner, Niels and Liebchen, Christian}, title = {Integrating Line Planning for Construction Sites into Periodic Timetabling via Track Choice}, volume = {115}, booktitle = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, doi = {10.4230/OASIcs.ATMOS.2023.5}, pages = {5:1 -- 5:15}, year = {2023}, abstract = {We consider maintenance sites for urban rail systems, where unavailable tracks typically require changes to the regular timetable, and often even to the line plan. In this paper, we present an integrated mixed-integer linear optimization model to compute an optimal line plan that makes best use of the available tracks, together with a periodic timetable, including its detailed routing on the tracks within the stations. The key component is a flexible, turn-sensitive event-activity network that allows to integrate line planning and train routing using a track choice extension of the Periodic Event Scheduling Problem (PESP). Major goals are to maintain as much of the regular service as possible, and to keep the necessary changes rather local. Moreover, we present computational results on real construction site scenarios on the S-Bahn Berlin network. We demonstrate that this integrated problem is indeed solvable on practically relevant instances.}, language = {en} } @inproceedings{Masing2022, author = {Masing, Berenike}, title = {Optimal Line Planning in the Parametric City}, booktitle = {Operations Research Proceedings 2021. OR 2021.}, editor = {Trautmann, Norbert and Dr{\"a}gi, Mario}, publisher = {Springer, Cham}, isbn = {978-3-031-08623-6}, doi = {10.1007/978-3-031-08623-6_7}, pages = {39 -- 44}, year = {2022}, abstract = {We formulate the line planning problem in public transport as a mixed integer linear program (MILP), which selects both passenger and vehicle routes, such that travel demands are met with respect to minimized travel times for both operators and users. We apply MILP to the Parametric City, a generic city model developed by Fielbaum et al. [2]. While the infrastructure graph and demand are entirely rotation symmetric, asymmetric optimal line plans can occur. Using group theory, we analyze the properties of symmetric solutions and introduce a symmetry gap to measure their deviation of the optimum. We also develop a 1+1+2√g-approximation algorithm, depending only on the cost related parameter g. Supported by computational experiments, we conclude that in practice symmetric line plans provide good solutions for the line planning problem in the Parametric City.}, language = {en} } @inproceedings{LindnervanLieshout2022, author = {Lindner, Niels and van Lieshout, Rolf}, title = {Benders Decomposition for the Periodic Event Scheduling Problem}, booktitle = {Operations Research Proceedings 2021}, publisher = {Springer International Publishing}, address = {Cham}, doi = {10.1007/978-3-031-08623-6_43}, pages = {289 -- 294}, year = {2022}, abstract = {The Periodic Event Scheduling Problem (PESP) is the central mathematical model behind the optimization of periodic timetables in public transport. We apply Benders decomposition to the incidence-based MIP formulation of PESP. The resulting formulation exhibits particularly nice features: The subproblem is a minimum cost network flow problem, and feasibility cuts are equivalent to the well-known cycle inequalities by Odijk. We integrate the Benders approach into a branch-and-cut framework, and assess the performance of this method on instances derived from the benchmarking library PESPlib.}, language = {en} } @inproceedings{LoebelLindnerBorndoerfer2020, author = {L{\"o}bel, Fabian and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {The Restricted Modulo Network Simplex Method for Integrated Periodic Timetabling and Passenger Routing}, booktitle = {Operations Research Proceedings 2019}, editor = {Neufeld, Janis S. and Buscher, Udo and Lasch, Rainer and M{\"o}st, Dominik and Sch{\"o}nberger, J{\"o}rn}, publisher = {Springer International Publishing}, address = {Cham}, isbn = {978-3-030-48438-5}, doi = {https://doi.org/10.1007/978-3-030-48439-2_92}, pages = {757 -- 763}, year = {2020}, abstract = {The Periodic Event Scheduling Problem is a well-studied NP-hard problem with applications in public transportation to find good periodic timetables. Among the most powerful heuristics to solve the periodic timetabling problem is the modulo network simplex method. In this paper, we consider the more difficult version with integrated passenger routing and propose a refined integrated variant to solve this problem on real-world-based instances.}, language = {en} } @inproceedings{PrauseBorndoerfer2024, author = {Prause, Felix and Bornd{\"o}rfer, Ralf}, title = {A Bayesian Rolling Horizon Approach for Rolling Stock Rotation Planning with Predictive Maintenance}, volume = {123}, booktitle = {24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)}, doi = {10.4230/OASIcs.ATMOS.2024.13}, pages = {13:1 -- 13:19}, year = {2024}, abstract = {We consider the rolling stock rotation planning problem with predictive maintenance (RSRP-PdM), where a timetable given by a set of trips must be operated by a fleet of vehicles. Here, the health states of the vehicles are assumed to be random variables, and their maintenance schedule should be planned based on their predicted failure probabilities. Utilizing the Bayesian update step of the Kalman filter, we develop a rolling horizon approach for RSRP-PdM, in which the predicted health state distributions are updated as new data become available. This approach reduces the uncertainty of the health states and thus improves the decision-making basis for maintenance planning. To solve the instances, we employ a local neighborhood search, which is a modification of a heuristic for RSRP-PdM, and demonstrate its effectiveness. Using this solution algorithm, the presented approach is compared with the results of common maintenance strategies on test instances derived from real-world timetables. The obtained results show the benefits of the rolling horizon approach.}, language = {en} } @inproceedings{BortolettoLindner2025, author = {Bortoletto, Enrico and Lindner, Niels}, title = {Scaling and Rounding Periodic Event Scheduling Instances to Different Period Times}, 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}, doi = {10.1007/978-3-031-58405-3_51}, pages = {397 -- 402}, year = {2025}, abstract = {The Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice.}, language = {en} } @inproceedings{EbertMasingLindneretal.2025, author = {Ebert, Patricia and Masing, Berenike and Lindner, Niels and Gleixner, Ambros}, title = {Sorting Criteria for Line-based Periodic Timetabling Heuristics}, booktitle = {Operations Research Proceedings 2024. OR 2024}, pages = {348 -- 354}, year = {2025}, abstract = {It is well-known that optimal solutions are notoriously hard to find for the Periodic Event Scheduling Problem (PESP), which is the standard mathematical formulation to optimize periodic timetables in public transport. We consider a class of incremental heuristics that have been demonstrated to be effective by Lindner and Liebchen (2023), however, for only one fixed sorting strategy of lines along which a solution is constructed. Thus, in this paper, we examine a variety of sortings based on the number, weight, weighted span, and lower bound of arcs, and test for each setting various combinations of the driving, dwelling, and transfer arcs of lines. Additionally, we assess the impact on the incremental extension of the event-activity network by minimizing resp. maximizing a connectivity measure between subsets of lines. We compare our 27 sortings on the railway instances of the benchmarking library PESPlib within the ConcurrentPESP solver framework. We are able to find five new incumbent solutions, resulting in improvements of up to 2\%.}, language = {en} } @inproceedings{FrankeHamacherManns2026, author = {Franke, Paula and Hamacher, Kay and Manns, Paul}, title = {Minimizing and Maximizing the Shannon Entropy for Fixed Marginals}, booktitle = {Operations Research Proceedings 2025}, year = {2026}, abstract = {The mutual information (MI) between two random variables is an important correlation measure in data analysis. The Shannon entropy of a joint probability distri- bution is the variable part under fixed marginals. We aim to minimize and maximize it to obtain the largest and smallest MI possible in this case, leading to a scaled MI ratio for better comparability. We present algorithmic approaches and optimal solutions for a set of problem instances based on data from molecular evolution. We show that this allows us to construct a sensible, systematic correction to raw MI values.}, language = {en} } @inproceedings{RiccardiLindner2026, author = {Riccardi, Gabor and Lindner, Niels}, title = {On The Minimum-Weight Forward (Weakly) Fundamental Cycle Basis Problem in Directed Graphs}, booktitle = {International Network Optimization Conference 2026 (INOC 2026)}, year = {2026}, abstract = {The cycle space of a directed graph is generated by a cycle basis, where, in general, cycles are allowed to have both forward and backward arcs. In a forward cycle, all arcs have to follow the given direction. We study the existence, structure, and computational complexity of minimum-weight forward cycle bases in directed graphs. We give a complete structural characterization of digraphs that admit weakly fundamental (and hence integral) forward cycle bases, showing that this holds if and only if every block is either strongly connected or a single arc. We further provide an easily verifiable characterization of when a strongly connected digraph admits a forward fundamental cycle basis, proving that such a basis exists if and only if the set of directed cycles has cardinality equal to the cycle rank; in this case, the basis is unique and computable in polynomial time, and nonexistence can likewise be certified efficiently. Lastly, we show that while minimum-weight forward fundamental cycle bases can be found in polynomial time whenever they exist, the minimum-weight forward weakly fundamental cycle basis problem is NP-hard via a polynomial-time reduction from the minimum-weight weakly fundamental cycle basis problem on digraphs with metric weights.}, language = {en} }