@misc{LindnerMehlBartoszuketal.2025, author = {Lindner, Niels and Mehl, Lukas and Bartoszuk, Karolina and Berendes, Sarah and Zittel, Janina}, title = {Demand Uncertainty in Energy Systems: Scenario Catalogs vs. Integrated Robust Optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-102404}, year = {2025}, abstract = {Designing efficient energy systems is indispensable for shaping a more sustainable society. This involves making infrastructure investment decisions that must be valid for a long-term time horizon. While energy system optimization models constitute a powerful technique to support planning decisions, they need to cope with inherent uncertainty. For example, predicting future demand on a scale of decades is not only an intricate challenge in itself, but small fluctuations in such a forecast might also largely impact the layout of a complex energy system. In this paper, we compare two methodologies of capturing demand uncertainty for linear-programming based energy system optimization models. On one hand, we generate and analyze catalogs of varying demand scenarios, where each individual scenario is considered independently, so that the optimization produces scenario-specific investment pathways. On the other hand, we make use of robust linear programming to meet the demand of all scenarios at once. Since including a multitude of scenarios increases the size and complexity of the optimization model, we will show how to use warm-starting approaches to accelerate the computation process, by exploiting the similar structure of the linear program across different demand inputs. This allows to integrate a meaningful number of demand scenarios with fully-fledged energy system models. We demonstrate the practical use of our methods in a case study of the Berlin-Brandenburg area in Germany, a region that contains both a metropolitan area and its rural surroundings. As a backbone, we use the open-source framework oemof to create a sector-coupled optimization model for planning an energy system with up to 100\% reduction of greenhouse gas emissions. This model features a fine-grained temporal resolution of one hour for the full year 2050. We consider uncertainty in demand for electricity, hydrogen, natural gas, central, and decentral heat. Based on our computations, we analyze the trade-offs in terms of quality and computation time for scenario catalogs and the robust optimization approach. We further demonstrate that our procedure provides a valuable strategy for decision makers to gain insight on the robustness and sensitivity of solutions regarding demand variability.}, 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} } @misc{LindnerLiebchen2025, author = {Lindner, Niels and Liebchen, Christian}, title = {A two-stage model for periodic timetabling with fixed line activities}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-101234}, year = {2025}, abstract = {The timetable is a central pillar of any public transportation system. Constructing and optimizing periodic timetables in terms of passenger comfort and operational efficiency leads to NP-hard optimization problems that are also computationally challenging in applications. The Periodic Event Scheduling Problem (PESP) as standard mathematical tool benefits from its succinct formulation and rich combinatorial structure, but suffers from poor linear programming relaxations and weak dual bounds. These difficulties persist in a reduced version, where driving and dwelling activities of the lines are assumed to be fixed. In this case, fixing the initial departure time of each line fully determines the timetable, and for each pair of lines, the resulting (weighted) transfer durations can be expressed in terms of a piecewise linear non-convex function in terms of the difference of the initial times. When the number of activities between two lines is bounded, this function can be computed in polynomial time. By inserting precomputed piecewise linear functions into a mixed-integer program with the initial departure times as variables, we introduce an equivalent formulation for reduced PESP instances. The model bears analogies with quadratic semi-assignment approaches and offers alternative ways to compute primal and dual bounds. We evaluate the computational behavior of our approach on realistic benchmarking instances.}, language = {en} } @misc{Lindner2025, author = {Lindner, Niels}, title = {A Multi-Commodity Flow Heuristic for Integrated Periodic Timetabling for Railway Construction Sites}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-99449}, year = {2025}, abstract = {Rescheduling a railway system comprises many aspects, such as line planning, timetabling, track allocation, and vehicle scheduling. For periodic timetables, these features can be integrated into a single mixed-integer program extending the Periodic Event Scheduling Problem (PESP) with a routing component. We develop a multi-commodity-flow-based heuristic that allows to compute better solutions faster than a black-box MIP approach on real construction site scenarios on the S-Bahn Berlin network.}, language = {en} } @misc{Prause2023, author = {Prause, Felix}, title = {A Multi-Swap Heuristic for Rolling Stock Rotation Planning with Predictive Maintenance}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-93133}, year = {2023}, abstract = {We present a heuristic solution approach for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). The task of this problem is to assign a sequence of trips to each of the vehicles and to schedule their maintenance such that all trips can be operated. Here, the health states of the vehicles are considered to be random variables distributed by a family of probability distribution functions, and the maintenance services should be scheduled based on the failure probability of the vehicles. The proposed algorithm first generates a solution by solving an integer linear program and then heuristically improves this solution by applying a local search procedure. For this purpose, the trips assigned to the vehicles are split up and recombined, whereby additional deadhead trips can be inserted between the partial assignments. Subse- quently, the maintenance is scheduled by solving a shortest path problem in a state-expanded version of a space-time graph restricted to the trips of the individual vehicles. The solution approach is tested and evaluated on a set of test instances based on real-world timetables.}, language = {en} } @misc{LoebelBorndoerferWeider2023, author = {L{\"o}bel, Fabian and Bornd{\"o}rfer, Ralf and Weider, Steffen}, title = {Non-Linear Battery Behavior in Electric Vehicle Scheduling Problems}, issn = {1438-0064}, doi = {10.1007/978-3-031-58405-3_53}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-92441}, year = {2023}, abstract = {The currently most popular approach to handle non-linear battery behavior for electric vehicle scheduling is to use a linear spline interpolation of the charge curve. We show that this can lead to approximate models that underestimate the charge duration and overestimate the state of charge, which is not desirable. While the error is of second order with respect to the interpolation step size, the associated mixed-integer linear programs do not scale well with the number of spline segments. It is therefore recommendable to use coarse interpolation grids adapted to the curvature of the charge curve, and to include sufficient safety margins to ensure solutions of approximate models remain feasible subjected to the exact charge curve.}, language = {en} } @misc{PrauseBorndoerfer2023, author = {Prause, Felix and Bornd{\"o}rfer, Ralf}, title = {Construction of a Test Library for the Rolling Stock Rotation Problem with Predictive Maintenance}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91734}, year = {2023}, abstract = {We describe the development of a test library for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). Our approach involves the utilization of genuine timetables from a private German railroad company. The generated instances incorporate probability distribution functions for modeling the health states of the vehicles and the considered trips possess varying degradation functions. RSRP-PdM involves assigning trips to a fleet of vehicles and scheduling their maintenance based on their individual health states. The goal is to minimize the total costs consisting of operational costs and the expected costs associated with vehicle failures. The failure probability is dependent on the health states of the vehicles, which are assumed to be random variables distributed by a family of probability distributions. Each distribution is represented by the parameters characterizing it and during the operation of the trips, these parameters get altered. Our approach incorporates non-linear degradation functions to describe the inference of the parameters but also linear ones could be applied. The resulting instances consist of the timetables of the individual lines that use the same vehicle type. Overall, we employ these assumptions and utilize open-source data to create a library of instances with varying difficulty. Our approach is vital for evaluating and comparing algorithms designed to solve the RSRP-PdM.}, language = {en} } @misc{TjusilaBesanconTurneretal.2023, author = {Tjusila, Gennesaret and Besancon, Mathieu and Turner, Mark and Koch, Thorsten}, title = {How Many Clues To Give? A Bilevel Formulation For The Minimum Sudoku Clue Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-90902}, year = {2023}, abstract = {It has been shown that any 9 by 9 Sudoku puzzle must contain at least 17 clues to have a unique solution. This paper investigates the more specific question: given a particular completed Sudoku grid, what is the minimum number of clues in any puzzle whose unique solution is the given grid? We call this problem the Minimum Sudoku Clue Problem (MSCP). We formulate MSCP as a binary bilevel linear program, present a class of globally valid inequalities, and provide a computational study on 50 MSCP instances of 9 by 9 Sudoku grids. Using a general bilevel solver, we solve 95\\% of instances to optimality, and show that the solution process benefits from the addition of a moderate amount of inequalities. Finally, we extend the proposed model to other combinatorial problems in which uniqueness of the solution is of interest.}, language = {en} } @misc{SchieweGoerigkLindner2023, author = {Schiewe, Philine and Goerigk, Marc and Lindner, Niels}, title = {Introducing TimPassLib - A library for integrated periodic timetabling and passenger routing}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89741}, year = {2023}, abstract = {Classic models to derive a timetable for public transport often face a chicken-and-egg situation: A good timetable should offer passengers routes with small travel times, but the route choice of passengers depends on the timetable. While models that fix passenger routes were frequently considered in the literature, integrated models that simultaneously optimize timetables and passenger routes have seen increasing attention lately. This creates a growing need for a set of instances that allows to test and compare new algorithmic developments for the integrated problem. Our paper addresses this requirement by presenting TimPassLib, a new benchmark library of instances for integrated periodic timetabling and passenger routing.}, language = {en} } @misc{PrauseBorndoerferGrimmetal.2023, author = {Prause, Felix and Bornd{\"o}rfer, Ralf and Grimm, Boris and Tesch, Alexander}, title = {Approximating the RSRP with Predictive Maintenance}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89531}, year = {2023}, abstract = {We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for two instances derived from real world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions.}, language = {en} }