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 - CHAP A1 - Borndörfer, Ralf A1 - Neumann, Marika A1 - Pfetsch, Marc ED - Barnhart, Cynthia ED - Clausen, Uwe ED - Lauther, Ulrich ED - Möhring, Rolf T1 - Line Planning and Connectivity T2 - Models and Algorithms for Optimization in Logistics Y1 - 2009 IS - 09261 PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany CY - Dagstuhl, Germany ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Klostermeier, Fridolin A1 - Küttner, Christian T1 - Berliner Telebussystem bietet Mobilität für Behinderte JF - Der Nahverkehr Y1 - 1997 VL - 1/2 SP - 20 EP - 22 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Neumann, Marika A1 - Pfetsch, Marc ED - Haasis, Hans-Dietrich ED - Kopfer, Herbert ED - Schönberger, Jörn T1 - Optimal Fares for Public Transport T2 - Operations Research Proceedings 2005 Y1 - 2006 UR - {http://opus.kobv.de/zib/volltexte/2005/869/} SP - 29 EP - 36 PB - Springer-Verlag ER - TY - CHAP A1 - Neumann, Marika ED - Waldmann, Karl-Heinz ED - Stocker, Ulrike T1 - Fare Planning for Public Transport T2 - Operations Research Proceedings 2006 Y1 - 2007 UR - {http://opus.kobv.de/zib/volltexte/2009/1160/} SP - 61 EP - 66 PB - Springer-Verlag ER - TY - JOUR A1 - Neumann, Marika T1 - Mathematische Preisplanung im ÖPNV JF - OR News Y1 - 2007 IS - 30 SP - 29 EP - 31 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Klostermeier, Fridolin A1 - Küttner, Christian T1 - Optimierung des Berliner Behindertenfahrdienstes JF - DMV-Mitteilungen Y1 - 1997 VL - 2 SP - 38 EP - 43 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 - CHAP A1 - Heismann, Olga A1 - Borndörfer, Ralf T1 - The Random Hypergraph Assignment Problem T2 - Proceedings of the 16th International Multiconference INFORMATION SOCIETY - IS 2013 N2 - The analysis of random instances of a combinatorial optimization problem, especially their optimal values, can provide a better insight into its structure. Such an extensive analysis was theoretically and practically done for the assignment problem ("random assignment problem") and several of its generalizations. For a recent generalization of the assignment problem to bipartite hypergraphs, the hypergraph assignment problem, such results do not exist so far. We consider a random version of the hypergraph assignment problem for the simplest possible complete bipartite hypergraphs. They have only edges and proper hyperedges of size four and follow a special structure, but the hypergraph assignment problem for this type of hypergraphs is, however, already NP-hard. It can be viewed as a combination of two assignment problems. For random hyperedge costs exponentially i.i.d. with mean 1 we show computational results that suggest that the expected value of minimum cost hyperassignments converges to some value around 1.05 with a small standard deviation. The computational results also suggest that the optimal value is most probably attained with half of the maximum possible number of proper hyperedges. The main result of this paper is the proof that the expected value of a minimum cost hyperassignment which uses exactly half the possible maximum number of proper hyperedges if the vertex number tends to infinity lies between 0.3718 and 1.8310 when hyperedge costs are exponentially i.i.d. with mean 1. Y1 - 2013 SP - 599 EP - 602 ER - TY - CHAP A1 - Sagnol, Guillaume T1 - Network-related problems in optimal experimental design and second order cone programming T2 - Proceedings of PROBASTAT'2011, Tatra Mountains Mathematical Publications N2 - In the past few years several applications of optimal experimental designs have emerged to optimize the measurements in communication networks. The optimal design problems arising from this kind of applications share three interesting properties: (i) measurements are only available at a small number of locations of the network; (ii) each monitor can simultaneously measure several quantities, which can be modeled by ``multiresponse experiments"; (iii) the observation matrices depend on the topology of the network. In this paper, we give an overview of these experimental design problems and recall recent results for the computation of optimal designs by Second Order Cone Programming (SOCP). New results for the network-monitoring of a discrete time process are presented. In particular, we show that the optimal design problem for the monitoring of an AR1 process can be reduced to the standard form and we give experimental results. Y1 - 2012 U6 - https://doi.org/10.2478/v10127-012-0016-x VL - 51 SP - 161 EP - 171 ER - TY - JOUR A1 - Sagnol, Guillaume T1 - On the semidefinite representation of real functions applied to symmetric matrices JF - Linear Algebra and its Applications N2 - We present a new semidefinite representation for the trace of a real function f applied to symmetric matrices, when a semidefinite representation of the convex function f is known. Our construction is intuitive, and yields a representation that is more compact than the previously known one. We also show with the help of matrix geometric means and the Riemannian metric of the set of positive definite matrices that for a rational number p in the interval (0,1], the matrix X raised to the exponent p is the largest element of a set represented by linear matrix inequalities. We give numerical results for a problem inspired from the theory of experimental designs, which show that the new semidefinite programming formulation yields a speed-up factor in the order of 10. Y1 - 2013 U6 - https://doi.org/10.1016/j.laa.2013.08.021 VL - 439 IS - 10 SP - 2829 EP - 2843 ER - TY - CHAP A1 - Hildenbrandt, Achim A1 - Reinelt, Gerhard A1 - Heismann, Olga T1 - Integer Programming Models for the Target Visitation Problem T2 - Proceedings of the 16th International Multiconference INFORMATION SOCIETY - IS 2013 N2 - The target visitation problem (TVP) is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance traveled a tour is evaluated by taking also preferences into account which address the sequence in which the targets are visited. The problem thus is a combination of two well-known combinato- rial optimization problems: the traveling salesman and the linear ordering problem. In this paper we present several possible IP-Models for this problem and compared them to their usability for branch-and-cut approaches. Y1 - 2013 SP - 569 EP - 572 ER - TY - CHAP A1 - Heismann, Olga A1 - Borndörfer, Ralf T1 - Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning T2 - Operations Research Proceedings 2011 N2 - 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. Y1 - 2012 SP - 59 EP - 64 ER - TY - JOUR A1 - Langenhan, Andreas A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Schulz, Christof A1 - Weider, Steffen ED - Muñoz, J. C. ED - Voß, S. T1 - Duty Scheduling Templates JF - Proceedings of Conference on Advanced Systems for Public Transport 2012 (CASPT12) N2 - We propose duty templates as a novel concept to produce similar duty schedules for similar days of operation in public transit. Duty templates can conveniently handle various types of similarity requirements, and they can be implemented with ease using standard algorithmic techniques. They have produced good results in practice. Y1 - 2012 ER - TY - THES A1 - Karbstein, Marika T1 - Line Planning and Connectivity N2 - This thesis introduces the Steiner connectivity problem. It is a generalization of the well known Steiner tree problem. Given a graph G = (V, E) and a subset T ⊆ V of the nodes, the Steiner tree problem consists in finding a cost minimal set of edges connecting all nodes in T . The Steiner connectivity problem chooses, instead of edges, from a given set of paths a subset to connect all nodes in T . We show in the first part of this thesis that main results about complexity, approximation, integer programming formulations, and polyhedra can be generalized from the Steiner tree problem to the Steiner connectivity problem. An example for a straightforward generalization are the Steiner partition inequalities, a fundamental class of facet defining inequalities for the Steiner tree problem. They can be defined for the Steiner connectivity problem in an analogous way as for the Steiner tree problem. An example for a generalization that needs more effort is the definition of a directed cut formulation and the proof that this dominates the canonical undirected cut formulation enriched by all Steiner partition inequalities. For the Steiner connectivity problem this directed cut formulation leads to extended formulations, a concept that is not necessary for the Steiner tree problem. There are also major differences between both problems. For instance, the case T = V for the Steiner connectivity problem is equivalent to a set covering problem and, hence, not a polynomial solvable case as in the Steiner tree problem. The Steiner connectivity problem is not only an interesting generalization of the Steiner tree problem but also the underlying connectivity problem in line planning with inte- grated passenger routing. The integrated line planning and passenger routing problem is an important planning problem in service design of public transport and the topic of the second part. Given is the infrastructure network of a public transport system where the edges correspond to streets and tracks and the nodes correspond to stations/stops of lines. The task is to find paths in the infrastructure network for lines and passengers such that the capacities of the lines suffice to transport all passengers. Existing models in the literature that integrate a passenger routing in line planning either treat transfers in a rudimentary way and, hence, neglect an important aspect for the choice of the pas- senger routes, or they treat transfers in a too comprehensive way and cannot be solved for large scale real world problems. We propose a new model that focuses on direct connections. The attractiveness of transfer free connections is increased by introducing a transfer penalty for each non-direct connection. In this way, a passenger routing is computed that favors direct connections. For the computation of this model we also implemented algorithms influenced by the results for the Steiner connectivity problem. We can compute with our model good solutions that minimize a weighted sum of line operating costs and passengers travel times. These solutions improve the solutions of an existing approach, that does not consider direct connections, by up to 17%. In contrast to a comprehensive approach, that considers every transfer and for which we could not even solve the root LP within 10 hours for large instances, the solutions of the new model, computed in the same time, are close to optimality (<1%) or even optimal for real world instances. In a project with the Verkehr in Potsdam GmbH to compute the line plan for 2010 we showed that our approach is applicable in practice and can be used to solve real world problems. Y1 - 2013 UR - www.zib.de/karbstein/scplpp.pdf SN - 978-3-8439-1062-0 ER - TY - JOUR A1 - Hiller, Benjamin A1 - Klug, Torsten A1 - Tuchscherer, Andreas T1 - An Exact Reoptimization Algorithm for the Scheduling of Elevator Groups JF - Flexible Services and Manufacturing Journal Y1 - 2013 U6 - https://doi.org/10.1007/s10696-013-9175-6 SP - 1 EP - 24 ER - TY - CHAP A1 - Schlechte, Thomas T1 - Railway Track Allocation BT - Selected Papers of the International Annual Conference of the German Operations Research Society (GOR), Leibniz University of Hannover, Germany, September 5-7, 2012 T2 - Operations Research Proceedings Y1 - 2012 U6 - https://doi.org/10.1007/978-3-319-00795-314 SP - 15 EP - 20 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Karbstein, Marika A1 - Pfetsch, Marc T1 - The Steiner connectivity problem JF - Mathematical Programming A Y1 - 2013 U6 - https://doi.org/10.1007/s10107-012-0564-5 VL - 142 IS - 1 SP - 133 EP - 167 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Klostermeier, Fridolin A1 - Küttner, Christian T1 - Telebus-Disposition: Ein Konzept zur Serviceverbesserung bei gleichzeitiger Kostensenkung.[nur hausintern] N2 - "`Telebus"' ist der soziale Behindertenfahrdienst im Land Berlin. Das Telebus-Forschungsprojekt des Konrad-Zuse-Zentrums für Informationstechnik (ZIB) hat das Ziel, den Fahrdienst (insbesondere die Disposition der Telebusse) zu verbessern, d.h. kundenfreundlicher zu gestalten und gleichzeitig billiger zu machen. In diesem Bericht werden die bisherigen Ergebnisse dargestellt und weitere Möglichkeiten zur Verbesserung des Service und zur Reduzierung der Kosten skizziert. \originalTeX T3 - ZIB-Report - TR-93-03 Y1 - 1993 N1 - Volltext nur Hausintern ER -