@misc{BorndoerferGrimmReutheretal.2016, author = {Bornd{\"o}rfer, Ralf and Grimm, Boris and Reuther, Markus and Schlechte, Thomas}, title = {Optimization of Handouts for Rolling Stock Rotations Visualization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61430}, year = {2016}, abstract = {A railway operator creates (rolling stock) rotations in order to have a precise master plan for the operation of a timetable by railway vehicles. A rotation is considered as a cycle that multiply traverses a set of operational days while covering trips of the timetable. As it is well known, the proper creation of rolling stock rotations by, e.g., optimization algorithms is challenging and still a topical research subject. Nevertheless, we study a completely different but strongly related question in this paper, i.e.: How to visualize a rotation? For this purpose, we introduce a basic handout concept, which directly leads to the visualization, i.e., handout of a rotation. In our industrial application at DB Fernverkehr AG, the handout is exactly as important as the rotation itself. Moreover, it turns out that also other European railway operators use exactly the same methodology (but not terminology). Since a rotation can have many handouts of different quality, we show how to compute optimal ones through an integer program (IP) by standard software. In addition, a construction as well as an improvement heuristic are presented. Our computational results show that the heuristics are a very reliable standalone approach to quickly find near-optimal and even optimal handouts. The efficiency of the heuristics is shown via a computational comparison to the IP approach.}, language = {en} } @misc{Tesch2016, author = {Tesch, Alexander}, title = {A Nearly Exact Propagation Algorithm for Energetic Reasoning in O(n^2 log n)}, issn = {1438-0064}, doi = {10.1007/978-3-319-44953-1_32}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-59332}, year = {2016}, abstract = {In constraint programming, energetic reasoning constitutes a powerful start time propagation rule for cumulative scheduling problems (CuSP). In this paper, we first present an improved time interval checking algorithm that is derived from a polyhedral model. In a second step, we extend this algorithm to an energetic reasoning propagation algorithm with complexity O(n^2 log n) where n denotes the number of jobs. The key idea is based on a new sweep line subroutine that efficiently evaluates the relevant time intervals for all jobs. In particular, our algorithm yields at least one possible energetic reasoning propagation for each job. Finally, we show that on the vast number of relevant time intervals our approach yields the maximum possible propagation according to the energetic reasoning rule.}, language = {en} } @misc{SagnolBorndoerferGrimaetal.2016, author = {Sagnol, Guillaume and Bornd{\"o}rfer, Ralf and Grima, Micka{\"e}l and Seeling, Matthes and Spies, Claudia}, title = {Robust Allocation of Operating Rooms with Lognormal case Durations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-58497}, year = {2016}, abstract = {The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects and uncertainty handling. In this article, we formulate this problem as a job shop scheduling problem, in which the job durations follow a lognormal distribution. We propose to use a cutting-plane approach to solve a robust version of this optimization problem. To this end, we develop an algorithm based on fixed-point iterations to solve the subproblems that identify worst-case scenarios and generate cut inequalities. The procedure is illustrated with numerical experiments based on real data from a major hospital in Berlin.}, language = {en} } @article{BorndoerferFuegenschuhKlugetal.2016, author = {Bornd{\"o}rfer, Ralf and F{\"u}genschuh, Armin and Klug, Torsten and Schang, Thilo and Schlechte, Thomas and Sch{\"u}lldorf, Hanno}, title = {The Freight Train Routing Problem for Congested Railway Networks with Mixed Traffic}, volume = {50}, journal = {Transportation Science}, number = {2}, doi = {10.1287/trsc.2015.0656}, pages = {408 -- 423}, year = {2016}, abstract = {We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that the sum of all expected delays and all running times is minimal. Previous research concentrated on microscopic train routings for junctions or inside major stations. Only recently approaches were developed to tackle larger corridors or even networks. We investigate the routing problem from a strategic perspective, calculating the routes in a macroscopic transportation network of Deutsche Bahn AG. In this context, macroscopic refers to an aggregation of complex and large real-world structures into fewer network elements. Moreover, the departure and arrival times of freight trains are approximated. The problem has a strategic character since it asks only for a coarse routing through the network without the precise timings. We provide a mixed-integer nonlinear programming (MINLP) formulation for the FTRP, which is a multicommodity flow model on a time-expanded graph with additional routing constraints. The model's nonlinearities originate from an algebraic approximation of the delays of the trains on the arcs of the network by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model (MILP) by piecewise linear approximation. The latter is solved by a state-of-the art MILP solver for various real-world test instances.}, language = {en} } @inproceedings{Karbstein2016, author = {Karbstein, Marika}, title = {Integrated Line Planning and Passenger Routing: Connectivity and Transfers}, booktitle = {Operations Research Proceedings 2014}, doi = {10.1007/978-3-319-28697-6_37}, pages = {263 -- 269}, year = {2016}, 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{BeckenbachBorndoerfer2016, author = {Beckenbach, Isabel and Bornd{\"o}rfer, Ralf}, title = {An Approximation Result for Matchings in Partitioned Hypergraphs}, booktitle = {Operations Research Proceedings 2014}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-28697-6_5}, pages = {31 -- 36}, year = {2016}, abstract = {We investigate the matching and perfect matching polytopes of hypergraphs having a special structure, which we call partitioned hypergraphs. We show that the integrality gap of the standard LP-relaxation is at most \$2\sqrt{d}\$ for partitioned hypergraphs with parts of size \$\leq d\$. Furthermore, we show that this bound cannot be improved to \$\mathcal{O}(d^{0.5-\epsilon})\$.}, language = {en} } @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} } @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} } @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{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} } @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} } @inproceedings{BorndoerferSchenkerSkutellaetal.2016, author = {Bornd{\"o}rfer, Ralf and Schenker, Sebastian and Skutella, Martin and Strunk, Timo}, title = {PolySCIP}, volume = {9725}, booktitle = {Mathematical Software - ICMS 2016, 5th International Conference, Berlin, Germany, July 11-14, 2016, Proceedings}, editor = {Greuel, G.-M. and Koch, Thorsten and Paule, Peter and Sommese, Andrew}, edition = {Mathematical Software - ICMS 2016}, publisher = {Springer International Publishing}, isbn = {978-3-319-42431-6}, doi = {10.1007/978-3-319-42432-3_32}, pages = {259 -- 264}, year = {2016}, abstract = {PolySCIP is a new solver for multi-criteria integer and multi-criteria linear programs handling an arbitrary number of objectives. It is available as an official part of the non-commercial constraint integer programming framework SCIP. It utilizes a lifted weight space approach to compute the set of supported extreme non-dominated points and unbounded non-dominated rays, respectively. The algorithmic approach can be summarized as follows: At the beginning an arbitrary non-dominated point is computed (or it is determined that there is none) and a weight space polyhedron created. In every next iteration a vertex of the weight space polyhedron is selected whose entries give rise to a single-objective optimization problem via a combination of the original objectives. If the ptimization of this single-objective problem yields a new non-dominated point, the weight space polyhedron is updated. Otherwise another vertex of the weight space polyhedron is investigated. The algorithm finishes when all vertices of the weight space polyhedron have been investigated. The file format of PolySCIP is based on the widely used MPS format and allows a simple generation of multi-criteria models via an algebraic modelling language.}, language = {en} } @article{BorndoerferHoppmannKarbstein2016, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Passenger routing for periodic timetable optimization}, journal = {Public Transport}, publisher = {Springer-Verlag Berlin Heidelberg}, doi = {10.1007/s12469-016-0132-0}, year = {2016}, abstract = {The task of periodic timetabling is to determine trip arrival and departure times in a public transport system such that travel and transfer times are minimized. This paper investigates periodic timetabling models with integrated passenger routing. We show that different routing models can have a huge influence on the quality of the entire system: Whatever metric is applied, the performance ratios of timetables w.r.t. different routing models can be arbitrarily large. Computations on a real-world instance for the city of Wuppertal substantiate the theoretical findings. These results indicate the existence of untapped optimization potentials that can be used to improve the efficiency of public transport systems by integrating passenger routing.}, language = {en} } @inproceedings{Hoppmann2016, author = {Hoppmann, Heide}, title = {An Extended Formulation for the Line Planning Problem}, booktitle = {Operations Research Proceedings 2015}, doi = {10.1007/978-3-319-42902-1_2}, pages = {11 -- 17}, year = {2016}, abstract = {In this paper we present a novel extended formulation for the line planning problem that is based on what we call "configurations" of lines and frequencies. Configurations account for all possible options to provide a required transportation capacity on an infrastructure edge. The proposed configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, MIR, and multicover inequalities. These theoretical findings can be confirmed in computational results. Further, we show how this concept can be generalized to define configurations for subsets of edges; the generalized model implies additional inequalities from the line planning literature.}, language = {en} } @inproceedings{BorndoerferHoppmannKarbstein2016, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Separation of Cycle Inequalities for the Periodic Timetabling Problem}, volume = {57}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, doi = {10.4230/LIPIcs.ESA.2016.21}, year = {2016}, abstract = {Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.}, language = {en} }