@misc{BorndoerferKarbsteinMehrgardtetal.2014, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika and Mehrgardt, Julika and Reuther, Markus and Schlechte, Thomas}, title = {The Cycle Embedding Problem}, issn = {1438-0064}, doi = {10.1007/978-3-319-28697-6_65}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52788}, year = {2014}, abstract = {Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.}, language = {en} } @inproceedings{BorndoerferMehrgardtReutheretal.2014, author = {Bornd{\"o}rfer, Ralf and Mehrgardt, Julika and Reuther, Markus and Schlechte, Thomas and Waas, Kerstin}, title = {Re-Optimization of Rolling Stock Rotations}, edition = {Operations Research Proceedings 2013}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-07001-8_8}, pages = {49 -- 55}, year = {2014}, abstract = {The Rolling Stock Rotation Problem is to schedule rail vehicles in order to cover timetabled trips by a cost optimal set of vehicle rotations. The problem integrates several facets of railway optimization, such as vehicle composition, maintenance constraints, and regularity aspects. In industrial applications existing vehicle rotations often have to be re-optimized to deal with timetable changes or construction sites. We present an integrated modeling and algorithmic approach to this task as well as computational results for industrial problem instances of DB Fernverkehr AG.}, language = {en} } @inproceedings{BlancoSchlechte2014, author = {Blanco, Marco and Schlechte, Thomas}, title = {Analysis of Micro-Macro Transformations of Railway Networks}, booktitle = {Operations Research Proceedings 2013}, doi = {10.1007/978-3-319-07001-8_6}, pages = {37 -- 42}, year = {2014}, abstract = {A common technique in the solution of large or complex optimization problems is the use of micro-macro transformations. In this paper, we carry out a theoretical analysis of such transformations for the track allocation problem in railway networks. We prove that the cumulative rounding technique of Schlechte et al. satisfies two of three natural optimality criteria and that this performance cannot be improved. We also show that under extreme circumstances, this technique can perform inconveniently by underestimating the global optimal value.}, language = {en} } @inproceedings{SagnolBorndoerferSchlechteetal.2014, author = {Sagnol, Guillaume and Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Swarat, Elmar}, title = {The Price of Spite in Spot-checking games}, volume = {8768}, booktitle = {7th International Symposium on Algorithmic Game Theory (SAGT'2014)}, editor = {Lavi, Ron}, publisher = {Springer}, isbn = {978-3-662-44802-1}, doi = {10.1007/978-3-662-44803-8}, pages = {293}, year = {2014}, abstract = {We introduce the class of spot-checking games (SC games). These games model problems where the goal is to distribute fare inspectors over a toll network. Although SC games are not zero-sum, we show that a Nash equilibrium can be computed by linear programming. The computation of a strong Stackelberg equilibrium is more relevant for this problem, but we show that this is NP-hard. However, we give some bounds on the \emph{price of spite}, which measures how the payoff of the inspector degrades when committing to a Nash equilibrium. Finally, we demonstrate the quality of these bounds for a real-world application, namely the enforcement of a truck toll on German motorways.}, language = {en} } @inproceedings{SchadeBorndoerferBreueretal.2017, author = {Schade, Stanley and Bornd{\"o}rfer, Ralf and Breuer, Matthias and Grimm, Boris and Reuther, Markus and Schlechte, Thomas and Siebeneicher, Patrick}, title = {Pattern Detection For Large-Scale Railway Timetables}, booktitle = {Proceedings of the IAROR conference RailLille}, year = {2017}, abstract = {We consider railway timetables of our industrial partner DB Fernverkehr AG that operates the ICE high speed trains in the long-distance passenger railway network of Germany. Such a timetable covers a whole year with 364 days and, typically, includes more than 45,000 trips. A rolling stock rotation plan is not created for the whole timetable at once. Instead the timetable is divided into regular invariant sections and irregular deviations (e.g. for public holidays). A separate rotation plan with a weekly period can then be provided for each of the different sections of the timetable. We present an algorithmic approach to automatically recognize these sections. Together with the supplementing visualisation of the timetable this method has shown to be very relevant for our industrial partner.}, 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}, 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.2016, 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}, volume = {50}, journal = {Transportation Science}, number = {3}, doi = {10.1287/trsc.2015.0633}, pages = {863 -- 877}, year = {2016}, 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{BlancoBorndoerferBrueckneretal.2015, author = {Blanco, Marco and Bornd{\"o}rfer, Ralf and Br{\"u}ckner, Michael and Hoang, Nam-Dung and Schlechte, Thomas}, title = {On the Path Avoiding Forbidden Pairs Polytope}, volume = {50}, journal = {Electronic Notes in Discrete Mathematics}, doi = {10.1016/j.endm.2015.07.057}, pages = {343 -- 348}, year = {2015}, abstract = {Given a directed, acyclic graph, a source and a sink node, and a set of forbidden pairs of arcs, the path avoiding forbidden pairs (PAFP) problem is to find a path that connects the source and sink nodes and contains at most one arc from each forbidden pair. The general version of the problem is NP-hard, but it becomes polynomially solvable for certain topological configurations of the pairs. We present the first polyhedral study of the PAFP problem. We introduce a new family of valid inequalities for the PAFP polytope and show that they are sufficient to provide a complete linear description in the special case where the forbidden pairs satisfy a disjointness property. Furthermore, we show that the number of facets of the PAFP polytope is exponential in the size of the graph, even for the case of a single forbidden pair.}, 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} } @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} }