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 - THES A1 - Weider, Steffen T1 - Integration of Vehicle and Duty Scheduling in Public Transport N2 - This thesis describes the algorithm IS-OPT that integrates scheduling of vehicles and duties in public bus transit. IS-OPT is the first algorithm which solves integrated vehicle and duty scheduling problems arising in medium sized carriers such that its solutions can be used in daily operations without further adaptions. This thesis is structured as follows: The first chapter highlights mathematical models of the planning process of public transit companies and examines their potential for integrating them with other planning steps. It also introduces descriptions of the vehicle and the duty scheduling problem. Chapter 2 motivates why it can be useful to integrate vehicle and duty scheduling, explains approaches of the literature, and gives an outline of our algorithm IS-OPT. The following chapters go into the details of the most important techniques and methods of IS-OPT: In Chapter 3 we describe how we use Lagrangean relaxation in a column generation framework. Next, in Chapter 4, we describe a variant of the proximal bundle method (PBM) that is used to approximate linear programs occurring in the solution process. We introduce here a new variant of the PBM which is able to utilize inexact function evaluation and the use of epsilon-subgradients. We also show the convergence of this method under certain assumptions. Chapter 5 treats the generation of duties for the duty scheduling problem. This problem is modeled as a resourceconstraint- shortest-path-problem with non-linear side constraints and nearly linear objective function. It is solved in a two-stage approach. At first we calculate lower bounds on the reduced costs of duties using certain nodes by a new inexact label-setting algorithm. Then we use these bounds to speed up a depth-first-search algorithm that finds feasible duties. In Chapter 6 we present the primal heuristic of IS-OPT that solves the integrated problem to integrality. We introduce a new branch-and-bound based heuristic which we call rapid branching. Rapid branching uses the proximal bundle method to compute lower bounds, it introduces a heuristic node selection scheme, and it utilizes a new branching rule that fixes sets of many variables at once. The common approach to solve the problems occurring in IS-OPT is to trade inexactness of the solutions for speed of the algorithms. This enables, as we show in Chapter 7, to solve large real world integrated problems by IS-OPT. The scheduled produced by IS-OPT save up to 5% of the vehicle and duty cost of existing schedules of regional and urban public transport companies. N2 - Diese Arbeit beschreibt den Algorithmus IS-OPT, welcher der erste Algorithmus ist, der integrierte Umlauf- und Dienstplanungsprobleme für mittelgroße Verkehrsunternehmen löst und dabei alle betrieblichen Einzelheiten berücksichtigt. Seine Lösungen können daher direkt in den täglichen Betrieb übernommen werden. Im ersten Kapitel werden mathematische Modelle für verschiedenen Probleme aus dem Planungsprozess von Nahverkehrsunternehmen beschrieben. Es werden Ansätze zur Integration der einzelnen Probleme untersucht. In diesem Kapitel werden außerdem das Umlauf- und das Dienstplanungsproblem eingeführt. Kapitel 2 motiviert, warum Integration von Umlauf- und Dienstplanung hilfreich ist oder in welchen Fällen sie sogar unabdingbar ist; es gibt einen Überblick über die vorhanden Literatur zur integrierten Umlauf- und Dienstplanung und umreißt unseren Algorithmus IS-OPT. Die weiteren Kapitel behandeln die in IS-OPT verwendeten Methoden: In Kapitel 3 beschreiben wir, wie Spaltenerzeugung für lineare Programme mit Lagrange-Relaxierung und Subgradienten-Verfahren kombiniert werden kann. In Kapitel 4 wird unsere Variante der proximalen Bündelmethode beschrieben. Diese wird benutzt um näherungsweise primale und duale Lösungen von lineare Programmen zu berechnen. Unsere Variante ist angepasst, um auch mit ungenauer Funktionsauswertung und Epsilon-Subgradienten arbeiten zu können. Wir zeigen die Konvergenz dieser Variante unter bestimmten Annahmen. Kapitel 5 behandelt das Erzeugen von Diensten für das Dienstplanungsproblem. Dieses Problem ist als ein Kürzeste-Wege-Problem mit nichtlinearen Nebenbedingungen und fast linearer Zielfunktion modelliert. Wir lösen es, indem zuerst Schranken für die reduzierten Kosten von Diensten, die bestimmte Knoten benutzen, berechnet werden. Diese Schranken werden benutzt, um in einem Tiefensuchalgorithmus den Suchbaum klein zu halten. Im Kapitel 6 präsentieren wir die neu entwickelte Heuristik "Rapid Branching", die eine ganzzahlige Lösung des integrierten Problems berechnet. Rapid Branching kann als eine spezielle Branch-and-Bound-Heuristik gesehen werden, welche die Bündelmethode benutzt. In den Knoten des Suchbaums können mehrere Variablen auf einmal fixiert werden, die mit Hilfe einer Perturbationsheuristik ausgewählt werden. In Kapitel 7 schließlich zeigen wir, daß wir mit IS-OPT auch große Probleminstanzen aus der Praxis lösen können und dabei bis zu 5% der Fahrzeug- und Dienstkosten sparen können. KW - Öffentlicher Personennahverkehr KW - lineare Optimierung KW - Umlaufplanung KW - Dienstplanung KW - Integration KW - Public Transport KW - linear Optimization KW - vehicle scheduling KW - duty scheduling KW - integration Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:83-opus-16240 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Dittbrenner, Bastian A1 - Langenhan, Andreas A1 - Seidl, Stephan A1 - Weider, Steffen T1 - Integrierte Dienst- und Dienstreihenfolgeplanung zur Erhöhung der Fahrerzufriedenheit JF - Straßenverkehrstechnik Y1 - 2014 IS - 9 SP - 583 EP - 591 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas A1 - Weider, Steffen T1 - Integrierte Umlauf- und Dienstplanung im öffentlichen Nahverkehr T2 - Neue Mathematische Verfahren in Industrie und Dienstleistungen Y1 - 2001 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Weider, Steffen ED - Erlebach, Thomas ED - Lübbecke, Marco T1 - Railway Track Allocation by Rapid Branching T2 - Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems Y1 - 2010 UR - http://drops.dagstuhl.de/opus/volltexte/2010/2746 U6 - https://doi.org/http://dx.doi.org/10.4230/OASIcs.ATMOS.2010.13 VL - 14 SP - 13 EP - 23 PB - Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik CY - Dagstuhl, Germany ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Weider, Steffen ED - Hickman, Mark ED - Mirchandani, Pitu ED - Voß, Stefan T1 - A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit T2 - Computer-aided Systems in Public Transport Y1 - 2008 UR - http://opus.kobv.de/zib/volltexte/2004/790/ VL - 600 SP - 3 EP - 24 PB - Springer-Verlag ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Schelten, Uwe A1 - Schlechte, Thomas A1 - Weider, Steffen ED - Haasis, Hans-Dietrich T1 - A Column Generation Approach to Airline Crew Scheduling T2 - Operations Research Proceedings 2005 Y1 - 2006 UR - http://opus.kobv.de/zib/volltexte/2005/871/ SP - 343 EP - 348 PB - Springer-Verlag ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Weider, Steffen T1 - Integrierte Umlauf- und Dienstplanung im Öffentlichen Verkehr T2 - Heureka ’02 Y1 - 2002 UR - http://opus.kobv.de/zib/volltexte/2002/678/ SP - 77 EP - 98 PB - Forschungsgesellschaft für Straßen- und Verkehrswesen CY - Köln ER - TY - GEN A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Swarat, Elmar A1 - Weider, Steffen T1 - Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue N2 - Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively. T3 - ZIB-Report - 15-44 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56070 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Dittbrenner, Bastian A1 - Langenhan, Andreas A1 - Seidl, Stephan A1 - Weider, Steffen T1 - Integrierte Dienst- und Dienstreihenfolgeplanung zur Erhöhung der Fahrerzufriedenheit N2 - Wir stellen einen mathematischen Optimierungsansatz zur integrierten Dienst- und Dienstreihenfolgeplanung im öffentlichen Nahverkehr vor, mit dem sich bei konstanten Personalkosten die Fahrerzufriedenheit deutlich steigern lässt. T3 - ZIB-Report - 14-02 KW - duty scheduling KW - duty rostering KW - integrated scheduling KW - Benders' decomposition Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-50270 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Swarat, Elmar A1 - Weider, Steffen T1 - Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue T2 - Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015) N2 - Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively. Y1 - 2015 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Waas, Kerstin A1 - Weider, Steffen T1 - Integrated Optimization of Rolling Stock Rotations for Intercity Railways JF - Transportation Science N2 - This paper proposes a highly integrated solution approach for rolling stock planning problems in the context of long distance passenger traffic between cities. The main contributions are a generic hypergraph-based mixed-integer programming model for the considered rolling stock rotation problem and an integrated algorithm for its solution. The newly developed algorithm is able to handle a large spectrum of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacities, and regularity aspects. We show that our approach has the power to produce rolling stock rotations that can be implemented in practice. In this way, the rolling stock rotations at the largest German long distance operator Deutsche Bahn Fernverkehr AG could be optimized by an automated system utilizing advanced mathematical programming techniques. Y1 - 2016 U6 - https://doi.org/10.1287/trsc.2015.0633 VL - 50 IS - 3 SP - 863 EP - 877 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schulz, Christof A1 - Seidl, Stephan A1 - Weider, Steffen T1 - Integration of Duty Scheduling and Rostering to Increase Driver Satisfaction N2 - Integrated treatment of hitherto individual steps in the planning process of public transit companies discloses opportunities to reduce costs and to improve the quality of service. The arising integrated planning problems are complex and their solution requires the development of novel mathematical methods. This article proposes a mathematical optimization approach to integrate duty scheduling and rostering in public transit, which allows to significantly increase driver satisfaction at almost zero cost. This is important in order to to increase the attractiveness of the driver profession. The integration is based on coupling the subproblems by duty templates, which, compared to a coupling by duties, drastically reduces the problem complexity. T3 - ZIB-Report - 15-50 KW - Benders decomposition KW - driver satisfaction KW - duty templates KW - duty scheduling KW - rostering Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56299 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - Rapid Branching N2 - We propose rapid branching (RB) as a general branch-and-bound heuristic for solving large scale optimization problems in traffic and transport. The key idea is to combine a special branching rule and a greedy node selection strategy in order to produce solutions of controlled quality rapidly and efficiently. We report on three successful applications of the method for integrated vehicle and crew scheduling, railway track allocation, and railway vehicle rotation planning. T3 - ZIB-Report - 12-10 KW - large scale optimization KW - rapid branching KW - column generation Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14728 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - Vehicle Rotation Planning for Intercity Railways N2 - This paper provides a generic formulation for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a graph theoretical model and a Mixed-Integer-Programming formulation that integrate all main requirements of the considered Vehicle-Rotation-Planning problem (VRPP). We show that it is possible to solve this model for real-world instances provided by our industrial partner DB Fernverkehr AG using modern algorithms and computers. T3 - ZIB-Report - 12-11 KW - rolling-stock-planning KW - mixed-integer-programming KW - hypergraphs KW - column generation KW - rapid branching Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14731 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Langenhan, Andreas A1 - Löbel, Andreas A1 - Schulz, Christof A1 - Weider, Steffen T1 - Duty Scheduling Templates N2 - We propose duty templates as a novel concept to produce similar duty schedules for similar days of operation in public transit. Duty templates can conveniently handle various types of similarity requirements, and they can be implemented with ease using standard algorithmic techniques. They have produced good results in practice. T3 - ZIB-Report - 12-09 KW - duty scheduling KW - duty templates Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14699 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 - TY - GEN A1 - Löbel, Fabian A1 - Borndörfer, Ralf A1 - Weider, Steffen T1 - Non-Linear Battery Behavior in Electric Vehicle Scheduling Problems 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. T3 - ZIB-Report - 23-24 KW - Electric Vehicle Scheduling KW - Non-Linear Charging Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-92441 SN - 1438-0064 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Eßer, Thomas A1 - Frankenberger, Patrick A1 - Huck, Andreas A1 - Jobmann, Christoph A1 - Krostitz, Boris A1 - Kuchenbecker, Karsten A1 - Moorhagen, Kai A1 - Nagl, Philipp A1 - Peterson, Michael A1 - Reuther, Markus A1 - Schang, Thilo A1 - Schoch, Michael A1 - Schülldorf, Hanno A1 - Schütz, Peter A1 - Therolf, Tobias A1 - Waas, Kerstin A1 - Weider, Steffen T1 - Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization JF - Informs Journal on Applied Analytics N2 - Deutsche Bahn (DB) operates a large fleet of rolling stock (locomotives, wagons, and train sets) that must be combined into trains to perform rolling stock rotations. This train composition is a special characteristic of railway operations that distinguishes rolling stock rotation planning from the vehicle scheduling problems prevalent in other industries. DB models train compositions using hyperarcs. The resulting hypergraph models are ad-dressed using a novel coarse-to-fine method that implements a hierarchical column genera-tion over three levels of detail. This algorithm is the mathematical core of DB’s fleet em-ployment optimization (FEO) system for rolling stock rotation planning. FEO’s impact within DB’s planning departments has been revolutionary. DB has used it to support the company’s procurements of its newest high-speed passenger train fleet and its intermodal cargo locomotive fleet for cross-border operations. FEO is the key to successful tendering in regional transport and to construction site management in daily operations. DB’s plan-ning departments appreciate FEO’s high-quality results, ability to reoptimize (quickly), and ease of use. Both employees and customers benefit from the increased regularity of operations. DB attributes annual savings of 74 million euro, an annual reduction of 34,000 tons of CO2 emissions, and the elimination of 600 coupling operations in cross-border operations to the implementation of FEO. Y1 - 2021 U6 - https://doi.org/10.1287/inte.2020.1069 VL - 51 IS - 1 SP - 42 EP - 62 ER -