@misc{BorndoerferKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {Neue Planungsinstrumente nutzen: Das Verkehrsangebot verbessern und Kosten sparen}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55439}, year = {2015}, abstract = {Wir illustrieren anhand des Liniennetzes der Stadt Potsdam das Potenzial mathematischer Methoden der Angebotsplanung. Wir zeigen, dass das "bestm{\"o}gliche" Verkehrsangebot stark von planerischen Vorgaben beeinflusst wird, mit denen man die Erreichung unterschiedlicher und teilweise gegenl{\"a}ufiger Ziele steuern kann. Die Komplexit{\"a}t des Systems f{\"u}hrt zum Auftreten von R{\"u}ckkoppelungseffekten, die man nicht mit Hilfe von Daumenregeln beherrschen kann. Vielmehr ist der Einsatz moderner Planungsverfahren in einer interdisziplin{\"a}ren Zusammenarbeit von politischen Entscheidungstr{\"a}gern, Verkehrsingenieuren und Mathematikern notwendig, um die aktuellen Herausforderungen in der Verkehrsplanung zu meistern. Der Artikel dokumentiert einen Beitrag zum 7. {\"O}PNV Innovationskongress des Ministeriums f{\"u}r Verkehr und Infrastruktur des Landes Baden-W{\"u}rttemberg, der vom 9.-11. M{\"a}rz 2015 in Freiburg stattfand.}, language = {de} } @misc{BorndoerferHoppmannKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Timetabling and Passenger Routing in Public Transport}, journal = {Appeard in: Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-55305}, year = {2015}, abstract = {The task of timetabling is to schedule the trips in a public transport system by determining periodic arrival and departure times at every station. The goal is to provide a service that is both attractive for passengers and can be operated economically. To date, timetable optimization is generally done with respect to fixed passenger routes, i.e., it is assumed that passengers do not respond to changes in the timetable. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We propose several models that differ in the allowed passenger paths and the objectives. We compare these models theoretically and report on computations on real-world instances for the city of Wuppertal.}, language = {en} } @article{D'AndreagiovanniNardin2015, author = {D'Andreagiovanni, Fabio and Nardin, Antonella}, title = {Towards the fast and robust optimal design of Wireless Body Area Networks}, volume = {37}, journal = {Applied Soft Computing}, publisher = {Elsevier}, doi = {10.1016/j.asoc.2015.04.037}, pages = {971 -- 982}, year = {2015}, abstract = {Wireless body area networks are wireless sensor networks whose adoption has recently emerged and spread in important healthcare applications, such as the remote monitoring of health conditions of patients. A major issue associated with the deployment of such networks is represented by energy consumption: in general, the batteries of the sensors cannot be easily replaced and recharged, so containing the usage of energy by a rational design of the network and of the routing is crucial. Another issue is represented by traffic uncertainty: body sensors may produce data at a variable rate that is not exactly known in advance, for example because the generation of data is event-driven. Neglecting traffic uncertainty may lead to wrong design and routing decisions, which may compromise the functionality of the network and have very bad effects on the health of the patients. In order to address these issues, in this work we propose the first robust optimization model for jointly optimizing the topology and the routing in body area networks under traffic uncertainty. Since the problem may result challenging even for a state-of-the-art optimization solver, we propose an original optimization algorithm that exploits suitable linear relaxations to guide a randomized fixing of the variables, supported by an exact large variable neighborhood search. Experiments on realistic instances indicate that our algorithm performs better than a state-of-the-art solver, fast producing solutions associated with improved optimality gaps.}, language = {en} } @article{MaherMurray2016, author = {Maher, Stephen J. and Murray, John M.}, title = {The unrooted set covering connected subgraph problem differentiating between HIV envelope sequences}, volume = {248}, journal = {European Journal of Operational Research}, number = {2}, doi = {doi:10.1016/j.ejor.2015.07.011}, pages = {668 -- 680}, year = {2016}, abstract = {This paper presents a novel application of operations research techniques to the analysis of HIV Env gene sequences, aiming to identify key features that are possible vaccine targets. These targets are identified as being critical to the transmission of HIV by being present in early transmitted (founder) sequences and absent in later chronic sequences. Identifying the key features of Env involves two steps: first, calculating the covariance of amino acid combinations and positions to form a network of related and compensatory mutations; and second, developing an integer program to identify the smallest connected subgraph of the constructed covariance network that exhibits a set covering property. The integer program developed for this analysis, labelled the unrooted set covering connected subgraph problem (USCCSP), integrates a set covering problem and connectivity evaluation, the latter formulated as a network flow problem. The resulting integer program is very large and complex, requiring the use of Benders' decomposition to develop an efficient solution approach. The results will demonstrate the necessity of applying acceleration techniques to the Benders' decomposition solution approach and the effectiveness of these techniques and heuristic approaches for solving the USCCSP.}, language = {en} } @inproceedings{GamrathHillerWitzig2015, author = {Gamrath, Gerald and Hiller, Benjamin and Witzig, Jakob}, title = {Reoptimization Techniques in MIP Solvers}, volume = {9125}, edition = {Experimental Algorithms, Lecture Notes in Computer Science}, publisher = {Springer}, isbn = {978-3-319-20086-6}, doi = {10.1007/978-3-319-20086-6_14}, pages = {181 -- 192}, year = {2015}, abstract = {Recently, there have been many successful applications of optimization algorithms that solve a sequence of quite similar mixed-integer programs (MIPs) as subproblems. Traditionally, each problem in the sequence is solved from scratch. In this paper we consider reoptimization techniques that try to benefit from information obtained by solving previous problems of the sequence. We focus on the case that subsequent MIPs differ only in the objective function or that the feasible region is reduced. We propose extensions of the very complex branch-and-bound algorithms employed by general MIP solvers based on the idea to ``warmstart'' using the final search frontier of the preceding solver run. We extend the academic MIP solver SCIP by these techniques to obtain a reoptimizing branch-and-bound solver and report computational results which show the effectiveness of the approach.}, language = {en} } @incollection{HillerHaynHeitschetal.2015, author = {Hiller, Benjamin and Hayn, Christine and Heitsch, Holger and Henrion, Ren{\´e} and Le{\"o}vey, Hernan and M{\"o}ller, Andris and R{\"o}misch, Werner}, title = {Methods for verifying booked capacities}, booktitle = {Evaluating gas network capacities}, publisher = {Society for Industrial and Applied Mathematics}, pages = {291 -- 315}, year = {2015}, language = {en} } @misc{GamrathBertholdHeinzetal.2017, author = {Gamrath, Gerald and Berthold, Timo and Heinz, Stefan and Winkler, Michael}, title = {Structure-driven fix-and-propagate heuristics for mixed integer programming}, issn = {1438-0064}, doi = {10.1007/s12532-019-00159-1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-65387}, year = {2017}, abstract = {Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early in the solving process and help to solve instances to optimality faster. In this paper, we present a scheme for primal start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved as an LP and the solution is rounded. If the rounded solution did not provide a feasible solution already, a sub-MIP is solved for the neighborhood defined by the variable fixings performed in the first phase. The global structures help to define a neighborhood that is with high probability significantly easier to process while (hopefully) still containing good feasible solutions. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about three out of five instances and therewith help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.}, language = {en} } @misc{BertholdHendelKoch2016, author = {Berthold, Timo and Hendel, Gregor and Koch, Thorsten}, title = {The Three Phases of MIP Solving}, issn = {1438-0064}, doi = {10.1080/10556788.2017.1392519}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61607}, year = {2016}, abstract = {Modern MIP solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three different phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behavior of the MIP solver SCIP at the predicted phase transition points.}, language = {en} } @misc{HillerKochScheweetal.2017, author = {Hiller, Benjamin and Koch, Thorsten and Schewe, Lars and Schwarz, Robert and Schweiger, Jonas}, title = {A System to Evaluate Gas Network Capacities: Concepts and Implementation}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61931}, year = {2017}, abstract = {Since 2005, the gas market in the European Union is liberalized and the trading of natural gas is decoupled from its transport. The transport is done by so-called transmissions system operators or TSOs. The market model established by the European Union views the gas transmission network as a black box, providing shippers (gas traders and consumers) the opportunity to transport gas from any entry to any exit. TSOs are required to offer maximum independent capacities at each entry and exit such that the resulting gas flows can be realized by the network without compromising security of supply. Therefore, evaluating the available transport capacities is extremely important to the TSOs. This paper gives an overview of the toolset for evaluating gas network capacities that has been developed within the ForNe project, a joint research project of seven research partners initiated by Open Grid Europe, Germany's biggest TSO. While most of the relevant mathematics is described in the book "Evaluating Gas Network Capacities", this article sketches the system as a whole, describes some developments that have taken place recently, and gives some details about the current implementation.}, language = {en} } @misc{GriewankStreubelLehmannetal.2016, author = {Griewank, Andreas and Streubel, Tom and Lehmann, Lutz and Hasenfelder, Richard and Radons, Manuel}, title = {Piecewise linear secant approximation via Algorithmic Piecewise Differentiation}, issn = {1438-0064}, doi = {10.1080/10556788.2017.1387256}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61642}, year = {2016}, abstract = {It is shown how piecewise differentiable functions \(F: R^n → R^m\) that are defined by evaluation programs can be approximated locally by a piecewise linear model based on a pair of sample points x̌ and x̂. We show that the discrepancy between function and model at any point x is of the bilinear order O(||x - x̌|| ||x - x̂||). This is a little surprising since x ∈ R^n may vary over the whole Euclidean space, and we utilize only two function samples F̌ = F(x̌) and F̂ = F(x̂), as well as the intermediates computed during their evaluation. As an application of the piecewise linearization procedure we devise a generalized Newton's method based on successive piecewise linearization and prove for it sufficient conditions for convergence and convergence rates equaling those of semismooth Newton. We conclude with the derivation of formulas for the numerically stable implementation of the aforedeveloped piecewise linearization methods.}, language = {en} } @misc{BorndoerferHoppmannKarbstein2017, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Umsteigen ohne Warten}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62006}, year = {2017}, abstract = {Wir stellen einen mathematischen Optimierungsansatz zur Berechnung von periodischen Taktfahrpl{\"a}nen vor, bei dem die Umsteigezeiten unter Ber{\"u}cksichtigung des Passagierverhaltens minimiert werden. Wir untersuchen damit den Einfluss wichtiger Systemparameter und Verhaltensmuster auf die Bef{\"o}rderungsqualit{\"a}t.}, language = {de} } @article{KickhoeferKern2015, author = {Kickh{\"o}fer, Benjamin and Kern, Julia}, title = {Pricing local emission exposure of road traffic: An agent-based approach}, volume = {37}, journal = {Transportation Research Part D: Transport and Environment}, doi = {10.1016/j.trd.2015.04.019}, pages = {14 -- 28}, year = {2015}, abstract = {This paper proposes a new approach to iteratively calculate local air pollution exposure tolls in large-scale urban settings by taking the exposure times and locations of individuals into consideration. It explicitly avoids detailed air pollution concentration calculations and is therefore characterized by little data requirements, reasonable computation times for iterative calculations, and open-source compatibility. In a first step, the paper shows how to derive time-dependent vehicle-specific exposure tolls in an agent-based model. It closes the circle from the polluting entity, to the receiving entity, to damage costs, to tolls, and back to the behavioral change of the polluting entity. In a second step, the approach is applied to a large-scale real-world scenario of the Munich metropolitan area in Germany. Changes in emission levels, exposure costs, and user benefits are calculated. These figures are compared to a flat emission toll, and to a regulatory measure (a speed reduction in the inner city), respectively. The results indicate that the flat emission toll reduces overall emissions more significantly than the exposure toll, but its exposure cost reductions are rather small. For the exposure toll, overall emissions increase for freight traffic which implies a potential conflict between pricing schemes to optimize local emission exposure and others to abate climate change. Regarding the mitigation of exposure costs caused by urban travelers, the regulatory measure is found to be an effective strategy, but it implies losses in user benefits.}, language = {en} } @article{BorndoerferGrimmReutheretal.2017, author = {Bornd{\"o}rfer, Ralf and Grimm, Boris and Reuther, Markus and Schlechte, Thomas}, title = {Template-based Re-optimization of Rolling Stock Rotations}, journal = {Public Transport}, publisher = {Springer}, doi = {10.1007/s12469-017-0152-4}, pages = {1 -- 19}, year = {2017}, abstract = {Rolling stock, i.e., the set of railway vehicles, is among the most expensive and limited assets of a railway company and must be used efficiently. We consider in this paper the re-optimization problem to recover from unforeseen disruptions. We propose a template concept that allows to recover cost minimal rolling stock rotations from reference rotations under a large variety of operational requirements. To this end, connection templates as well as rotation templates are introduced and their application within a rolling stock rotation planning model is discussed. We present an implementation within the rolling stock rotation optimization framework rotor and computational results for scenarios provided by DB Fernverkehr AG, one of the leading railway operators in Europe.}, language = {en} } @incollection{SchenkerVierhausBorndoerferetal.2017, author = {Schenker, Sebastian and Vierhaus, Ingmar and Bornd{\"o}rfer, Ralf and F{\"u}genschuh, Armin and Skutella, Martin}, title = {Optimisation Methods in Sustainable Manufacturing}, booktitle = {Sustainable Manufacturing}, editor = {Stark, Rainer and Seliger, G{\"u}nther and Bonvoisin, J{\´e}r{\´e}my}, publisher = {Springer International Publishing}, isbn = {978-3-319-48514-0}, doi = {10.1007/978-3-319-48514-0_15}, pages = {239 -- 253}, year = {2017}, abstract = {Sustainable manufacturing is driven by the insight that the focus on the economic dimension in current businesses and lifestyles has to be broadened to cover all three pillars of sustainability: economic development, social development, and environmental protection.}, language = {en} } @misc{Gamrath2016, type = {Master Thesis}, author = {Gamrath, Gerwin}, title = {A Coarse-to-Fine Approach for the Workforce Scheduling of Teams}, pages = {72}, year = {2016}, abstract = {We present a coarse-to-fine column generation approach for the workforce scheduling of teams. In addition we present a price-and-branch approach and a new hypergraph formulation for a specific workforce team problem, called the Toll Enforcement Problem.}, language = {en} } @article{Tesch2016, author = {Tesch, Alexander}, title = {Kompakte MIP Modelle f{\"u}r das Ressourcenbeschr{\"a}nkte Projektplanungsproblem}, volume = {58}, journal = {OR News}, pages = {19 -- 21}, year = {2016}, language = {de} } @misc{MaherDesaulniersSoumis2015, author = {Maher, Stephen J. and Desaulniers, Guy and Soumis, Francois}, title = {The tail assignment problem with look-ahead maintenance constraints}, issn = {1438-0064}, doi = {10.1016/j.ejor.2017.06.041}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56717}, year = {2015}, abstract = {The tail assignment problem is a critical part of the airline planning process that assigns specific aircraft to sequences of flights, called lines-of-flight, to be operated the next day. The aim of this paper is to develop an operationally flexible tail assignment that satisfies short-range---within the next three days---aircraft maintenance requirements and performs the aircraft/flight gate assignment for each input line-of-flight. While maintenance plans commonly span multiple days, the related tail assignment problems can be overly complex and provide little recourse in the event of schedule perturbations. The presented approach addresses operational uncertainty by extending the one-day routes aircraft maintenance routing approach to satisfy maintenance requirements explicitly for the current day and implicitly for the subsequent two days. A mathematical model is presented that integrates the gate assignment and maintenance planning problems. To increase the satisfaction of maintenance requirements, an iterative algorithm is developed that modifies the fixed lines-of-flight provided as input to the tail assignment problem. The tail assignment problem and iterative algorithm are demonstrated to effectively satisfy maintenance requirements within appropriate run times using input data collected from three different airlines.}, language = {en} } @misc{AhmadiGritzbachLundNguyenetal.2015, author = {Ahmadi, Sepideh and Gritzbach, Sascha F. and Lund-Nguyen, Kathryn and McCullough-Amal, Devita}, title = {Rolling Stock Rotation Optimization in Days of Strike: An Automated Approach for Creating an Alternative Timetable}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56425}, year = {2015}, abstract = {The operation of a railway network as large as Deutsche Bahn's Intercity Express (ICE) hinges on a number of factors, such as the availability of personnel and the assignment of physical vehicles to a timetable schedule, a problem known as the rolling stock rotation problem (RSRP). In this paper, we consider the problem of creating an alternative timetable in the case that there is a long-term disruption, such as a strike, and the effects that this alternative timetable has on the resulting vehicle rotation plan. We define a priority measure via the Analytic Hierarchy Process (AHP) to determine the importance of each trip in the timetable and therefore which trips to cancel or retain. We then compare our results with those of a limited timetable manually designed by Deutsche Bahn (DB). We find that while our timetable results in a more expensive rotation plan, its flexibility lends itself to a number of simple improvements. Furthermore, our priority measure has the potential to be integrated into the rolling stock rotation optimization process, in particular, the Rotation Optimizer for Railways (ROTOR) software, via the cost function. Ultimately, our method provides the foundation for an automated way of creating a new timetable quickly, and potentially in conjunction with a new rotation plan, in the case of a limited scenario.}, language = {en} } @misc{LeitnerLjubicSinnletal.2015, author = {Leitner, Markus and Ljubic, Ivana and Sinnl, Markus and Werner, Axel}, title = {Two algorithms for solving 3-objective k-ArchConFL and IPs in general}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56259}, year = {2015}, abstract = {We present two algorithms to solve a 3-objective optimization problem arising in telecommunications access network planning, the k-Architecture Connected Facility Location Problem. The methods can also be used to solve any 3-objective integer linear programming model and can be extended to the multiobjective case. We give some exemplary computations using small and medium-sized instances for our problem.}, language = {en} } @misc{BorndoerferSchulzSeidletal.2015, 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}, year = {2015}, 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} } @misc{BeckenbachBorndoerfer2015, author = {Beckenbach, Isabel and Bornd{\"o}rfer, Ralf}, title = {A Hall Condition for Normal Hypergraphs}, issn = {1438-0064}, doi = {10.1016/j.disc.2018.06.013}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56175}, year = {2015}, abstract = {Conforti, Cornu{\´e}jols, Kapoor, and Vusković gave a Hall-type condition for the non-existence of a perfect matching in a balanced hypergraph. We generalize this result to the class of normal hypergraphs.}, language = {en} } @inproceedings{DraegertEisenblaetterGamrathetal.2015, author = {Draegert, Andreas and Eisenbl{\"a}tter, Andreas and Gamrath, Inken and Werner, Axel}, title = {Optimal battery control for smart grid nodes}, volume = {13}, booktitle = {Optimization in the Real World - Towards Solving Real-World Optimization Problems}, editor = {Fujisawa, Katsuki and Shinano, Yuji and Waki, Hayato}, publisher = {Springer}, doi = {10.1007/978-4-431-55420-2_6}, pages = {97 -- 113}, year = {2015}, abstract = {Energy storages can be of great value when added to power grids. They introduce the possibility to store and release energy whenever this is favorable. This is particularly relevant, for example, if power supply is volatile (as is the case with renewable energy) and the network is small (so that there are few other nodes that might balance fluctuations in consumption or production). We present models and methods from mathematical optimization for computing an optimized storage schedule for this purpose. We look at alternative optimization objectives, such as smallest possible peak load, low energy costs, or the close approximation of a prescribed load curve. The optimization needs to respect general operational and economic constraints as well as limitations in the use of storage, which are imposed by the chosen storage technology. We therefore introduce alternative approaches for modeling the non-linear properties of energy storages and study their impact on the efficiency of the optimization process. Finally, we present a computational study with batteries as storage devices. We use this to highlight the trade-off between solution quality and computational tractability. A version of the model for the purpose of leveling peaks and instabilities has been implemented into a control system for an office-building smart grid scenario.}, language = {en} } @article{GamrathKochMartinetal.2015, author = {Gamrath, Gerald and Koch, Thorsten and Martin, Alexander and Miltenberger, Matthias and Weninger, Dieter}, title = {Progress in presolving for mixed integer programming}, volume = {7}, journal = {Mathematical Programming Computation}, number = {4}, doi = {10.1007/s12532-015-0083-5}, pages = {367 -- 398}, year = {2015}, abstract = {This paper describes three presolving techniques for solving mixed integer programming problems (MIPs) that were implemented in the academic MIP solver SCIP. The task of presolving is to reduce the problem size and strengthen the formulation, mainly by eliminating redundant information and exploiting problem structures. The first method fixes continuous singleton columns and extends results known from duality fixing. The second analyzes and exploits pairwise dominance relations between variables, whereas the third detects isolated subproblems and solves them independently. The performance of the presented techniques is demonstrated on two MIP test sets. One contains all benchmark instances from the last three MIPLIB versions, while the other consists of real-world supply chain management problems. The computational results show that the combination of all three presolving techniques almost halves the solving time for the considered supply chain management problems. For the MIPLIB instances we obtain a speedup of 20 \% on affected instances while not degrading the performance on the remaining problems.}, language = {en} } @article{BorndoerferKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {Neue Planungsinstrumente nutzen: Das Verkehrsangebot verbessern und Kosten sparen}, volume = {68}, journal = {Verkehr und Technik}, number = {7}, pages = {239 -- 243}, year = {2015}, abstract = {Wir illustrieren anhand des Liniennetzes der Stadt Potsdam das Potenzial mathematischer Methoden der Angebotsplanung. Wir zeigen, dass das "bestm{\"o}gliche" Verkehrsangebot stark von planerischen Vorgaben beeinflusst wird, mit denen man die Erreichung unterschiedlicher und teilweise gegenl{\"a}ufiger Ziele steuern kann. Die Komplexit{\"a}t des Systems f{\"u}hrt zum Auftreten von R{\"u}ckkoppelungseffekten, die man nicht mit Hilfe von Daumenregeln beherrschen kann. Vielmehr ist der Einsatz moderner Planungsverfahren in einer interdisziplin{\"a}ren Zusammenarbeit von politischen Entscheidungstr{\"a}gern, Verkehrsingenieuren und Mathematikern notwendig, um die aktuellen Herausforderungen in der Verkehrsplanung zu meistern. Der Artikel dokumentiert einen Beitrag zum 7. {\"O}PNV Innovationskongress des Ministeriums f{\"u}r Verkehr und Infrastruktur des Landes Baden-W{\"u}rttemberg, der vom 9.-11. M{\"a}rz 2015 in Freiburg stattfand.}, language = {de} } @inproceedings{BorndoerferHoppmannKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Timetabling and Passenger Routing in Public Transport}, booktitle = {Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, year = {2015}, abstract = {The task of timetabling is to schedule the trips in a public transport system by determining periodic arrival and departure times at every station. The goal is to provide a service that is both attractive for passengers and can be operated economically. To date, timetable optimization is generally done with respect to fixed passenger routes, i.e., it is assumed that passengers do not respond to changes in the timetable. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We propose several models that differ in the allowed passenger paths and the objectives. We compare these models theoretically and report on computations on real-world instances for the city of Wuppertal.}, language = {en} } @misc{BorndoerferSagnolSchlechteetal.2013, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schlechte, Thomas and Swarat, Elmar}, title = {Optimal Toll Enforcement - an Integration of Vehicle Routing and Duty Rostering}, issn = {1438-0064}, doi = {10.1007/s10479-016-2152-1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-45107}, year = {2013}, abstract = {We present the problem of planning mobile tours of inspectors on German motorways to enforce the payment of the toll for heavy good trucks. This is a special type of vehicle routing problem with the objective to conduct as good inspections as possible on the complete network. In addition, the crews of the tours have to be scheduled. Thus, we developed a personalized crew rostering model. The planning of daily tours and the rostering are combined in a novel integrated approach and formulated as a complex and large scale Integer Program. The paper focuses first on different requirements for the rostering and how they can be modeled in detail. The second focus is on a bicriterion analysis of the planning problem to find the balance between the control quality and the roster acceptance. On the one hand the tour planning is a profit maximization problem and on the other hand the rostering should be made in a employee friendly way. Finally, computational results on real-world instances show the practicability of our method.}, language = {en} } @misc{SagnolHarman2014, author = {Sagnol, Guillaume and Harman, Radoslav}, title = {Optimal Designs for Steady-state Kalman filters}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52808}, year = {2014}, abstract = {We consider a stationary discrete-time linear process that can be observed by a finite number of sensors. The experimental design for the observations consists of an allocation of available resources to these sensors. We formalize the problem of selecting a design that maximizes the information matrix of the steady-state of the Kalman filter, with respect to a standard optimality criterion, such as \$D-\$ or \$A-\$optimality. This problem generalizes the optimal experimental design problem for a linear regression model with a finite design space and uncorrelated errors. Finally, we show that under natural assumptions, a steady-state optimal design can be computed by semidefinite programming.}, language = {en} } @misc{Karbstein2014, author = {Karbstein, Marika}, title = {Integrated Line Planning and Passenger Routing: Connectivity and Transfers}, issn = {1438-0064}, doi = {10.1007/978-3-319-28697-6_37}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52986}, year = {2014}, abstract = {The integrated line planning and passenger routing problem is an important planning problem in service design of public transport. A major challenge is the treatment of transfers. A main property of a line system is its connectivity. In this paper we show that analysing the connecvitiy aspect of a line plan gives a new idea to handle the transfer aspect of the line planning problem.}, language = {en} } @inproceedings{VierhausFuegenschuh2013, author = {Vierhaus, Ingmar and F{\"u}genschuh, Armin}, title = {A Global Approach to the Optimal Control of System Dynamics Models}, booktitle = {Proceedings of the 31st International Conference of the System Dynamics Society}, year = {2013}, abstract = {The System Dynamics (SD) methodology is a framework for modeling and simulating the dynamic behavior of socioeconomic systems. Characteristic for the description of such systems is the occurrence of feedback loops together with stocks and flows. The mathematical equations that describe the system are usually ordinary differential equations and nonlinear algebraic constraints. Seemingly simple systems can show a nonintuitive, unpredictable behavior over time. Controlling a dynamical system means to specify potential interventions from outside that should keep the system on the desired track, and to define an evaluation schema to compare different controls among each other, so that a ``best'' control can be defined in a meaningful way. The central question is how to compute such globally optimal control for a given SD model, that allows the transition of the system into a desired state with minimum effort. We propose a mixed-integer nonlinear programming (MINLP) reformulation of the System Dynamics Optimization (SDO) problem. MINLP problems can be solved by linear programming based branch-and-bound approach. We demonstrate that standard MINLP solvers are not able to solve SDO problem. To overcome this obstacle, we introduce a special-tailored bound propagation method. Numerical results for these test cases are presented.}, language = {en} } @article{D'AndreagiovanniKrolikowskiPulaj2014, author = {D'Andreagiovanni, Fabio and Krolikowski, Jonatan and Pulaj, Jonad}, title = {A fast hybrid primal heuristic for multiband robust capacitated network design with multiple time periods}, volume = {26}, journal = {Applied Soft Computing}, doi = {10.1016/j.asoc.2014.10.016}, pages = {497 -- 507}, year = {2014}, abstract = {We investigate the Robust Multiperiod Network Design Problem, a generalization of the Capacitated Network Design Problem (CNDP) that, besides establishing flow routing and network capacity installation as in a canonical CNDP, also considers a planning horizon made up of multiple time periods and protection against fluctuations in traffic volumes. As a remedy against traffic volume uncertainty, we propose a Robust Optimization model based on Multiband Robustness (B{\"u}sing and D'Andreagiovanni, 2012), a refinement of classical Gamma-Robustness by Bertsimas and Sim (2004) that uses a system of multiple deviation bands. Since the resulting optimization problem may prove very challenging even for instances of moderate size solved by a state-of-the-art optimization solver, we propose a hybrid primal heuristic that combines a randomized fixing strategy inspired by ant colony optimization and an exact large neighbourhood search. Computational experiments on a set of realistic instances from the SNDlib (2010) show that our original heuristic can run fast and produce solutions of extremely high quality associated with low optimality gaps.}, language = {en} } @inproceedings{VierhausFuegenschuhGottwaldetal.2014, author = {Vierhaus, Ingmar and F{\"u}genschuh, Armin and Gottwald, Robert Lion and Gr{\"o}sser, Stefan}, title = {Modern Nonlinear Optimization Techniques for an Optimal Control of System Dynamics Models}, booktitle = {Proceedings of the 32nd International Conference of the System Dynamics Society}, year = {2014}, abstract = {We study System Dynamics models with several free parameters that can be altered by the user. We assume that the user's goal is to achieve a certain dynamic behavior of the model by varying these parameters. In order to find best possible combination of parameter settings, several automatic parameter tuning methods are described in the literature and readily available within existing System Dynamic software packages. We give a survey on the available techniques in the market and describe their theoretical background. Some of these methods are already six decades old, and meanwhile newer and more powerful optimization methods have emerged in the mathematical literature. One major obstacle for their direct use are tabled data in System Dynamics models, which are usually interpreted as piecewise linear functions. However, modern optimization methods usually require smooth functions which are twice continuously differentiable. We overcome this problem by a smooth spline interpolation of the tabled data. We use a test set of three complex System Dynamic models from the literature, describe their individual transition into optimization problems, and demonstrate the applicability of modern optimization algorithms to these System Dynamics Optimization problems.}, language = {en} } @article{BetkerGamrathKosiankowskietal.2014, author = {Betker, Andreas and Gamrath, Inken and Kosiankowski, Dirk and Lange, Christoph and Lehmann, Heiko and Pfeuffer, Frank and Simon, Felix and Werner, Axel}, title = {Comprehensive Topology and Traffic Model of a Nationwide Telecommunication Network}, volume = {6}, journal = {Journal of Optical Communications and Networking}, number = {11}, doi = {10.1364/JOCN.6.001038}, pages = {1038 -- 1047}, year = {2014}, abstract = {As a basis for meaningful simulation and optimization efforts with regard to traffic engineering or energy consumption in telecommunication networks, suitable models are indispensable. This concerns not only realistic network topologies but also models for the geographical distribution and the temporal dynamics of traffic, as well as the assumptions on network components and technology. This paper derives such a model from the practice of a large national carrier. Applying the network and traffic model, we demonstrate its use by presenting various optimization cases related to energy-efficient telecommunication. Here, we focus on load adaptivity by employing sleep modes to the network hardware, where several constraints on the reconfigurability of the network over time are considered.}, language = {en} } @inproceedings{BorndoerferReutherSchlechte2014, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas}, title = {A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem}, volume = {42}, booktitle = {14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, doi = {10.4230/OASIcs.ATMOS.2014.79}, pages = {79 -- 91}, year = {2014}, abstract = {We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.}, language = {en} } @misc{HeinzBeck2012, author = {Heinz, Stefan and Beck, J. Christopher}, title = {Reconsidering Mixed Integer Programming and MIP-based Hybrids for Scheduling}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14660}, number = {12-05}, year = {2012}, abstract = {Despite the success of constraint programming (CP) for scheduling, the much wider penetration of mixed integer programming (MIP) technology into business applications means that many practical scheduling problems are being addressed with MIP, at least as an initial approach. Furthermore, there has been impressive and well-documented improvements in the power of generic MIP solvers over the past decade. We empirically demonstrate that on an existing set of resource allocation and scheduling problems standard MIP and CP models are now competitive with the state-of-the-art manual decomposition approach. Motivated by this result, we formulate two tightly coupled hybrid models based on constraint integer programming (CIP) and demonstrate that these models, which embody advances in CP and MIP, are able to out-perform the CP, MIP, and decomposition models. We conclude that both MIP and CIP are technologies that should be considered along with CP for solving scheduling problems.}, language = {en} } @misc{BorndoerferLoebelReutheretal.2012, 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}, year = {2012}, 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{MenneRaackWessaelyetal.2012, author = {Menne, Ulrich and Raack, Christian and Wess{\"a}ly, Roland and Kharitonov, Daniel}, title = {Optimal Degree of Optical Circuit Switching in IP-over-WDM Networks}, issn = {1438-0064}, doi = {10.1109/ONDM.2012.6210206}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14843}, year = {2012}, abstract = {In this paper, we study the influence of technology, traffic properties and price trends on optimized design of a reference IP-over-WDM network with rich underlying fiber topology. In each network node, we investigate the optimal degree of traffic switching in an optical (lambda) domain versus an electrical (packet) domain, also known as measure of \emph{node transparency}. This measure is studied in connection to changes in traffic volume, demand affinity, optical circuit speeds and equipment cost. By applying variable design constraints, we assess the relative roles of the two distinct equipment groups, IP routers and optical cross-connects, with respect to resulting changes in cost-sensitive network architectures.}, language = {en} } @misc{BorndoerferHeismann2012, author = {Bornd{\"o}rfer, Ralf and Heismann, Olga}, title = {The Hypergraph Assignment Problem}, issn = {1438-0064}, doi = {10.1016/j.disopt.2014.11.002}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14822}, year = {2012}, abstract = {The hypergraph assignment problem (HAP) is the generalization of assignments from directed graphs to directed hypergraphs. It serves, in particular, as a universal tool to model several train composition rules in vehicle rotation planning for long distance passenger railways. We prove that even for problems with a small hyperarc size and hypergraphs with a special partitioned structure the HAP is NP-hard and APX-hard. Further, we present an extended integer linear programming formulation which implies, e. g., all clique inequalities.}, language = {en} } @misc{BorndoerferReutherSchlechteetal.2012, 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}, year = {2012}, 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{WessaelyWernerEckeletal.2012, author = {Wess{\"a}ly, Roland and Werner, Axel and Eckel, Klaus and Seibel, Julia and Orlowski, Sebastian and Louchet, Hadrien and Patzak, Erwin and Bentz, Winfried}, title = {Sch{\"a}tze heben bei der Planung von FTTx-Netzen: optimierte Nutzung von existierenden Leerrohren - eine Praxisstudie}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14861}, year = {2012}, abstract = {Das vom BMBF gef{\"o}rderte Projekt FTTX-PLAN entwickelt mathematische Modelle und Optimierungsverfahren, um automatisiert kostenoptimierte FTTx-Netze berechnen zu k{\"o}nnen. Wir zeigen anhand einer Praxisstudie in Zusammenarbeit mit der Regensburger R-KOM, wie ein Planer von diesen Verfahren profitieren kann, um die Auswirkungen bestimmter Entscheidungen auf die Netzstruktur und -kosten zu untersuchen. Wir illustrieren dies am Beispiel eines FTTB/FTTH-Vergleichs, der Variation von Kundenanbindungsraten und der gezielten Ausnutzung existierender Leerrohre, um Tiefbau zu vermeiden.}, language = {de} } @misc{BorndoerferLangenhanLoebeletal.2012, 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}, year = {2012}, 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{Werner2012, author = {Werner, Axel}, title = {Kombinatorische Optimierung und die 40-Punkte-Regel}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14871}, year = {2012}, abstract = {Wieviele Punkte braucht eine Mannschaft in der Fußball-Bundesliga mindestens, um sicher dem Abstieg zu entgehen? Wir benutzen kombinatorische Optimierung, um diese und {\"a}hnliche Fragen zu beantworten.}, language = {de} } @phdthesis{Fereirra1994, author = {Fereirra, Carlos Eduardo}, title = {On Combinatorial Optimization Problems Arising in Computer System Design}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10146}, school = {Zuse Institute Berlin (ZIB)}, year = {1994}, language = {en} } @misc{BorndoerferGroetschelLoebel1995, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Alcuin's Transportation Problems and Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1932}, number = {SC-95-27}, year = {1995}, abstract = {The need to solve {\it transportation problems\/} was and still is one of the driving forces behind the development of the mathematical disciplines of graph theory, optimization, and operations research. Transportation problems seem to occur for the first time in the literature in the form of the four ''River Crossing Problems'' in the book Propositiones ad acuendos iuvenes. The {\it Propositiones\/} ---the oldest collection of mathematical problems written in Latin--- date back to the \$8\$th century A.D. and are attributed to Alcuin of York, one of the leading scholars of his time, a royal advisor to Charlemagne at his Frankish court. Alcuin's river crossing problems had no impact on the development of mathematics. However, they already display all the characteristics of today's large-scale real transportation problems. From our point of view, they could have been the starting point of combinatorics, optimization, and operations research. We show the potential of Alcuin's problems in this respect by investigating his problem~18 about a wolf, a goat and a bunch of cabbages with current mathematical methods. This way, we also provide the reader with a leisurely introduction into the modern theory of integer programming.}, language = {en} } @inproceedings{EulerBorndoerferPuchertetal.2024, author = {Euler, Ricardo and Bornd{\"o}rfer, Ralf and Puchert, Christian and Takkula, Tuomo}, title = {ULD Build-Up Scheduling with Logic-Based Benders Decomposition}, volume = {14742}, booktitle = {Integration of Constraint Programming, Artificial Intelligence, and Operations Research}, doi = {10.1007/978-3-031-60597-0_17}, pages = {259 -- 276}, year = {2024}, abstract = {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}, language = {en} } @article{EulerMaristanydelasCasas2024, author = {Euler, Ricardo and Maristany de las Casas, Pedro}, title = {Labeling methods for partially ordered paths}, volume = {318}, journal = {European Journal of Operational Research}, number = {1}, edition = {1}, publisher = {Elsevier BV}, arxiv = {http://arxiv.org/abs/2307.10332}, doi = {10.1016/j.ejor.2024.05.002}, pages = {19 -- 30}, year = {2024}, abstract = {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.}, language = {en} } @misc{MaristanydelasCasasSedenoNodaBorndoerfer2021, author = {Maristany de las Casas, Pedro and Sedeno-Noda, Antonio and Bornd{\"o}rfer, Ralf}, title = {An Improved Multiobjective Shortest Path Algorithm}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-79712}, year = {2021}, abstract = {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.}, 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} } @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{LoebelBorndoerferWeider2024, author = {L{\"o}bel, Fabian and Bornd{\"o}rfer, Ralf and Weider, Steffen}, title = {Electric Bus Scheduling with Non-Linear Charging, Power Grid Bottlenecks, and Dynamic Recharge Rates}, arxiv = {http://arxiv.org/abs/2407.14446}, year = {2024}, abstract = {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.}, language = {en} } @inproceedings{BorndoerferLoebelLoebeletal.2024, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and L{\"o}bel, Fabian and Weider, Steffen}, title = {Solving the Electric Bus Scheduling Problem by an Integrated Flow and Set Partitioning Approach}, volume = {123}, booktitle = {24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024)}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, doi = {10.4230/OASIcs.ATMOS.2024.11}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-211992}, pages = {11:1 -- 11:16}, year = {2024}, abstract = {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.}, language = {en} } @article{PrauseBorndoerfer2024, author = {Prause, Felix and Bornd{\"o}rfer, Ralf}, title = {An Iterative Refinement Approach for the Rolling Stock Rotation Problem with Predictive Maintenance}, arxiv = {http://arxiv.org/abs/2404.08367}, year = {2024}, abstract = {The rolling stock rotation problem with predictive maintenance (RSRP-PdM) involves the assignment of trips to a fleet of vehicles with integrated maintenance scheduling based on the predicted failure probability of the vehicles. These probabilities are determined by the health states of the vehicles, which are considered to be random variables distributed by a parameterized family of probability distribution functions. During the operation of the trips, the corresponding parameters get updated. In this article, we present a dual solution approach for RSRP-PdM and generalize a linear programming based lower bound for this problem to families of probability distribution functions with more than one parameter. For this purpose, we define a rounding function that allows for a consistent underestimation of the parameters and model the problem by a state-expanded event-graph in which the possible states are restricted to a discrete set. This induces a flow problem that is solved by an integer linear program. We show that the iterative refinement of the underlying discretization leads to solutions that converge from below to an optimal solution of the original instance. Thus, the linear relaxation of the considered integer linear program results in a lower bound for RSRP-PdM. Finally, we report on the results of computational experiments conducted on a library of test instances.}, language = {en} } @inproceedings{Prause2024, author = {Prause, Felix}, title = {A Multi-Swap Heuristic for Rolling Stock Rotation Planning with Predictive Maintenance}, booktitle = {Proceedings of the 11th International Network Optimization Conference (INOC), Dublin, Ireland, March 11-23, 2024}, doi = {10.48786/inoc.2024.11}, pages = {58 -- 63}, year = {2024}, 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. Subsequently, 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} } @article{PrauseBorndoerferGrimmetal.2024, author = {Prause, Felix and Bornd{\"o}rfer, Ralf and Grimm, Boris and Tesch, Alexander}, title = {Approximating rolling stock rotations with integrated predictive maintenance}, volume = {30}, journal = {Journal of Rail Transport Planning \& Management}, doi = {10.1016/j.jrtpm.2024.100434}, pages = {100434}, year = {2024}, abstract = {We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PdM) 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 six 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} } @article{SahinDigehsaraBorndoerfer2021, author = {Sahin, Guvenc and Digehsara, Amin Ahmadi and Bornd{\"o}rfer, Ralf}, title = {Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation}, volume = {96}, journal = {Open Access Series in Informatics (OASIcs), 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)}, doi = {10.4230/OASIcs.ATMOS.2021.17}, pages = {17:1 -- 17:6}, year = {2021}, abstract = {In order to plan and schedule a demand-responsive public transportation system, both temporal and spatial changes in demand should be taken into account even at the line planning stage. We study the multi-period line planning problem with integrated decisions regarding dynamic allocation of vehicles among the lines. Given the NP-hard nature of the line planning problem, the multi-period version is clearly difficult to solve for large public transit networks even with advanced solvers. It becomes necessary to develop algorithms that are capable of solving even the very-large instances in reasonable time. For instances which belong to real public transit networks, we present results of a heuristic local branching algorithm and an exact approach based on constraint propagation.}, language = {en} } @article{BorndoerferDaneckerWeiser2021, author = {Bornd{\"o}rfer, Ralf and Danecker, Fabian and Weiser, Martin}, title = {A Discrete-Continuous Algorithm for Free Flight Planning}, volume = {14}, journal = {Algorithms}, number = {1}, publisher = {MDPI}, issn = {1438-0064}, doi = {10.3390/a14010004}, pages = {4}, year = {2021}, abstract = {We propose a hybrid discrete-continuous algorithm for flight planning in free flight airspaces. In a first step, our DisCOptER method discrete-continuous optimization for enhanced resolution) computes a globally optimal approximate flight path on a discretization of the problem using the A* method. This route initializes a Newton method that converges rapidly to the smooth optimum in a second step. The correctness, accuracy, and complexity of the method are goverened by the choice of the crossover point that determines the coarseness of the discretization. We analyze the optimal choice of the crossover point and demonstrate the asymtotic superority of DisCOptER over a purely discrete approach.}, language = {en} }