@inproceedings{LiebchenSwarat2008, author = {Liebchen, Christian and Swarat, Elmar}, title = {The Second Chvatal Closure Can Yield Better Railway Timetables}, booktitle = {ATMOS 2008 - 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}, editor = {Fischetti, Matteo and Widmayer, Peter}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany}, address = {Dagstuhl, Germany}, doi = {10.4230/OASIcs.ATMOS.2008.1580}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-15802}, year = {2008}, language = {en} } @article{BorndoerferErolGraffagninoetal.2012, author = {Bornd{\"o}rfer, Ralf and Erol, Berkan and Graffagnino, Thomas and Schlechte, Thomas and Swarat, Elmar}, title = {Optimizing the Simplon railway corridor}, volume = {218}, journal = {Annals of Operations Research}, number = {1}, edition = {Annals of Operations Research}, publisher = {Springer US}, doi = {10.1007/s10479-012-1260-9}, pages = {93 -- 106}, year = {2012}, language = {en} } @inproceedings{SchlechteTanner2010, author = {Schlechte, Thomas and Tanner, Andreas}, title = {Railway capacity auctions with dual prices}, booktitle = {Selected Proceedings of the 12th World Conference on Transport Research}, year = {2010}, language = {en} } @inproceedings{BorndoerferSchlechte2007, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Models for Railway Track Allocation}, volume = {07001}, booktitle = {ATMOS 2007 - 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}, editor = {Liebchen, Christian and Ahuja, Ravindra and Mesa, Juan}, publisher = {Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany}, year = {2007}, language = {en} } @inproceedings{BorndoerferSchlechte2008, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Balancing Efficiency and Robustness}, booktitle = {MCDM for Sustainable Energy and Transportation Systems}, editor = {Ehrgott, Matthias and Naujoks, Boris and Stewart, Theo and Wallenius, Jyrki}, publisher = {Lecture Notes in Economics and Mathematical Systems}, year = {2008}, language = {en} } @misc{BorndoerferGroetschelLoebel1999, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Der Schnellste Weg zum Ziel}, doi = {10.1007/978-3-322-96366-6_5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4209}, number = {SC-99-32}, year = {1999}, abstract = {Wir geben eine Einf{\"u}hrung in die Mathematik von und mit Wegen. Nicht auf dem k{\"u}rzesten, aber auf einem hoffentlich kurzweiligen Weg!}, language = {de} } @misc{SchwartzBorndoerferBartz2016, author = {Schwartz, Stephan and Bornd{\"o}rfer, Ralf and Bartz, Gerald}, title = {The Graph Segmentation Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60750}, year = {2016}, abstract = {We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.}, language = {en} } @inproceedings{BorndoerferHoppmannKarbsteinetal.2016, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and L{\"o}bel, Fabian}, title = {The Modulo Network Simplex with Integrated Passenger Routing}, booktitle = {Operations Research Proceedings 2016}, year = {2016}, abstract = {Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method, a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers' travel paths into consideration.}, language = {en} } @misc{Wenzel2016, type = {Master Thesis}, author = {Wenzel, Ron}, title = {On the In-Flight Rest Assignment Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-59328}, pages = {76}, year = {2016}, abstract = {The airplane has changed the world in a tremendous way. Efficient scheduling of airmen and aircrafts is of considerable importance for cost-effectiveness of compa- nies. Attentiveness of flight crew members is vital as fatigue can lead to severe accidents. Therefore, duty times of flight crews are strictly limited. Long distance flights may be difficult to schedule with only one set of crew members. Furthermore, pertu- bations of the schedules may entail exchanging the entire crew, which confounds multiday schedules. A new EU regulation introduced in-flight rest: a schedule may extend pilots' duty times if they rest for a certain time in designated crew compart- ments provided aboard airplanes. Of course they have to be replaced in that period of time. This thesis examines the in-flight rest assignment problem, which is the decision problem whether a given schedule allows for all crew members to take their compul- sory rest. The problem can be seen as multimachine scheduling problem. Efficient algorithms for special cases were developed and an alternative approach for entire hard cases is discussed.}, language = {en} } @misc{SagnolBalzerBorndoerferetal.2016, author = {Sagnol, Guillaume and Balzer, Felix and Bornd{\"o}rfer, Ralf and Spies, Claudia and von Dincklage, Falk}, title = {Makespan and Tardiness in Activity Networks with Lognormal Activity Durations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-59290}, year = {2016}, abstract = {We propose an algorithm to approximate the distribution of the completion time (makespan) and the tardiness costs of a project, when durations are lognormally distributed. This problem arises naturally for the optimization of surgery scheduling, where it is very common to assume lognormal procedure times. We present an analogous of Clark's formulas to compute the moments of the maximum of a set of lognormal variables. Then, we use moment matching formulas to approximate the earliest starting time of each activity of the project by a shifted lognormal variable. This approach can be seen as a lognormal variant of a state-of-the-art method used for the statistical static timing analysis (SSTA) of digital circuits. We carried out numerical experiments with instances based on real data from the application to surgery scheduling. We obtained very promising results, especially for the approximation of the mean overtime in operating rooms, for which our algorithm yields results of a similar quality to Monte-Carlo simulations requiring an amount of computing time several orders of magnitude larger.}, language = {en} } @misc{SagnolHegeWeiser2016, author = {Sagnol, Guillaume and Hege, Hans-Christian and Weiser, Martin}, title = {Using sparse kernels to design computer experiments with tunable precision}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-59605}, year = {2016}, abstract = {Statistical methods to design computer experiments usually rely on a Gaussian process (GP) surrogate model, and typically aim at selecting design points (combinations of algorithmic and model parameters) that minimize the average prediction variance, or maximize the prediction accuracy for the hyperparameters of the GP surrogate. In many applications, experiments have a tunable precision, in the sense that one software parameter controls the tradeoff between accuracy and computing time (e.g., mesh size in FEM simulations or number of Monte-Carlo samples). We formulate the problem of allocating a budget of computing time over a finite set of candidate points for the goals mentioned above. This is a continuous optimization problem, which is moreover convex whenever the tradeoff function accuracy vs. computing time is concave. On the other hand, using non-concave weight functions can help to identify sparse designs. In addition, using sparse kernel approximations drastically reduce the cost per iteration of the multiplicative weights updates that can be used to solve this problem.}, language = {en} } @misc{BeckenbachScheidweiler2016, author = {Beckenbach, Isabel and Scheidweiler, Robert}, title = {Perfect f-Matchings and f-Factors in Hypergraphs - A Combinatorial Approach}, issn = {1438-0064}, doi = {10.1016/j.disc.2017.05.005}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-59071}, year = {2016}, abstract = {We prove characterizations of the existence of perfect f-matchings in uniform mengerian and perfect hypergraphs. Moreover, we investigate the f-factor problem in balanced hypergraphs. For uniform balanced hypergraphs we prove two existence theorems with purely combinatorial arguments, whereas for non-uniform balanced hypergraphs we show that the f-factor problem is NP-hard.}, language = {en} } @article{SagnolHarman2015, author = {Sagnol, Guillaume and Harman, Radoslav}, title = {Computing exact D-optimal designs by mixed integer second-order cone programming}, volume = {43}, journal = {The Annals of Statistics}, number = {5}, doi = {10.1214/15-AOS1339}, pages = {2198 -- 2224}, year = {2015}, abstract = {Let the design of an experiment be represented by an \$s-\$dimensional vector \$w\$ of weights with nonnegative components. Let the quality of \$w\$ for the estimation of the parameters of the statistical model be measured by the criterion of \$D-\$optimality, defined as the \$m\$th root of the determinant of the information matrix \$M(w)=\sum_{i=1}^s w_i A_i A_i^T\$, where \$A_i\$,\$i=1,\ldots,s\$ are known matrices with \$m\$ rows. In this paper, we show that the criterion of \$D-\$optimality is second-order cone representable. As a result, the method of second-order cone programming can be used to compute an approximate \$D-\$optimal design with any system of linear constraints on the vector of weights. More importantly, the proposed characterization allows us to compute an exact \$D-\$optimal design, which is possible thanks to high-quality branch-and-cut solvers specialized to solve mixed integer second-order cone programming problems. Our results extend to the case of the criterion of \$D_K-\$optimality, which measures the quality of \$w\$ for the estimation of a linear parameter subsystem defined by a full-rank coefficient matrix \$K\$. We prove that some other widely used criteria are also second-order cone representable, for instance, the criteria of \$A-\$, \$A_K\$-, \$G-\$ and \$I-\$optimality. We present several numerical examples demonstrating the efficiency and general applicability of the proposed method. We show that in many cases the mixed integer second-order cone programming approach allows us to find a provably optimal exact design, while the standard heuristics systematically miss the optimum.}, language = {en} } @inproceedings{DuarteSagnolOliveira2015, author = {Duarte, Belmiro P.M. and Sagnol, Guillaume and Oliveira, Nuno M.C.}, title = {A Robust Minimax Semidefinite Programming Formulation for Optimal Design of Experiments for Model Parametrization}, volume = {37}, booktitle = {12th International Symposium on Process Systems Engineering and 25th European Symposium on Computer Aided Process Engineering}, doi = {10.1016/B978-0-444-63578-5.50146-8}, pages = {905 -- 910}, year = {2015}, abstract = {Model-based optimal design of experiments (M-bODE) is a crucial step in model parametrization since it encloses a framework that maximizes the amount of information extracted from a battery of lab experiments. We address the design of M-bODE for dynamic models considering a continuous representation of the design. We use Semidefinite Programming (SDP) to derive robust minmax formulations for nonlinear models, and extend the formulations to other criteria. The approaches are demonstrated for a CSTR where a two-step reaction occurs.}, language = {en} } @misc{SchenkerBorndoerferSkutella2016, author = {Schenker, Sebastian and Bornd{\"o}rfer, Ralf and Skutella, Martin}, title = {A novel partitioning of the set of non-dominated points}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61286}, year = {2016}, abstract = {We consider a novel partitioning of the set of non-dominated points for general multi-objective integer programs with \$k\$ objectives. The set of non-dominated points is partitioned into a set of non-dominated points whose efficient solutions are also efficient for some restricted subproblem with one less objective; the second partition comprises the non-dominated points whose efficient solutions are inefficient for any of the restricted subproblems. We show that the first partition has the nice property that it yields finite rectangular boxes in which the points of the second partition are located.}, language = {en} } @inproceedings{GrimmBorndoerferReutheretal.2016, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Schade, Stanley}, title = {Regularity patterns for rolling stock rotation optimization}, volume = {8}, booktitle = {8th International Conference on Applied Operational Research, Proceedings}, pages = {28 -- 32}, year = {2016}, abstract = {The operation of railways gives rise to many fundamental optimization problems. One of these problems is to cover a given set of timetabled trips by a set of rolling stock rotations. This is well known as the Rolling Stock Rotation Problem (RSRP). Most approaches in the literature focus primarily on modeling and minimizing the operational costs. However, an essential aspect for the industrial application is mostly neglected. As the RSRP follows timetabling and line planning, where periodicity is a highly desired property, it is also desired to carry over periodic structures to rolling stock rotations and following operations. We call this complex requirement regularity. Regularity turns out to be of essential interest, especially in the industrial scenarios that we tackle in cooperation with DB Fernverkehr AG. Moreover, regularity in the context of the RSRP has not been investigated thoroughly in the literature so far. We introduce three regularity patterns to tackle this requirement, namely regular trips, regular turns, and regular handouts. We present a two-stage approach in order to optimize all three regularity patterns. At first, we integrate regularity patterns into an integer programming approach for the minimization of the operational cost of rolling stock rotations. Afterwards regular handouts are computed. These handouts present the rotations of the first stage in the most regular way. Our computational results (i.e., rolling stock rotations evaluated by planners of DB Fernverkehr AG) show that the three regularity patterns and our concept are a valuable and, moreover, an essential contribution to rolling stock rotation optimization.}, language = {en} } @misc{DuarteSagnolOliveira2015, author = {Duarte, Belmiro P.M. and Sagnol, Guillaume and Oliveira, Nuno M.C.}, title = {A robust minimax Semidefinite Programming formulation for optimal design of experiments for model parametrization}, issn = {1438-0064}, doi = {10.1016/B978-0-444-63578-5.50146-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54626}, year = {2015}, abstract = {Model-based optimal design of experiments (M-bODE) is a crucial step in model parametrization since it encloses a framework that maximizes the amount of information extracted from a battery of lab experiments. We address the design of M-bODE for dynamic models considering a continuous representation of the design. We use Semidefinite Programming (SDP) to derive robust minmax formulations for nonlinear models, and extend the formulations to other criteria. The approaches are demonstrated for a CSTR where a two-step reaction occurs.}, language = {en} } @misc{BorndoerferNeumannPfetsch2008, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Models for Fare Planning in Public Transport}, issn = {1438-0064}, doi = {10.1016/j.dam.2012.02.027}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10708}, number = {08-16}, year = {2008}, abstract = {The optimization of fare systems in public transit allows to pursue objectives such as the maximization of demand, revenue, profit, or social welfare. We propose a non-linear optimization approach to fare planning that is based on a detailed discrete choice model of user behavior. The approach allows to analyze different fare structures, optimization objectives, and operational scenarios involving, e.g., subsidies. We use the resulting models to compute optimized fare systems for the city of Potsdam, Germany.}, language = {en} } @misc{BorndoerferNeumannPfetsch2008, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Angebotsplanung im {\"o}ffentlichen Nahverkehr}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10555}, number = {08-04}, year = {2008}, abstract = {Die Angebotsplanung im {\"o}ffentlichen Nahverkehr umfasst die Aufgaben der Netz-, Linien-,Fahr- und Preisplanung. Wir stellen zwei mathematische Optimierungsmodelle zur Linien- und Preisplanung vor. Wir zeigen anhand von Berechnungen f{\"u}r die Verkehrsbetriebe in Potsdam(ViP), dass sich damit komplexe Zusammenh{\"a}nge quantitativ analysieren lassen. Auf diese Weise untersuchen wir die Auswirkungen von Freiheitsgraden auf die Konstruktion von Linien und die Wahl von Reisewegen der Passagiere, Abh{\"a}ngigkeiten zwischen Kosten und Reisezeiten sowie den Einfluss verschiedener Preissysteme auf Nachfrage und Kostendeckung.}, language = {de} } @misc{BorndoerferNeumannPfetsch2005, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Fare Planning for Public Transport}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8541}, number = {05-20}, year = {2005}, abstract = {In this paper we introduce the fare planning problem for public transport which consists in designing a system of fares maximizing revenue. We propose a new simple general model for this problem. It i s based on a demand function and constraints for the different fares. The constraints define the structure of the fare system, e.g., distance dependent fares or zone fares. We discuss a simple example with a quadratic demand function and distance dependent fares. Then we introduce a more realistic discrete choice model in which passengers choose between different alternatives depending on the numb er of trips per month. We demonstrate the examples by computational experiments.}, language = {en} } @misc{BeckenbachPeisSchaudtetal.2017, author = {Beckenbach, Isabel and Peis, Britta and Schaudt, Oliver and Scheidweiler, Robert}, title = {A Combinatorial Proof of a K{\"o}nig-type Theorem for Unimodular Hypergraphs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64017}, year = {2017}, abstract = {We state purely combinatorial proofs for K{\"o}nig- and Hall-type theorems for a wide class of combinatorial optimization problems. Our methods rely on relaxations of the matching and vertex cover problem and, moreover, on the strong coloring properties admitted by bipartite graphs and their generalizations.}, language = {en} } @misc{GrimmBorndoerferReutheretal.2017, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schade, Stanley and Schlechte, Thomas}, title = {A Propagation Approach to Acyclic Rolling Stock Rotation Optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-63930}, year = {2017}, abstract = {The rolling stock, i.e., railway vehicles, are one of the key ingredients of a running railway system. As it is well known, the offer of a railway company to their customers, i.e., the railway timetable, changes from time to time. Typical reasons for that are different timetables associated with different seasons, maintenance periods or holidays. Therefore, the regular lifetime of a timetable is split into (more or less) irregular periods where parts of the timetable are changed. In order to operate a railway timetable most railway companies set up sequences that define the operation of timetabled trips by a single physical railway vehicle called (rolling stock) rotations. Not surprisingly, the individual parts of a timetable also affect the rotations. More precisely, each of the parts brings up an acyclic rolling stock rotation problem with start and end conditions associated with the beginning and ending of the corresponding period. In this paper, we propose a propagation approach to deal with large planning horizons that are composed of many timetables with shorter individual lifetimes. The approach is based on an integer linear programming formulation that propagates rolling stock rotations through the irregular parts of the timetable while taking a large variety of operational requirements into account. This approach is implemented within the rolling stock rotation optimization framework ROTOR used by DB Fernverkehr AG, one of the leading railway operators in Europe. Computational results for real world scenarios are presented to evaluate the approach.}, language = {en} } @misc{BorndoerferBuwayaSagnoletal.2012, author = {Bornd{\"o}rfer, Ralf and Buwaya, Julia and Sagnol, Guillaume and Swarat, Elmar}, title = {Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach}, issn = {1438-0064}, doi = {/10.1016/j.endm.2013.05.100}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17401}, year = {2012}, abstract = {We present a game-theoretic approach to optimize the strategies of toll enforcement on a motorway network. In contrast to previous approaches, we consider a network with an arbitrary topology, and we handle the fact that users may choose their Origin-Destination path; in particular they may take a detour to avoid sections with a high control rate. We show that a Nash equilibrium can be computed with an LP (although the game is not zero-sum), and we give a MIP for the computation of a Stackelberg equilibrium. Experimental results based on an application to the enforcement of a truck toll on German motorways are presented.}, language = {en} } @misc{BorndoerferSagnolSwarat2011, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar}, title = {An IP Approach to Toll Enforcement Optimization on German Motorways}, issn = {1438-0064}, doi = {10.1007/978-3-642-29210-1_51}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14299}, number = {11-42}, year = {2011}, abstract = {This paper proposes the first model for toll enforcement optimization on German motorways. The enforcement is done by mobile control teams and our goal is to produce a schedule achieving network-wide control, proportional to spatial and time-dependent traffic distributions. Our model consists of two parts. The first plans control tours using a vehicle routing approach with profits and some side constraints. The second plans feasible rosters for the control teams. Both problems can be modeled as Multi-Commodity Flow Problems. Adding additional coupling constraints produces a large-scale integrated integer programming formulation. We show that this model can be solved to optimality for real world instances associated with a control area in East Germany.}, language = {en} } @misc{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}, issn = {1438-0064}, doi = {10.1007/978-3-662-44803-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-52775}, 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{BorndoerferSagnolSchwartz2016, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schwartz, Stephan}, title = {An Extended Network Interdiction Problem for Optimal Toll Control}, volume = {52}, booktitle = {INOC 2015 - 7th International Network Optimization Conference}, doi = {10.1016/j.endm.2016.03.040}, pages = {301 -- 308}, year = {2016}, abstract = {We study an extension of the shortest path network interdiction problem and present a novel real-world application in this area. We consider the problem of determining optimal locations for toll control stations on the arcs of a transportation network. We handle the fact that drivers can avoid control stations on parallel secondary roads. The problem is formulated as a mixed integer program and solved using Benders decomposition. We present experimental results for the application of our models to German motorways.}, language = {en} } @misc{SchadeSchlechteWitzig2017, author = {Schade, Stanley and Schlechte, Thomas and Witzig, Jakob}, title = {Structure-based Decomposition for Pattern-Detection for Railway Timetables}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64525}, year = {2017}, abstract = {We consider the problem of pattern detection in large scale railway timetables. This problem arises in rolling stock optimization planning in order to identify invariant sections of the timetable for which a cyclic rotation plan is adequate. We propose a dual reduction technique which leads to an decomposition and enumeration method. Computational results for real world instances demonstrate that the method is able to produce optimal solutions as fast as standard MIP solvers.}, language = {en} } @misc{BorndoerferHoppmannKarbsteinetal.2016, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and L{\"o}bel, Fabian}, title = {The Modulo Network Simplex with Integrated Passenger Routing}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60319}, year = {2016}, abstract = {Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method, a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers' travel paths into consideration.}, language = {en} } @inproceedings{SchadeStrehler2016, author = {Schade, Stanley and Strehler, Martin}, title = {The Maximum Flow Problem for Oriented Flows}, volume = {54}, booktitle = {16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)}, editor = {Goerigk, Marc and Werneck, Renato}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, isbn = {978-3-95977-021-7}, issn = {2190-6807}, doi = {10.4230/OASIcs.ATMOS.2016.7}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-65318}, pages = {1 -- 13}, year = {2016}, abstract = {In several applications of network flows, additional constraints have to be considered. In this paper, we study flows, where the flow particles have an orientation. For example, cargo containers with doors only on one side and train coaches with 1st and 2nd class compartments have such an orientation. If the end position has a mandatory orientation, not every path from source to sink is feasible for routing or additional transposition maneuvers have to be made. As a result, a source-sink path may visit a certain vertex several times. We describe structural properties of optimal solutions, determine the computational complexity, and present an approach for approximating such flows.}, language = {en} } @misc{BorndoerferKlugLamorgeseetal.2015, author = {Bornd{\"o}rfer, Ralf and Klug, Torsten and Lamorgese, Leonardo and Mannino, Carlo and Reuther, Markus and Schlechte, Thomas}, title = {Recent Success Stories on Optimization of Railway Systems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53726}, year = {2015}, abstract = {Planning and operating railway transportation systems is an extremely hard task due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. Because of that, however, mathematical models and optimization techniques can result in large gains for both railway cus- tomers and operators, e.g., in terms of cost reductions or service quality improvements. In the last years a large and growing group of researchers in the OR community have devoted their attention to this domain devel- oping mathematical models and optimization approaches to tackle many of the relevant problems in the railway planning process. However, there is still a gap to bridge between theory and practice, with a few notable exceptions. In this paper we address three success stories, namely, long-term freight train routing (part I), mid-term rolling stock rotation planning (part II), and real-time train dispatching (part III). In each case, we describe real-life, successful implementations. We will dis- cuss the individual problem setting, survey the optimization literature, and focus on particular aspects addressed by the mathematical models. We demonstrate on concrete applications how mathematical optimization can support railway planning and operations. This gives proof that math- ematical optimization can support the planning of rolling stock resources. Thus, mathematical models and optimization can lead to a greater effi- ciency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry.}, language = {en} } @misc{BorndoerferKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {Metric Inequalities for Routings on Direct Connections with Application in Line Planning}, issn = {1438-0064}, doi = {10.1016/j.disopt.2015.07.004}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53507}, year = {2015}, abstract = {We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the feasibility condition for arc capacities in ordinary multi-commodity flows. The concept allows to solve large-scale real-world line planning problems in public transport including a novel passenger routing model that favors direct connections over connections with transfers.}, language = {en} } @misc{HarmanSagnol2015, author = {Harman, Radoslav and Sagnol, Guillaume}, title = {Computing D-optimal experimental designs for estimating treatment contrasts under the presence of a nuisance time trend}, issn = {1438-0064}, doi = {10.1007/978-3-319-13881-7_10}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53640}, year = {2015}, abstract = {We prove a mathematical programming characterisation of approximate partial D-optimality under general linear constraints. We use this characterisation with a branch-and-bound method to compute a list of all exact D-optimal designs for estimating a pair of treatment contrasts in the presence of a nuisance time trend up to the size of 24 consecutive trials.}, language = {en} } @inproceedings{SagnolHarman2015, author = {Sagnol, Guillaume and Harman, Radoslav}, title = {Optimal Designs for Steady-state Kalman filters}, volume = {122}, booktitle = {Stochastic Models, Statistics and Their Applications}, editor = {Steland, Ansgar and Rafajłowicz, Ewaryst and Szajowski, Krzysztof}, publisher = {Springer}, doi = {10.1007/978-3-319-13881-7_17}, pages = {149 -- 157}, year = {2015}, 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} } @inproceedings{HarmanSagnol2015, author = {Harman, Radoslav and Sagnol, Guillaume}, title = {Computing D-optimal experimental designs for estimating treatment contrasts under the presence of a nuisance time trend}, volume = {122}, booktitle = {Stochastic Models, Statistics and Their Applications}, editor = {Steland, Ansgar and Rafajłowicz, Ewaryst and Szajowski, Krzysztof}, publisher = {Springer}, doi = {10.1007/978-3-319-13881-7_10}, pages = {83 -- 91}, year = {2015}, abstract = {We prove a mathematical programming characterisation of approximate partial D-optimality under general linear constraints. We use this characterisation with a branch-and-bound method to compute a list of all exact D-optimal designs for estimating a pair of treatment contrasts in the presence of a nuisance time trend up to the size of 24 consecutive trials.}, language = {en} } @misc{BorndoerferSchlechteSwarat2011, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Swarat, Elmar}, title = {Railway Track Allocation - Simulation, Aggregation, and Optimization}, issn = {1438-0064}, doi = {10.1007/978-3-642-27963-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14031}, number = {11-35}, year = {2011}, abstract = {Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway company. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market in Europe. This leads to more potential conflicts between trains caused by an increasing demand of train paths. Planning and operating railway transportation systems is extremely hard due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. In order to make best use of the infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithms can help to automatize and tackle these challenges. Our contribution in this paper is to present a renewed planning process due to the liberalization in Europe and an associated concept for track allocation, that consists of three important parts, simulation, aggregation, and optimization. Furthermore, we present results of our general framework for real world data.}, language = {en} } @misc{BorndoerferFriedowKarbstein2012, author = {Bornd{\"o}rfer, Ralf and Friedow, Isabel and Karbstein, Marika}, title = {Optimierung des Linienplans 2010 in Potsdam}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14486}, number = {12-04}, year = {2012}, abstract = {Im Zuge der {\"U}bernahme von 6 Linien der Havelbus Verkehrsgesellschaft mbH durch die ViP Verkehr in Potsdam GmbH ergab sich 2009 die Notwendigkeit der Entwicklung eines neuen Linien- und Taktplans f{\"u}r das Jahr 2010. Das Konrad-Zuse-Zentrum f{\"u}r Informationstechnik Berlin (ZIB) entwickelt in einem Projekt des DFG-Forschungszentrums Matheon ein Verfahren zur mathematischen Linienoptimierung. Dieses Tool wurde bei der Optimierung des ViP Linienplans 2010 in einer projektbegleitenden Studie eingesetzt, um Alternativen bei verschiedenen Planungs- und Zielvorgaben auszuloten. In dem Artikel wird eine Auswertung der Ergebnisse mit dem Verkehrsanalysesystem Visum der PTV AG beschrieben. Die Auswertungen best{\"a}tigen, dass mit Hilfe von mathematischer Optimierung eine weitere Verk{\"u}rzung der Reisezeit um 1\%, eine als um 6\% verk{\"u}rzt empfundene Reisezeit, 10\% weniger Fahrzeit im Fahrzeug und eine gleichzeitige Kostenreduktion um 5\% m{\"o}glich sind.}, language = {de} } @misc{BorndoerferHeismann2012, author = {Bornd{\"o}rfer, Ralf and Heismann, Olga}, title = {Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14564}, number = {11-46}, year = {2012}, abstract = {Vehicle rotation planning is a fundamental problem in rail transport. It decides how the railcars, locomotives, and carriages are operated in order to implement the trips of the timetable. One important planning requirement is operational regularity, i.e., using the rolling stock in the same way on every day of operation. We propose to take regularity into account by modeling the vehicle rotation planning problem as a minimum cost hyperassignment problem (HAP). Hyperassignments are generalizations of assignments from directed graphs to directed hypergraphs. Finding a minimum cost hyperassignment is NP-hard. Most instances arising from regular vehicle rotation planning, however, can be solved well in practice. We show that, in particular, clique inequalities strengthen the canonical LP relaxation substantially.}, language = {en} } @misc{BorndoerferKarbstein2012, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {A Note on Menger's Theorem for Hypergraphs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14471}, number = {12-03}, year = {2012}, abstract = {We prove the companion Theorem to Menger's Theorem for hypergraphs. This result gives rise to a new class of blocking pairs of ideal matrices, that generalize the incidence matrices of cuts and paths.}, language = {en} } @inproceedings{BorndoerferMuraSchlechte2009, author = {Bornd{\"o}rfer, Ralf and Mura, Annette and Schlechte, Thomas}, title = {Vickrey Auctions for Railway Tracks}, booktitle = {Operations Research Proceedings 2008}, editor = {Fleischmann, Bernhard and Borgwardt, Karl and Klein, Robert and Tuma, Axel}, publisher = {Springer-Verlag}, pages = {551 -- 556}, year = {2009}, language = {en} } @inproceedings{BorndoerferNeumannPfetsch2009, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {The Line Connectivity Problem}, booktitle = {Operations Research Proceedings 2008}, editor = {Fleischmann, Bernhard and Borgwardt, Karl and Klein, Robert and Tuma, Axel}, publisher = {Springer-Verlag}, pages = {557 -- 562}, year = {2009}, language = {en} } @inproceedings{BorndoerferGroetschelKlostermeieretal.1999, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Klostermeier, Fridolin and K{\"u}ttner, Christian}, title = {Telebus Berlin: Vehicle Scheduling in a Dial-a-Ride System}, booktitle = {Proceedings of the 7th International Workshop on Computer-Aided Transit Scheduling}, editor = {Wilson, Nigel}, publisher = {Springer Verlag}, address = {Berlin}, doi = {10.1007/978-3-642-85970-0_19}, pages = {391 -- 422}, year = {1999}, language = {en} } @inproceedings{BorndoerferSchlechteWeider2010, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Weider, Steffen}, title = {Railway Track Allocation by Rapid Branching}, 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{BorndoerferNeumannPfetsch2008, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Angebotsplanung im {\"o}ffentlichen Nahverkehr}, booktitle = {HEUREKA'08}, publisher = {FGSV Verlag}, year = {2008}, language = {en} } @misc{Borndoerfer2004, author = {Bornd{\"o}rfer, Ralf}, title = {Combinatorial Packing Problems}, journal = {The Sharpest Cut - The Impact of Manfred Padberg and His Work}, editor = {Gr{\"o}tschel, Martin}, publisher = {SIAM}, address = {Philadelphia}, pages = {19 -- 32}, year = {2004}, language = {en} } @misc{BorndoerferKarbstein2012, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {A Direct Connection Approach to Integrated Line Planning and Passenger Routing}, volume = {25}, journal = {ATMOS 2012 - 12th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}, editor = {Delling, Daniel and Liberti, Leo}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, issn = {1438-0064}, doi = {http://dx.doi.org/10.4230/OASIcs.ATMOS.2012.47}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15812}, pages = {47 -- 57}, year = {2012}, abstract = {The treatment of transfers is a major challenge in line planning. Existing models either route passengers and lines sequentially, and hence disregard essential degrees of freedom, or they are of extremely large scale, and seem to be computationally intractable. We propose a novel direct connection approach that allows an integrated optimization of line and passenger routing, including accurate estimates of the number of direct travelers, for large-scale real-world instances.}, language = {en} } @misc{BorndoerferNeumann2010, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika}, title = {Models for Line Planning with Transfers}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11742}, number = {10-11}, year = {2010}, abstract = {We propose a novel integer programming approach to transfer minimization for line planning problems in public transit. The idea is to incorporate penalties for transfers that are induced by "connection capacities" into the construction of the passenger paths. We show that such penalties can be dealt with by a combination of shortest and constrained shortest path algorithms such that the pricing problem for passenger paths can be solved efficiently. Connection capacity penalties (under)estimate the true transfer times. This error is, however, not a problem in practice. We show in a computational comparison with two standard models on a real-world scenario that our approach can be used to minimize passenger travel and transfer times for large-scale line planning problems with accurate results.}, language = {en} } @misc{BorndoerferNeumann2010, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika}, title = {Linienoptimierung - reif f{\"u}r die Praxis?}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11832}, number = {10-20}, year = {2010}, abstract = {Wir stellen in dieser Arbeit ein mathematisches Optimierungsmodell zur Bestimmung eines optimalen Linienplans vor, das sowohl die Fahrzeiten und die Anzahl der Umstiege ber{\"u}cksichtigt als auch die Kosten des Liniennetzes. Dieses Modell deckt wichtige praktische Anforderungen ab, die in einem gemeinsamen Projekt mit den Verkehrsbetrieben in Potsdam (ViP) formuliert wurden. In diesem Projekt wurde der Linienplan 2010 f{\"u}r Potsdam entwickelt. Unsere Berechnungen zeigen, dass die mathematische Optimierung in nichts einer "Handplanung" des Liniennetzes nachsteht. Im Gegenteil, mit Hilfe des Optimierungsprogramms ist es m{\"o}glich, durch Ver{\"a}nderung der Parameter mehrere verschiedene Szenarien zu berechnen, miteinander zu vergleichen und Aussagen {\"u}ber minimale Kosten und Fahrzeiten zu machen.}, language = {de} } @misc{Beckenbach2017, author = {Beckenbach, Isabel}, title = {A Hypergraph Network Simplex Algorithm}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64539}, year = {2017}, abstract = {We describe a network simplex algorithm for the minimum cost flow problem on graph-based hypergraphs which are directed hypergraphs of a particular form occurring in railway rotation planning. The algorithm is based on work of Cambini, Gallo, and Scutell{\`a} who developed a hypergraphic generalization of the network simplex algorithm. Their main theoretical result is the characterization of basis matrices. We give a similar characterization for graph-based hypergraphs and show that some operations of the simplex algorithm can be done combinatorially by exploiting the underlying digraph structure.}, language = {en} } @inproceedings{GrimmBorndoerferReutheretal.2017, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schade, Stanley and Schlechte, Thomas}, title = {A Propagation Approach to Acyclic Rolling Stock Rotation Optimization}, booktitle = {Proceedings of the IAROR conference RailLille}, year = {2017}, abstract = {The rolling stock, i.e., railway vehicles, are one of the key ingredients of a running railway system. As it is well known, the offer of a railway company to their customers, i.e., the railway timetable, changes from time to time. Typical reasons for that are different timetables associated with different seasons, maintenance periods or holidays. Therefore, the regular lifetime of a timetable is split into (more or less) irregular periods where parts of the timetable are changed. In order to operate a railway timetable most railway companies set up sequences that define the operation of timetabled trips by a single physical railway vehicle called (rolling stock) rotations. Not surprisingly, the individual parts of a timetable also affect the rotations. More precisely, each of the parts brings up an acyclic rolling stock rotation problem with start and end conditions associated with the beginning and ending of the corresponding period. In this paper, we propose a propagation approach to deal with large planning horizons that are composed of many timetables with shorter individual lifetimes. The approach is based on an integer linear programming formulation that propagates rolling stock rotations through the irregular parts of the timetable while taking a large variety of operational requirements into account. This approach is implemented within the rolling stock rotation optimization framework ROTOR used by DB Fernverkehr AG, one of the leading railway operators in Europe. Computational results for real world scenarios are presented to evaluate the approach.}, language = {en} } @inproceedings{BorndoerferSagnolSwarat2012, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar}, title = {A Case Study on Optimizing Toll Enforcements on Motorways}, volume = {22}, booktitle = {3rd Student Conference on Operational Research}, doi = {10.4230/OASIcs.SCOR.2012.1}, pages = {1 -- 10}, year = {2012}, abstract = {In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach.}, language = {en} } @article{BorndoerferSagnolSchlechteetal.2016, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schlechte, Thomas and Swarat, Elmar}, title = {Optimal duty rostering for toll enforcement inspectors}, volume = {252(2)}, journal = {Annals of Operations Research}, edition = {252}, publisher = {Springer US}, doi = {10.1007/s10479-016-2152-1}, pages = {383 -- 406}, year = {2016}, 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, we developed a personalized crew rostering model, to schedule the crews of the tours. 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 main focus of this paper extends our previous publications on how different requirements for the rostering can be modeled in detail. The second focus is on a bi-criteria analysis of the planning problem to find the balance between the control quality and the roster acceptance. Finally, computational results on real-world instances show the practicability of our method and how different input parameters influence the problem complexity.}, language = {en} }