TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Klostermeier, Fridolin A1 - Küttner, Christian T1 - Telebus Berlin - Mobilität für Behinderte N2 - Steigendes Mobilitätsbedürfnis der Behinderten bei angespannter Haushaltslage --- diese Situation ergab vor drei Jahren beim Berliner Behindertenfahrdienst {\em Telebus\/} Handlungsbedarf. Gleichzeitig stie\ss{} die verwendete manuelle (Fahrzeug-)Tourenplanung mit damals etwa 1.000 Fahrtwünschen pro Tag an ihre Grenzen. Zur Lösung dieser Probleme war der effiziente Einsatz von Computern und von {\em mathematischen Optimierungsverfahren\/} erforderlich. Ergebnis des daraufhin gestarteten {\em Telebus-Projektes\/} ist die Entwicklung eines neuen, alle Arbeitsabläufe unterstützenden Computersystems, das seit über einem Jahr im Einsatz ist. Herzstück dieses Systems ist ein auf mathematischen Methoden der ganzzahligen Optimierung basierendes Verfahren zur Tourenplanung. Ziel dieses Artikels ist die Beschreibung dieses Verfahrens und seiner Verwendung bei der Behindertenbeförderung. Das Beispiel Telebus zeigt, da\ss{} der Einsatz mathematischer Optimierungstechniken neue Möglichkeiten für Kosteneinsparungen bei gleichzeitiger Serviceverbesserung auch in anderen Bereichen des ÖPNV eröffnet. T3 - ZIB-Report - SC-96-40 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2500 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Optimization of Handouts for Rolling Stock Rotations Visualization N2 - 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. T3 - ZIB-Report - ZR-16-73 Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61430 SN - 1438-0064 ER - TY - GEN A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Schlechte, Thomas T1 - Re-optimizing ICE Rotations after a Tunnel Breakdown near Rastatt N2 - Planning rolling stock movements in industrial passenger railway applications isa long-term process based on timetables which are also often valid for long periods of time. For these timetables and rotation plans, i.e., plans of railway vehicle movements are constructed as templates for these periods. During operation the rotation plans are affected by all kinds of unplanned events. An unusal example for that is the collapse of a tunnel ceiling near Rastatt in southern Germany due to construction works related to the renewal of the central station in Stuttgart. As a result the main railway connection between Stuttgart and Frankfurt am Main, located on top of the tunnel, had to be closed from August 12th to October 2nd 2017. This had a major impact on the railway network in southern Germany. Hence, all rotation plans and train schedules for both passenger and cargo traffic had to be revised. In this paper we focus on a case study for this situation and compute new rotation plans via mixed integer programming for the ICE high speed fleet of DB Fernverkehr AG one of the largest passenger railway companies in Europe. In our approach we take care of some side constraints to ensure a smooth continuation of the rotation plans after the disruption has ended. T3 - ZIB-Report - 19-02 KW - case study KW - re-optimization KW - railway rolling stock optimization KW - mixed integer programming Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-73976 SN - 1438-0064 ER - TY - GEN A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Schulz, Christof A1 - Weider, Steffen T1 - The Rolling Stock Rotation Planning Problem under Revenue Considerations N2 - In many railway undertakings a railway timetable is offered that is valid for a longer period of time. At DB Fernverkehr AG, one of our industrial partners, this results in a summer and a winter timetable. For both of these timetables rotation plans, i.e., a detailed plan of railway vehicle movements is constructed as a template for this period. Sometimes there are be periods where you know for sure that vehicle capacities are not sufficient to cover all trips of the timetable or to transport all passenger of the trips. Reasons for that could be a heavy increase of passenger flow, a heavy decrease of vehicle availability, impacts from nature, or even strikes of some employees. In such events the rolling stock rotations have to be adapted. Optimization methods are particularly valuable in such situations in order to maintain a best possible level of service or to maximize the expected revenue using the resources that are still available. In most cases found in the literature, a rescheduling based on a timetable update is done, followed by the construction of new rotations that reward the recovery of parts of the obsolete rotations. We consider a different, novel, and more integrated approach. The idea is to guide the cancellation of the trips or reconfiguration of the vehicle composition used to operate a trip of the timetable by the rotation planning process, which is based on the mixed integer programming approach presented in Reuther (2017). The goal is to minimize the operating costs while cancelling or operating a trip with an insufficient vehicle configuration in sense of passenger capacities inflicts opportunity costs and loss of revenue, which are based on an estimation of the expected number of passengers. The performance of the algorithms presented in two case studies, including real world scenarios from DB Fernverkehr AG and a railway operator in North America. T3 - ZIB-Report - 19-01 Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71339 SN - 1438-0064 ER - TY - GEN A1 - Beckenbach, Isabel A1 - Hatzel, Meike A1 - Wiederrecht, Sebastian T1 - The Tight Cut Decomposition of Matching Covered Uniformable Hypergraphs N2 - The perfect matching polytope, i.e. the convex hull of (incidence vectors of) perfect matchings of a graph is used in many combinatorial algorithms. Kotzig, Lovász and Plummer developed a decomposition theory for graphs with perfect matchings and their corresponding polytopes known as the tight cut decomposition which breaks down every graph into a number of indecomposable graphs, so called bricks. For many properties that are of interest on graphs with perfect matchings, including the description of the perfect matching polytope, it suffices to consider these bricks. A key result by Lovász on the tight cut decomposition is that the list of bricks obtained is the same independent of the choice of tight cuts made during the tight cut decomposition procedure. This implies that finding a tight cut decomposition is polynomial time equivalent to finding a single tight cut. We generalise the notions of a tight cut, a tight cut contraction and a tight cut decomposition to hypergraphs. By providing an example, we show that the outcome of the tight cut decomposition on general hypergraphs is no longer unique. However, we are able to prove that the uniqueness of the tight cut decomposition is preserved on a slight generalisation of uniform hypergraphs. Moreover, we show how the tight cut decomposition leads to a decomposition of the perfect matching polytope of uniformable hypergraphs and that the recognition problem for tight cuts in uniformable hypergraphs is polynomial time solvable. T3 - ZIB-Report - 18-61 KW - uniform hypergraphs KW - perfect matchings KW - tight cuts Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71149 SN - 1438-0064 ER - TY - GEN A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Olthoff, Mats T1 - A Solution Approach to the Vehicle Routing Problem with Perishable Goods N2 - This paper focuses on a special case of vehicle routing problem where perishable goods are considered. Deliveries have to be performed until a due date date, which may vary for different products. Storing products is prohibited. Since late deliveries have a direct impact on the revenues for these products, a precise demand prediction is important. In our practical case the product demands and vehicle driving times for the product delivery are dependent on weather conditions, i.e., temperatures, wind, and precipitation. In this paper the definition and a solution approach to the Vehicle Routing Problem with Perishable Goods is presented. The approach includes a procedure how historical weather data is used to predict demands and driving times. Its run time and solution quality is evaluated on different data sets given by the MOPTA Competition 2018. T3 - ZIB-Report - 20-03 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-77020 SN - 1438-0064 ER - TY - GEN A1 - Sagnol, Guillaume A1 - Blanco, Marco A1 - Sauvage, Thibaut T1 - The Cone of Flow Matrices: Approximation Hierarchies and Applications N2 - Let G be a directed acyclic graph with n arcs, a source s and a sink t. We introduce the cone K of flow matrices, which is a polyhedral cone generated by the matrices $\vec{1}_P\vec{1}_P^T\in\RR^{n\times n}$, where $\vec{1}_P\in\RR^n$ is the incidence vector of the (s,t)-path P. We show that several hard flow (or path) optimization problems, that cannot be solved by using the standard arc-representation of a flow, reduce to a linear optimization problem over $\mathcal{K}$. This cone is intractable: we prove that the membership problem associated to $\mathcal{K}$ is NP-complete. However, the affine hull of this cone admits a nice description, and we give an algorithm which computes in polynomial-time the decomposition of a matrix $X\in \operatorname{span} \mathcal{K}$ as a linear combination of some $\vec{1}_P\vec{1}_P^T$'s. Then, we provide two convergent approximation hierarchies, one of them based on a completely positive representation of~K. We illustrate this approach by computing bounds for the quadratic shortest path problem, as well as a maximum flow problem with pairwise arc-capacities. T3 - ZIB-Report - 17-32 KW - Flows in graphs KW - Approximation Hierarchies KW - Copositive Programming KW - Semidefinite Programming Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64399 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Karbstein, Marika T1 - A Primal-Dual Approximation Algorithm for the Steiner Connectivity Problem N2 - We extend the primal-dual approximation technique of Goemans and Williamson to the Steiner connectivity problem, a kind of Steiner tree problem in hypergraphs. This yields a (k+1)-approximation algorithm for the case that k is the minimum of the maximal number of nodes in a hyperedge minus 1 and the maximal number of terminal nodes in a hyperedge. These results require the proof of a degree property for terminal nodes in hypergraphs which generalizes the well-known graph property that the average degree of terminal nodes in Steiner trees is at most 2. T3 - ZIB-Report - 13-54 KW - Primal-Dual Approximation KW - Steiner Connectivity Problem KW - Degree Property KW - Hypergraph Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42430 SN - 1438-0064 ER - TY - GEN A1 - Grimm, Boris A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance T2 - 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) N2 - For providing railway services the company’s railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride and it is often related to the image of the company itself. Thus, it is highly desired to have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see Maroti and Kroon 2005, or Cordeau et. al. 2001 for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in Borndörfer et. al. 2015. The new approach is tested on real world instances modeling different scenarios for the ICE high speed train network in Germany and compared to the approaches of Reuther 2017 that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values. T3 - ZIB-Report - 19-61 Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-75501 SN - 1438-0064 ER - TY - GEN A1 - Tesch, Alexander T1 - A Nearly Exact Propagation Algorithm for Energetic Reasoning in O(n^2 log n) N2 - 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. T3 - ZIB-Report - 16-25 KW - Cumulative Scheduling KW - Energetic Reasoning KW - Sweep Line Algorithm Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59332 SN - 1438-0064 ER -