TY - JOUR A1 - Riedmüller, Stephanie A1 - Lindner, Niels T1 - Column Generation for Periodic Timetabling N2 - 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. Y1 - 2025 ER - TY - CHAP A1 - Löbel, Fabian A1 - Lindner, Niels ED - Sauer, Jonas ED - Schmidt, Marie T1 - A Geometric Approach to Integrated Periodic Timetabling and Passenger Routing T2 - 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025) N2 - 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. KW - Periodic Timetabling KW - Passenger Routing KW - Polyhedral Complexes Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-247580 SN - 978-3-95977-404-8 SN - 2190-6807 VL - 137 SP - 2:1 EP - 2:19 PB - Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik CY - Dagstuhl, Germany ER - TY - JOUR A1 - van Lieshout, Rolf A1 - Lindner, Niels T1 - A Compact Cycle Formulation for the Multiperiodic Event Scheduling Problem N2 - 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. Y1 - 2025 ER - TY - GEN A1 - Ebert, Patricia A1 - Schlechte, Thomas A1 - Schwartz, Stephan T1 - Scheduling for German Road Inspectors N2 - 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. T3 - ZIB-Report - 25-13 KW - scheduling KW - rostering KW - mixed-integer linear program KW - crew scheduling KW - hypergraph Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-101999 SN - 1438-0064 ER - TY - CHAP A1 - Lindner, Niels A1 - Liebchen, Christian ED - Voigt, Guido ED - Fliedner, Malte ED - Haase, Knut ED - Brüggemann, Wolfgang ED - Hoberg, Kai ED - Meissner, Jörn T1 - Incremental Heuristics for Periodic Timetabling T2 - Operations Research Proceedings 2023 N2 - 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. Y1 - 2025 U6 - https://doi.org/10.1007/978-3-031-58405-3_59 SP - 461 EP - 467 PB - Springer Nature Switzerland CY - Cham ER - TY - JOUR A1 - Lindner, Niels A1 - Masing, Berenike T1 - On the split closure of the periodic timetabling polytope JF - Mathematical Programming N2 - The Periodic Event Scheduling Problem (PESP) is the central mathematical tool for periodic timetable optimization in public transport. PESP can be formulated in several ways as a mixed-integer linear program with typically general integer variables. We investigate the split closure of these formulations and show that split inequalities are identical with the recently introduced flip inequalities. While split inequalities are a general mixed-integer programming technique, flip inequalities are defined in purely combinatorial terms, namely cycles and arc sets of the digraph underlying the PESP instance. It is known that flip inequalities can be separated in pseudo-polynomial time. We prove that this is best possible unless P = NP, but also observe that the complexity becomes linear-time if the cycle defining the flip inequality is fixed. Moreover, introducing mixed-integer-compatible maps, we compare the split closures of different formulations, and show that reformulation or binarization by subdivision do not lead to stronger split closures. Finally, we estimate computationally how much of the optimality gap of the instances of the benchmark library PESPlib can be closed exclusively by split cuts, and provide better dual bounds for five instances. KW - Periodic event scheduling problem KW - Periodic timetabling KW - Split closure KW - Mixed-integer programming Y1 - 2025 U6 - https://doi.org/10.1007/s10107-025-02220-5 SN - 0025-5610 PB - Springer Science and Business Media LLC ER - TY - GEN A1 - Lindner, Niels A1 - Mehl, Lukas A1 - Bartoszuk, Karolina A1 - Berendes, Sarah A1 - Zittel, Janina T1 - Demand Uncertainty in Energy Systems: Scenario Catalogs vs. Integrated Robust Optimization N2 - 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. T3 - ZIB-Report - 25-19 Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-102404 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels T1 - A Multi-Commodity Flow Heuristic for Integrated Periodic Timetabling for Railway Construction Sites N2 - 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. T3 - ZIB-Report - 25-02 KW - Railway Timetabling KW - Periodic Timetabling KW - Rescheduling KW - Railway Track Allocation Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-99449 SN - 1438-0064 ER - TY - CHAP A1 - Löbel, Fabian A1 - Borndörfer, Ralf A1 - Weider, Steffen ED - Voigt, Guido ED - Fliedner, Malte ED - Haase, Knut ED - Brüggermann, Wolfgang ED - Hoberg, Kai ED - Meissner, Joern T1 - Non-linear Battery Behavior in Electric Vehicle Scheduling Problems T2 - Operations Research Proceedings 2023. OR 2023. N2 - 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. KW - Electric Vehicle Scheduling KW - Non-Linear Charging Y1 - 2025 SN - 9783031584046 U6 - https://doi.org/10.1007/978-3-031-58405-3_53 SN - 2731-040X SP - 415 EP - 421 PB - Springer Nature Switzerland CY - Cham ER - TY - GEN A1 - Lindner, Niels A1 - Liebchen, Christian T1 - A two-stage model for periodic timetabling with fixed line activities N2 - 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. T3 - ZIB-Report - 25-14 Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-101234 SN - 1438-0064 ER - TY - CHAP A1 - Lindner, Niels A1 - Masing, Berenike A1 - Liebchen, Christian T1 - Integrierte Baufahrplanoptimierung auf dem Netz der S-Bahn Berlin T2 - HEUREKA'24 - Optimierung in Verkehr und Transport N2 - Zur Instandhaltung von Eisenbahnnetzen sind regelmäßig Baumaßnahmen erforderlich. Diese erfordern stets Anpassungen der Fahrpläne. Um den Fahrgästen trotz der Baumaßnahme weiterhin einen möglichst großen Teil des Regelangebotes bieten zu können, bewegen sich die resultierenden Baufahrpläne insbesondere in Schnellbahnnetzen mit ihren dichten Zugfolgen häufig nahe der Kapazitätsgrenze der Infrastruktur. Etablierte Verfahren zur Taktfahrplanoptimierung können diesen Anforderungen nicht genügen, da in der Praxis Anpassungen von Laufwegen der Linien, sowie der Gleisbelegungen häufig Teil der realisierten Lösungen sind. Für diese Aufgabe haben die Autoren zuletzt ein Optimierungsmodell vorgestellt, welches diese Möglichkeiten ausschöpft. In dem vorliegenden Beitrag wird erstmalig dessen Anwendung auf ein unmittelbar der Praxis der Baufahrplanung entnommenes Beispiel aus dem Netz der Berliner S-Bahn im Detail beschrieben. Y1 - 2024 VL - 002/140 ER - TY - CHAP A1 - Lindner, Niels A1 - Masing, Berenike T1 - SAT-Generated Initial Solutions for Integrated Line Planning and Turn-Sensitive Periodic Timetabling with Track Choice T2 - hEART 2024: 12th Symposium of the European Association for Research in Transportation N2 - Periodic timetabling is a challenging planning task in public transport. As safety requirements are crucial, track allocation is indispensable for validating the practical feasibility of a railway timetable. For busy stations with limited capacities, this requires a detailed planning of turn-arounds. It is therefore desirable to integrate timetabling not only with track allocation, but also with vehicle scheduling and line planning. This is captured by the Integrated Line Planning and Turn-Sensitive Periodic Timetabling Problem with Track Choice, whose MIP formulation has been demonstrated to be effective for construction site railway rescheduling, as long as a good quality initial solution is available. In this paper, we discuss how to generate such a solution by extending the SAT formulation of the Periodic Event Scheduling Problem with track choice, track occupation, and minimum service frequency components. The SAT approach is superior to pure MIP on real-world instances of the S-Bahn Berlin network. KW - Periodic Timetabling KW - Railway Timetabling KW - Railway Track Allocation KW - Boolean Satisfiability Problem KW - Rescheduling KW - Line Planning Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-98066 UR - https://transp-or.epfl.ch/heart/2024/abstracts/hEART_2024_paper_3685.pdf ER - TY - CHAP A1 - Bortoletto, Enrico A1 - van Lieshout, Rolf Nelson A1 - Masing, Berenike A1 - Lindner, Niels T1 - Periodic Event Scheduling with Flexible Infrastructure Assignment T2 - 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024) N2 - We present novel extensions of the Periodic Event Scheduling Problem (PESP) that integrate the assignment of activities to infrastructure elements. An application of this is railway timetabling, as station and platform capacities are limited and need to be taken into account. We show that an assignment of activities to platforms can always be made periodic, and that it can be beneficial to allow larger periods for the assignment than for the timetable. We present mixed-integer programming formulations for the general problem, as well as for the practically relevant case when multiple platforms can be considered equivalent, for which we present a bipartite matching approach. We finally test and compare these models on real-world instances. Y1 - 2024 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2024.4 VL - 123 SP - 4:1 EP - 4:18 ER - TY - CHAP A1 - Euler, Ricardo A1 - Borndörfer, Ralf A1 - Puchert, Christian A1 - Takkula, Tuomo T1 - ULD Build-Up Scheduling with Logic-Based Benders Decomposition T2 - Integration of Constraint Programming, Artificial Intelligence, and Operations Research N2 - We study a complex planning and scheduling problem arising from the build-up process of air cargo pallets and containers, collectively referred to as unit load devices (ULD), in which ULDs must be assigned to workstations for loading. Since air freight usually becomes available gradually along the planning horizon, ULD build-ups must be scheduled neither too early to avoid underutilizing ULD capacity, nor too late to avoid resource conflicts with other flights. Whenever possible, ULDs should be built up in batches, thereby giving ground handlers more freedom to rearrange cargo and utilize the ULD's capacity efficiently. The resulting scheduling problem has an intricate cost function and produces large time-expanded models, especially for longer planning horizons. We propose a logic-based Benders decomposition approach that assigns batches to time intervals and workstations in the master problem, while the actual schedule is decided in a subproblem. By choosing appropriate intervals, the subproblem becomes a feasibility problem that decomposes over the workstations. Additionally, the similarity of many batches is exploited by a strengthening procedure for no-good cuts. We benchmark our approach against a time-expanded MIP formulation from the literature on a publicly available data set. It solves 15% more instances to optimality and decreases run times by more than 50% in the geometric mean. This improvement is especially pronounced for longer planning horizons of up to one week, where the Benders approach solves over 50% instances more than the baseline Y1 - 2024 U6 - https://doi.org/10.1007/978-3-031-60597-0_17 VL - 14742 SP - 259 EP - 276 ER - TY - JOUR A1 - Euler, Ricardo A1 - Maristany de las Casas, Pedro T1 - Labeling methods for partially ordered paths JF - European Journal of Operational Research N2 - The landscape of applications and subroutines relying on shortest path computations continues to grow steadily. This growth is driven by the undeniable success of shortest path algorithms in theory and practice. It also introduces new challenges as the models and assessing the optimality of paths become more complicated. Hence, multiple recent publications in the field adapt existing labeling methods in an ad hoc fashion to their specific problem variant without considering the underlying general structure: they always deal with multi-criteria scenarios, and those criteria define different partial orders on the paths. In this paper, we introduce the partial order shortest path problem (POSP), a generalization of the multi-objective shortest path problem (MOSP) and in turn also of the classical shortest path problem. POSP captures the particular structure of many shortest path applications as special cases. In this generality, we study optimality conditions or the lack of them, depending on the objective functions’ properties. Our final contribution is a big lookup table summarizing our findings and providing the reader with an easy way to choose among the most recent multi-criteria shortest path algorithms depending on their problems’ weight structure. Examples range from time-dependent shortest path and bottleneck path problems to the electric vehicle shortest path problem with recharging and complex financial weight functions studied in the public transportation community. Our results hold for general digraphs and, therefore, surpass previous generalizations that were limited to acyclic graphs. Y1 - 2024 U6 - https://doi.org/10.1016/j.ejor.2024.05.002 VL - 318 IS - 1 SP - 19 EP - 30 PB - Elsevier BV ET - 1 ER - TY - GEN A1 - Maristany de las Casas, Pedro A1 - Sedeno-Noda, Antonio A1 - Borndörfer, Ralf T1 - An Improved Multiobjective Shortest Path Algorithm N2 - We present a new label-setting algorithm for the Multiobjective Shortest Path (MOSP) problem that computes the minimal complete set of efficient paths for a given instance. The size of the priority queue used in the algorithm is bounded by the number of nodes in the input graph and extracted labels are guaranteed to be efficient. These properties allow us to give a tight output-sensitive running time bound for the new algorithm that can almost be expressed in terms of the running time of Dijkstra's algorithm for the Shortest Path problem. Hence, we suggest to call the algorithm \emph{Multiobjective Dijkstra Algorithm} (MDA). The simplified label management in the MDA allows us to parallelize some subroutines. In our computational experiments, we compare the MDA and the classical label-setting MOSP algorithm by Martins', which we improved using new data structures and pruning techniques. On average, the MDA is $\times2$ to $\times9$ times faster on all used graph types. On some instances the speedup reaches an order of magnitude. T3 - ZIB-Report - 20-26 KW - Multiobjective Shortest Path Problem KW - Output-Sensitive Multiobjective Combinatorial Problems KW - Network Optimization Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-79712 SN - 1438-0064 ER - TY - GEN A1 - Prause, Felix A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Tesch, Alexander T1 - Approximating the RSRP with Predictive Maintenance N2 - 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. T3 - ZIB-Report - 23-04 KW - Rolling Stock Rotation Planning KW - Predictive Maintenance KW - Integer Linear Programming KW - Heuristic KW - Lower Bound Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-89531 SN - 1438-0064 ER - TY - GEN A1 - Prause, Felix T1 - A Multi-Swap Heuristic for Rolling Stock Rotation Planning with Predictive Maintenance N2 - 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. T3 - ZIB-Report - 23-29 KW - Rolling stock rotation planning KW - Predictive maintenance KW - Heuristic KW - State-expanded graph model KW - Integer linear program Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-93133 SN - 1438-0064 ER - TY - GEN A1 - Löbel, Fabian A1 - Borndörfer, Ralf A1 - Weider, Steffen T1 - Electric Bus Scheduling with Non-Linear Charging, Power Grid Bottlenecks, and Dynamic Recharge Rates N2 - Public transport operators are gradually electrifying their bus fleets, predominantly with battery-powered drive trains. These buses commonly have to be scheduled to recharge in-service, which gives rise to a number of challenges. A major problem is that the relationship between charging time and replenished driving range is non-linear, which is often approximately modeled. We examine the associated approximation error and show how it can result in a gross over- or underestimation of the fleet size. Moreover, we demonstrate that commonly used piecewise linear underestimations of the charge curve do not result in an underestimation of the predicted charge states in electric vehicle scheduling and routing models. Furthermore, since power grid upgrades are currently not keeping up with an ever growing electricity demand, operators are introducing active charge management tools to dynamically adjust the charging speed depending on the amount of available energy. It is therefore imperative to extend electric bus scheduling models to account for these developments. We propose a novel mixed-integer programming formulation for the electric bus scheduling problem featuring an improved approximation of the non-linear battery charging behavior as well as dynamic recharge speeds to accommodate grid load limits. The idea is to linearly interpolate what we call the charge increment function, which is closely related to the derivative of the commonly used charge curve. This provides very good error control and integrates easily into integer programming models. We demonstrate the practical usefulness of our model on a diverse library of real-life instances. Y1 - 2024 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Löbel, Fabian A1 - Weider, Steffen T1 - Solving the Electric Bus Scheduling Problem by an Integrated Flow and Set Partitioning Approach T2 - 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024) N2 - Attractive and cost-efficient public transport requires solving computationally difficult optimization problems from network design to crew rostering. While great progress has been made in many areas, new requirements to handle increasingly complex constraints are constantly coming up. One such challenge is a new type of resource constraints that are used to deal with the state-of-charge of battery-electric vehicles, which have limited driving ranges and need to be recharged in-service. Resource constrained vehicle scheduling problems can classically be modelled in terms of either a resource constrained (multi-commodity) flow problem or in terms of a path-based set partition problem. We demonstrate how a novel integrated version of both formulations can be leveraged to solve resource constrained vehicle scheduling with replenishment in general and the electric bus scheduling problem in particular by Lagrangian relaxation and the proximal bundle method. Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-211992 VL - 123 SP - 11:1 EP - 11:16 PB - Schloss Dagstuhl -- Leibniz-Zentrum für Informatik CY - Dagstuhl, Germany ER -