TY - GEN A1 - Borndörfer, Ralf A1 - Euler, Ricardo A1 - Karbstein, Marika A1 - Mett, Fabian T1 - Ein mathematisches Modell zur Beschreibung von Preissystemen im öV N2 - Dieses Dokument fasst den Stand der mathematischen Modellierung von Preissystemen des öV mittels eines am ZIB entwickelten Tarifgraphenmodells zusammen. Damit sind sehr einfache und konzise Beschreibungen von Tarifstrukturen möglich, die sich algorithmisch behandeln lassen: Durch das zeitgleiche Tracken eines Pfades im Routinggraphen im Tarifgraphen kann schon während einer Routenberechnung der Preis bestimmt werden. Wir beschreiben zunächst das Konzept. Die konkrete Realisierung wird im Folgenden beispielhaft an den Tarifsystemen der Verkehrsverbünde Warnow, MDV, Vogtland, Bremen/Niedersachsen, Berlin/Brandenburg und Mittelsachsen erläutert. Anschließend folgen Überlegungen zur konkreten Implementierung von Kurzstrecken-Tarifen und zur Behandlung des Verbundübergriffs. T3 - ZIB-Report - 18-47 Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-70564 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Pfetsch, Marc T1 - Models for Line Planning in Public Transport N2 - The \emph{line planning problem} is one of the fundamental problems in strategic planning of public and rail transport. It consists of finding lines and corresponding frequencies in a public transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize its operating cost; the passengers request short travel times. We propose two new multi-commodity flow models for line planning. Their main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically. T3 - ZIB-Report - 04-10 KW - line planning KW - column generation Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7854 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - Railway Track Allocation by Rapid Branching N2 - The track allocation problem, also known as train routing problem or train timetabling problem, is to find a conflict-free set of train routes of maximum value in a railway network. Although it can be modeled as a standard path packing problem, instances of sizes relevant for real-world railway applications could not be solved up to now. We propose a rapid branching column generation approach that integrates the solution of the LP relaxation of a path coupling formulation of the problem with a special rounding heuristic. The approach is based on and exploits special properties of the bundle method for the approximate solution of convex piecewise linear functions. Computational results for difficult instances of the benchmark library TTPLIB are reported. T3 - ZIB-Report - 10-22 KW - Trassenallokationsproblem KW - Ganzzahlige Programmierung KW - Rapid-Branching-Heuristik KW - Proximale Bündelmethode KW - Optimization KW - Railway Track Allocation KW - Bundle Method KW - Rapid Branching Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11864 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Karbstein, Marika T1 - Metric Inequalities for Routings on Direct Connections N2 - 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 show that the concept of metric inequalities to characterize capacities that support a multi-commodity flow can be generalized to deal with direct connections. T3 - ZIB-Report - 14-04 KW - metric inequalities KW - direct connection KW - multi-commodity flow problem Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-44219 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika T1 - A Configuration Model for the Line Planning Problem N2 - We propose a novel extended formulation for the line planning problem in public transport. It is based on a new concept of frequency configurations that account for all possible options to provide a required transportation capacity on an infrastructure edge. We show that this model yields a strong LP relaxation. It implies, in particular, general classes of facet defining inequalities for the standard model. T3 - ZIB-Report - 13-40 KW - combinatorial optimization KW - polyhedral combinatorics KW - line planning Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-41903 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Borndörfer, Ralf A1 - Grima, Mickaël A1 - Seeling, Matthes A1 - Spies, Claudia T1 - Robust Allocation of Operating Rooms with Lognormal case Durations N2 - 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. T3 - ZIB-Report - 16-16 KW - robust optimization KW - lognormal duration KW - Hilbert's projective metric Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-58497 UR - http://www.pms2016.com/congreso/ficha.en.html SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas T1 - Der Schnellste Weg zum Ziel N2 - Wir geben eine Einführung in die Mathematik von und mit Wegen. Nicht auf dem kürzesten, aber auf einem hoffentlich kurzweiligen Weg! T3 - ZIB-Report - SC-99-32 KW - Kürzeste Wege KW - Kombinatorische Optimierung KW - Operations Research Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4209 ER - TY - GEN A1 - Schwartz, Stephan A1 - Borndörfer, Ralf A1 - Bartz, Gerald T1 - The Graph Segmentation Problem N2 - 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. T3 - ZIB-Report - 16-53 KW - toll billing KW - graph segmentation KW - combinatorial optimization Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-60750 SN - 1438-0064 ER - TY - THES A1 - Wenzel, Ron T1 - On the In-Flight Rest Assignment Problem N2 - 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. Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59328 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Balzer, Felix A1 - Borndörfer, Ralf A1 - Spies, Claudia A1 - von Dincklage, Falk T1 - Makespan and Tardiness in Activity Networks with Lognormal Activity Durations N2 - 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. T3 - ZIB-Report - 16-23 KW - scheduling KW - activity network KW - lognormal distribution Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59290 SN - 1438-0064 ER -