@misc{BorndoerferLoebelWeider, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {Integrierte Umlauf- und Dienstplanung im {\"O}ffentlichen Nahverkehr}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6773}, number = {02-10}, abstract = {Wir beschreiben einen Ansatz zur integrierten Umlauf- und Dienstplanung im {\"o}ffentlichen Nahverkehr. Der Ansatz zielt auf die Verbesserung des Gesamtwirkungsgrades dieser beiden Planungsschritte und auf die besondere Planungsproblematik im Regionalverkehr. Wir entwickeln dazu mathematische Optimierungstechniken f{\"u}r den Einsatz in den Planungssystemen MICROBUS II und DIVA.}, language = {de} } @misc{BorndoerferScheltenSchlechteetal., author = {Bornd{\"o}rfer, Ralf and Schelten, Uwe and Schlechte, Thomas and Weider, Steffen}, title = {A Column Generation Approach to Airline Crew Scheduling}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8713}, number = {05-37}, abstract = {The airline crew scheduling problem deals with the construction of crew rotations in order to cover the flights of a given schedule at minimum cost. The problem involves complex rules for the legality and costs of individual pairings and base constraints for the availability of crews at home bases. A typical instance considers a planning horizon of one month and several thousand flights. We propose a column generation approach for solving airline crew scheduling problems that is based on a set partitioning model. We discuss algorithmic aspects such as the use of bundle techniques for the fast, approximate solution of linear programs, a pairing generator that combines Lagrangean shortest path and callback techniques, and a novel rapid branching'' IP heuristic. Computational results for a number of industrial instances are reported. Our approach has been implemented within the commercial crew scheduling system NetLine/Crew of Lufthansa Systems Berlin GmbH.}, language = {en} } @misc{BorndoerferLoebelWeider, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7898}, number = {04-14}, abstract = {This article proposes a Lagrangean relaxation approach to solve integrated duty and vehicle scheduling problems arising in public transport. The approach is based on the proximal bundle method for the solution of concave decomposable functions, which is adapted for the approximate evaluation of the vehicle and duty scheduling components. The primal and dual information generated by the bundle method is used to guide a branch-and-bound type algorithm. Computational results for large-scale real-world integrated vehicle and duty scheduling problems with up to 1,500 timetabled trips are reported. Compared with the results of a classical sequential approach and with reference solutions, integrated scheduling offers remarkable potentials in savings and drivers' satisfaction.}, language = {en} } @misc{KrumkeRambauWeider, author = {Krumke, Sven and Rambau, J{\"o}rg and Weider, Steffen}, title = {An Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6217}, number = {00-53}, abstract = {In the Capacitated Dial-a-Ride Problem (CDARP) we are given a transportation network and a finite set of transportation jobs. Each job specifies the source and target location which are both part of the network. A server which can carry at most \$C\$~objects at a time can move on the transportation network in order to process the transportation requests. The problem CDARP consists of finding a shortest transportation for the jobs starting and ending at a designated start location. In this paper we are concerned with the restriction of CDARP to graphs which are simple paths. This setting arises for instance when modelling applications in elevator transportation systems. It is known that even for this restricted class of graphs CDARP is NP-hard to solve. We provide a polynomial time approximation algorithm that finds a transportion of length at most thrice the length of the optimal transportation.}, language = {en} } @phdthesis{Weider, author = {Weider, Steffen}, title = {Integration of Vehicle and Duty Scheduling in Public Transport}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:83-opus-16240}, abstract = {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.}, language = {en} } @misc{BorndoerferLangenhanLoebeletal., author = {Bornd{\"o}rfer, Ralf and Langenhan, Andreas and L{\"o}bel, Andreas and Schulz, Christof and Weider, Steffen}, title = {Duty Scheduling Templates}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14699}, number = {12-09}, abstract = {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.}, language = {en} } @misc{BorndoerferLoebelReutheretal., author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {Rapid Branching}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14728}, number = {12-10}, abstract = {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.}, language = {en} } @misc{BorndoerferReutherSchlechteetal., author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {Vehicle Rotation Planning for Intercity Railways}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14731}, number = {12-11}, abstract = {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.}, language = {en} } @misc{BorndoerferSchlechteWeider, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Weider, Steffen}, title = {Railway Track Allocation by Rapid Branching}, organization = {Zuse Institut Berlin}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11864}, number = {10-22}, abstract = {The track allocation problem, also known as train routing problem or train timetabling problem, is to find a conflict-free set of train routes of maximum value in a railway network. Although it can be modeled as a standard path packing problem, instances of sizes relevant for real-world railway applications could not be solved up to now. We propose a rapid branching column generation approach that integrates the solution of the LP relaxation of a path coupling formulation of the problem with a special rounding heuristic. The approach is based on and exploits special properties of the bundle method for the approximate solution of convex piecewise linear functions. Computational results for difficult instances of the benchmark library TTPLIB are reported.}, language = {en} } @misc{BorndoerferReutherSchlechteetal., author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {A Hypergraph Model for Railway Vehicle Rotation Planning}, issn = {1438-0064}, doi = {/10.4230/OASIcs.ATMOS.2011.146}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-32746}, number = {11-36}, abstract = {We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the ``regularity'' of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved.}, language = {en} } @article{LangenhanBorndoerferLoebeletal., author = {Langenhan, Andreas and Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Schulz, Christof and Weider, Steffen}, title = {Duty Scheduling Templates}, series = {Proceedings of Conference on Advanced Systems for Public Transport 2012 (CASPT12)}, journal = {Proceedings of Conference on Advanced Systems for Public Transport 2012 (CASPT12)}, editor = {Mu{\~n}oz, J. C. and Voß, S.}, abstract = {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.}, language = {en} } @inproceedings{BorndoerferReutherSchlechteetal.2015, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Schulz, Christof and Swarat, Elmar and Weider, Steffen}, title = {Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue}, series = {Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, booktitle = {Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, year = {2015}, abstract = {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.}, language = {en} } @article{BorndoerferReutherSchlechteetal., author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Waas, Kerstin and Weider, Steffen}, title = {Integrated Optimization of Rolling Stock Rotations for Intercity Railways}, series = {Transportation Science}, volume = {50}, journal = {Transportation Science}, number = {3}, doi = {10.1287/trsc.2015.0633}, pages = {863 -- 877}, abstract = {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.}, language = {en} } @article{BorndoerferReutherSchlechteetal., author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {A Hypergraph Model for Railway Vehicle Rotation Planning}, series = {11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, volume = {OpenAccess Series in Informatics (OASIcs)}, journal = {11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, number = {20}, doi = {10.4230/OASIcs.ATMOS.2011.146}, pages = {146 -- 155}, abstract = {We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the ``regularity'' of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved.}, language = {en} } @article{BorndoerferLoebelReutheretal.2013, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {Rapid Branching}, series = {Public Transport}, volume = {5}, journal = {Public Transport}, number = {1}, editor = {Mu{\~n}oz, J. C. and Voß, S.}, publisher = {Springer Berlin Heidelberg}, pages = {3 -- 23}, year = {2013}, abstract = {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.}, language = {en} } @article{BorndoerferReutherSchlechteetal., author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {Vehicle Rotation Planning for Intercity Railways}, series = {Proceedings of Conference on Advanced Systems for Public Transport 2012 (CASPT12)}, journal = {Proceedings of Conference on Advanced Systems for Public Transport 2012 (CASPT12)}, editor = {Mu{\~n}oz, J. C. and Voß, S.}, abstract = {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.}, language = {en} } @inproceedings{BorndoerferLoebelWeider2008, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit}, series = {Computer-aided Systems in Public Transport}, volume = {600}, booktitle = {Computer-aided Systems in Public Transport}, editor = {Hickman, Mark and Mirchandani, Pitu and Voß, Stefan}, publisher = {Springer-Verlag}, pages = {3 -- 24}, year = {2008}, language = {en} } @inproceedings{BorndoerferSchlechteWeider2010, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Weider, Steffen}, title = {Railway Track Allocation by Rapid Branching}, series = {Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, volume = {14}, booktitle = {Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, editor = {Erlebach, Thomas and L{\"u}bbecke, Marco}, publisher = {Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, doi = {http://dx.doi.org/10.4230/OASIcs.ATMOS.2010.13}, pages = {13 -- 23}, year = {2010}, language = {en} } @inproceedings{BorndoerferGroetschelLoebeletal.2001, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas and Weider, Steffen}, title = {Integrierte Umlauf- und Dienstplanung im {\"o}ffentlichen Nahverkehr}, series = {Neue Mathematische Verfahren in Industrie und Dienstleistungen}, booktitle = {Neue Mathematische Verfahren in Industrie und Dienstleistungen}, year = {2001}, language = {en} } @inproceedings{BorndoerferLoebelWeider2002, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {Integrierte Umlauf- und Dienstplanung im {\"O}ffentlichen Verkehr}, series = {Heureka '02}, booktitle = {Heureka '02}, publisher = {Forschungsgesellschaft f{\"u}r Straßen- und Verkehrswesen}, address = {K{\"o}ln}, pages = {77 -- 98}, year = {2002}, language = {en} } @inproceedings{BorndoerferScheltenSchlechteetal.2006, author = {Bornd{\"o}rfer, Ralf and Schelten, Uwe and Schlechte, Thomas and Weider, Steffen}, title = {A Column Generation Approach to Airline Crew Scheduling}, series = {Operations Research Proceedings 2005}, booktitle = {Operations Research Proceedings 2005}, editor = {Haasis, Hans-Dietrich}, publisher = {Springer-Verlag}, pages = {343 -- 348}, year = {2006}, language = {en} } @misc{BorndoerferReutherSchlechteetal., author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Schulz, Christof and Swarat, Elmar and Weider, Steffen}, title = {Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56070}, abstract = {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.}, language = {en} } @misc{BorndoerferSchulzSeidletal., author = {Bornd{\"o}rfer, Ralf and Schulz, Christof and Seidl, Stephan and Weider, Steffen}, title = {Integration of Duty Scheduling and Rostering to Increase Driver Satisfaction}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56299}, abstract = {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.}, language = {en} } @article{BorndoerferDittbrennerLangenhanetal., author = {Bornd{\"o}rfer, Ralf and Dittbrenner, Bastian and Langenhan, Andreas and Seidl, Stephan and Weider, Steffen}, title = {Integrierte Dienst- und Dienstreihenfolgeplanung zur Erh{\"o}hung der Fahrerzufriedenheit}, series = {Straßenverkehrstechnik}, journal = {Straßenverkehrstechnik}, number = {9}, pages = {583 -- 591}, language = {de} } @article{BorndoerferEsserFrankenbergeretal., author = {Bornd{\"o}rfer, Ralf and Eßer, Thomas and Frankenberger, Patrick and Huck, Andreas and Jobmann, Christoph and Krostitz, Boris and Kuchenbecker, Karsten and Moorhagen, Kai and Nagl, Philipp and Peterson, Michael and Reuther, Markus and Schang, Thilo and Schoch, Michael and Sch{\"u}lldorf, Hanno and Sch{\"u}tz, Peter and Therolf, Tobias and Waas, Kerstin and Weider, Steffen}, title = {Deutsche Bahn Schedules Train Rotations Using Hypergraph Optimization}, series = {Informs Journal on Applied Analytics}, volume = {51}, journal = {Informs Journal on Applied Analytics}, number = {1}, doi = {10.1287/inte.2020.1069}, pages = {42 -- 62}, abstract = {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.}, language = {en} } @inproceedings{GrimmBorndoerferSchulzetal., author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Schulz, Christof and Weider, Steffen}, title = {The Rolling Stock Rotation Planning Problem under Revenue Considerations}, series = {Proceedings of the Rail Transport Demand Management Conference}, booktitle = {Proceedings of the Rail Transport Demand Management Conference}, abstract = {In many railway undertakings a railway timetable is offered that is valid for a longer period of time. At DB Fernverkehr AG, one of our industrial partners, this results in a summer and a winter timetable. For both of these timetables rotation plans, i.e., a detailed plan of railway vehicle movements is constructed as a template for this period. Sometimes there are be periods where you know for sure that vehicle capacities are not sufficient to cover all trips of the timetable or to transport all passenger of the trips. Reasons for that could be a heavy increase of passenger flow, a heavy decrease of vehicle availability, impacts from nature, or even strikes of some employees. In such events the rolling stock rotations have to be adapted. Optimization methods are particularly valuable in such situations in order to maintain a best possible level of service or to maximize the expected revenue using the resources that are still available. In most cases found in the literature, a rescheduling based on a timetable update is done, followed by the construction of new rotations that reward the recovery of parts of the obsolete rotations. We consider a different, novel, and more integrated approach. The idea is to guide the cancellation of the trips or reconfiguration of the vehicle composition used to operate a trip of the timetable by the rotation planning process, which is based on the mixed integer programming approach presented in Reuther (2017). The goal is to minimize the operating costs while cancelling or operating a trip with an insufficient vehicle configuration in sense of passenger capacities inflicts opportunity costs and loss of revenue, which are based on an estimation of the expected number of passengers. The performance of the algorithms presented in two case studies, including real world scenarios from DB Fernverkehr AG and a railway operator in North America.}, language = {en} } @misc{GrimmBorndoerferSchulzetal., author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Schulz, Christof and Weider, Steffen}, title = {The Rolling Stock Rotation Planning Problem under Revenue Considerations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71339}, abstract = {In many railway undertakings a railway timetable is offered that is valid for a longer period of time. At DB Fernverkehr AG, one of our industrial partners, this results in a summer and a winter timetable. For both of these timetables rotation plans, i.e., a detailed plan of railway vehicle movements is constructed as a template for this period. Sometimes there are be periods where you know for sure that vehicle capacities are not sufficient to cover all trips of the timetable or to transport all passenger of the trips. Reasons for that could be a heavy increase of passenger flow, a heavy decrease of vehicle availability, impacts from nature, or even strikes of some employees. In such events the rolling stock rotations have to be adapted. Optimization methods are particularly valuable in such situations in order to maintain a best possible level of service or to maximize the expected revenue using the resources that are still available. In most cases found in the literature, a rescheduling based on a timetable update is done, followed by the construction of new rotations that reward the recovery of parts of the obsolete rotations. We consider a different, novel, and more integrated approach. The idea is to guide the cancellation of the trips or reconfiguration of the vehicle composition used to operate a trip of the timetable by the rotation planning process, which is based on the mixed integer programming approach presented in Reuther (2017). The goal is to minimize the operating costs while cancelling or operating a trip with an insufficient vehicle configuration in sense of passenger capacities inflicts opportunity costs and loss of revenue, which are based on an estimation of the expected number of passengers. The performance of the algorithms presented in two case studies, including real world scenarios from DB Fernverkehr AG and a railway operator in North America.}, language = {en} } @misc{BorndoerferDittbrennerLangenhanetal., author = {Bornd{\"o}rfer, Ralf and Dittbrenner, Bastian and Langenhan, Andreas and Seidl, Stephan and Weider, Steffen}, title = {Integrierte Dienst- und Dienstreihenfolgeplanung zur Erh{\"o}hung der Fahrerzufriedenheit}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-50270}, abstract = {Wir stellen einen mathematischen Optimierungsansatz zur integrierten Dienst- und Dienstreihenfolgeplanung im {\"o}ffentlichen Nahverkehr vor, mit dem sich bei konstanten Personalkosten die Fahrerzufriedenheit deutlich steigern l{\"a}sst.}, language = {de} } @misc{ReutherBorndoerferSchlechteetal., author = {Reuther, Markus and Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Weider, Steffen}, title = {Integrated Optimization of Rolling Stock Rotations for Intercity Railways}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16424}, abstract = {This paper provides a highly integrated solution approach for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a generic hypergraph based mixed integer programming model and an integrated algorithm for the considered rolling stock rotation planning problem. The new developed approach is able to handle a very large set of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacity, and regularity aspects. By the integration of this large bundle of technical railway aspects, we show that our approach has the power to produce implementable rolling stock rotations for our industrial cooperation partner DB Fernverkehr. This is the first time that the rolling stock rotations at DB Fernverkehr could be optimized by an automated system utilizing advanced mathematical programming techniques.}, language = {en} } @inproceedings{LoebelBorndoerferWeider, author = {L{\"o}bel, Fabian and Bornd{\"o}rfer, Ralf and Weider, Steffen}, title = {Non-Linear Charge Functions for Electric Vehicle Scheduling with Dynamic Recharge Rates}, series = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, volume = {115}, booktitle = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, doi = {10.4230/OASIcs.ATMOS.2023.15}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-187765}, pages = {15:1 -- 15:6}, abstract = {The ongoing electrification of logistics systems and vehicle fleets increases the complexity of associated vehicle routing or scheduling problems. Battery-powered vehicles have to be scheduled to recharge in-service, and the relationship between charging time and replenished driving range is non-linear. In order to access the powerful toolkit offered by mixed-integer and linear programming techniques, this battery behavior has to be linearized. Moreover, as electric fleets grow, power draw peaks have to be avoided to save on electricity costs or to adhere to hard grid capacity limits, such that it becomes desirable to keep recharge rates dynamic. We suggest a novel linearization approach of battery charging behavior for vehicle scheduling problems, in which the recharge rates are optimization variables and not model parameters.}, language = {en} } @misc{LoebelBorndoerferWeider, 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}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-92441}, 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{SchlechteBlomeGerberetal., author = {Schlechte, Thomas and Blome, Christian and Gerber, Stefan and Hauser, Stefan and Kasten, Jens and M{\"u}ller, Gilbert and Schulz, Christof and Th{\"u}ring, Michel and Weider, Steffen}, title = {The Bouquet of Features in Rolling Stock Rotation Planning}, series = {Conference Proceedings RailBelgrade 2023}, journal = {Conference Proceedings RailBelgrade 2023}, abstract = {Rolling stock is one of the major assets for a railway transportation company. Hence, their utilization should be as efficiently and effectively as possible. Railway undertakings are facing rolling stock scheduling challenges in different forms - from rather idealized weekly strategic problems to very concrete operational ones. Thus, a vast of optimization models with different features and objectives exist. Thorlacius et al. (2015) provides a comprehensive and valuable collection on technical requirements, models, and methods considered in the scientific literature. We contribute with an update including recent works. The main focus of the paper is to present a classification and elaboration of the major features which our solver R-OPT is able to handle. Moreover, the basic optimization model and algorithmic ingredients of R-OPT are discussed. Finally, we present computational results for a cargo application at SBB CARGO AG and other railway undertakings for passenger traffic in Europe to show the capabilities of R-OPT.}, language = {en} }