TY - CHAP A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Löbel, Fabian A1 - Weider, Steffen T1 - Solving the Electric Bus Scheduling Problem by an Integrated Flow and Set Partitioning Approach T2 - 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024) N2 - Attractive and cost-efficient public transport requires solving computationally difficult optimization problems from network design to crew rostering. While great progress has been made in many areas, new requirements to handle increasingly complex constraints are constantly coming up. One such challenge is a new type of resource constraints that are used to deal with the state-of-charge of battery-electric vehicles, which have limited driving ranges and need to be recharged in-service. Resource constrained vehicle scheduling problems can classically be modelled in terms of either a resource constrained (multi-commodity) flow problem or in terms of a path-based set partition problem. We demonstrate how a novel integrated version of both formulations can be leveraged to solve resource constrained vehicle scheduling with replenishment in general and the electric bus scheduling problem in particular by Lagrangian relaxation and the proximal bundle method. Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0030-drops-211992 VL - 123 SP - 11:1 EP - 11:16 PB - Schloss Dagstuhl -- Leibniz-Zentrum für Informatik CY - Dagstuhl, Germany ER - TY - GEN A1 - Kokott, Andreas A1 - Löbel, Andreas T1 - Lagrangean Relaxations and Subgradient Methods for Multiple-Depot Vehicle Scheduling Problems N2 - This paper presents two Lagrangean relaxation approaches for the {\em NP}-hard multiple-depot vehicle scheduling problem in public mass transit and reports on computational investigations. Our Lagrangean relaxation approaches can be applied to generate very tight lower bounds and to compute feasible solutions efficiently. A further application is to use the Lagrangean relaxations as new pricing strategies for a delayed column generation of a branch-and-cut approach. The computational investigations are based on real-world test sets from the cities of Berlin and Hamburg having up to 25 thousand timetabled trips and 70 million dead-head trips. T3 - ZIB-Report - SC-96-22 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2330 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 - GEN A1 - Borndörfer, Ralf A1 - Langenhan, Andreas A1 - Löbel, Andreas A1 - Schulz, Christof A1 - Weider, Steffen T1 - Duty Scheduling Templates 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. T3 - ZIB-Report - 12-09 KW - duty scheduling KW - duty templates Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14699 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas ED - Aigner, Martin ED - Behrends, Ehrhard T1 - Der schnellste Weg zum Ziel T2 - Alles Mathematik Y1 - 2000 U6 - https://doi.org/10.1007/978-3-322-96366-6_5 SP - 45 EP - 76 PB - Vieweg Verlag CY - Braunschweig/Wiesbaden ER - TY - GEN A1 - Löbel, Andreas T1 - Experiments with a Dantzig-Wolfe Decomposition for Multiple-Depot Vehicle Scheduling Problems N2 - In this paper, we present a Dantzig-Wolfe decomposition for the $NP$-hard multiple-depot vehicle scheduling problem in public mass transit. It turned out that such a decomposition approach is an unsuitable method to solve such kind of multicommodity flow problems. The major obstacle to solve such problems is that the continuous master problem relaxations become too hard to be solved efficiently. Especially for problems with more than one thousand timetabled trips, the LU factorization in solving a restricted master problem takes far too much time. We will describe our computational experiments in detail and discuss the reasons why the decomposition method fails in this case. Our computational investigations are based on real-world problems from the city of Hamburg with up to 2,283 timetabled trips. Our decomposition implementation is compared with a delayed column generation to solve the linear programming (LP) relaxation directly. This LP method can solve the LP relaxations of the integer linear programming formulation exactly for truly large-scale real-world problems of the cities of Berlin and Hamburg. T3 - ZIB-Report - SC-97-16 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2852 ER - TY - GEN A1 - Löbel, Andreas T1 - Vehicle Scheduling in Public Transit and Lagrangean Pricing N2 - This paper investigates the solution of the linear programming (LP) relaxation of the multicommodity flow formulation of the multiple-depot vehicle scheduling problems arising in public mass transit. We develop a column generation technique that makes it possible to solve the huge linear programs that come up there. The technique, which we call {\em Lagrangean pricing}, is based on two different Lagrangean relaxations. We describe in detail the basic ingredients of our approach and give computational results for large-scale test data (with up to 70 million variables) from three German public transportation companies. Because of these results, we propose Lagrangean pricing as one of the basic ingredients of an effective method to solve multiple-depot vehicle scheduling problems to proven optimality. T3 - ZIB-Report - SC-96-26 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2375 ER - TY - GEN A1 - Löbel, Andreas T1 - Solving Large-Scale Real-World Minimum-Cost Flow Problems by a Network Simplex Method N2 - This paper presents a large-scale real-world application of the minimum-cost flow problem, describes some details of a new implementation of the network simplex algorithm, and reports on computational comparisions. The real-world test sets include minimum-cost flow problems that are based on single-depot vehicle scheduling problems and on a Lagrangean relaxation of multiple-depot vehicle scheduling problems. Some of the problems are extremely large with up to 42,000 nodes and 20,000,000 arcs. The standard test problems are generated with NETGEN and include parts of the DIMACS standard problems. Our network simplex code is compared with \mbox{RELAX-IV}, Cost Scaling 2 version 3.4, and CPLEX's network solver NETOPT. T3 - ZIB-Report - SC-96-07 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2184 ER - TY - GEN A1 - Grötschel, Martin A1 - Löbel, Andreas A1 - Völker, Manfred T1 - Optimierung des Fahrzeugumlaufs im Öffentlichen Nahverkehr N2 - This paper addresses the problem of scheduling vehicles in a public mass transportation system. We show how this problem can be modelled as a special multicommodity flow problem and outline the solution methodology we have developed. Based on polyhedral investigations, we have designed and implemented a branch&cut algorithm and various heuristics with which real vehicle scheduling problems of truely large scale can be solved to optimality. We describe some implementation issues and report computational results. T3 - ZIB-Report - SC-96-08 Y1 - 1996 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2195 ER - TY - GEN A1 - Löbel, Andreas A1 - Strubbe, Uwe T1 - Wagenumlaufoptimierung - Methodischer Ansatz und praktische Anwendung N2 - Im Rahmen des EDV-gestützten Systems zur {\bf{}BE}t{\bf{}R}iebseinsa{\bf{}T}zplanung und -{\bf{}A}uswertung (BERTA) der Berliner Verkehrsbetriebe (BVG) wird ein Modul zur Wagenumlaufoptimierung realisiert. In diesem Aufsatz berichten wir über die betrieblichen Anforderungen und Nebenbedingungen an eine mathematische Optimierung und erläutern unsere Konzepte zur Realisierung eines exakten mathematischen Verfahrens. T3 - ZIB-Report - SC-95-38 Y1 - 1995 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2047 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Strubbe, Uwe A1 - Völker, Manfred T1 - Zielorientierte Dienstplanoptimierung N2 - Dieser Artikel behandelt einen Ansatz zur zielorientierten Optimierung der Dienstplanung im ÖPNV. Der Ansatz zielt auf die vollständige Ausnutzung aller planerischen Freiheitsgrade unter korrekter Berücksichtigung von gesetzlichen, tariflichen, technischen und betrieblichen Rahmenbedingungen. Er basiert auf mathematischen Optimierungstechniken, die wir gegenwärtig in einem vom Bundesministerium für Bildung und Forschung ({\tt bmb+f}) geförderten Verbundprojekt in einer Kooperation zwischen der HanseCom GmbH, der IVU GmbH und dem Konrad-Zuse-Zentrum für Informationstechnik Berlin entwickeln. Es ist geplant, das Verfahren in die Softwareprodukte HOT II, MICROBUS II und OPUS zu integrieren. Verhandlungen mit den Berliner Verkehrsbetrieben über eine Projektbeteiligung und Integration unserer Software in BERTA sind zur Zeit im Gang. Wir beschreiben die Methodik des Ansatzes, diskutieren Aspekte seiner praktischen Verwendung, und wir berichten über den Stand der Entwicklung. T3 - ZIB-Report - SC-98-41 KW - Dienstplanung KW - Optimierung KW - Zielorientierte Planung Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3847 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas T1 - Optimization of Transportation Systems N2 - The world has experienced two hundred years of unprecedented advances in vehicle technology, transport system development, and traffic network extension. Technical progress continues but seems to have reached some limits. Congestion, pollution, and increasing costs have created, in some parts of the world, a climate of hostility against transportation technology. Mobility, however, is still increasing. What can be done? There is no panacea. Interdisciplinary cooperation is necessary, and we are going to argue in this paper that {\em Mathematics\/} can contribute significantly to the solution of some of the problems. We propose to employ methods developed in the {\em Theory of Optimization\/} to make better use of resources and existing technology. One way of optimization is better planning. We will point out that {\em Discrete Mathematics\/} provides a suitable framework for planning decisions within transportation systems. The mathematical approach leads to a better understanding of problems. Precise and quantitative models, and advanced mathematical tools allow for provable and reproducible conclusions. Modern computing equipment is suited to put such methods into practice. At present, mathematical methods contribute, in particular, to the solution of various problems of {\em operational planning}. We report about encouraging {\em results\/} achieved so far. T3 - ZIB-Report - SC-98-09 KW - Transportation Systems KW - Optimization KW - Discrete Mathematics Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3529 ER - TY - CHAP A1 - Grötschel, Martin A1 - Löbel, Andreas A1 - Völker, Manfred ED - Hoffmann, Karl-Heinz ED - Jäger, Willi ED - Lohmann, Thomas ED - Schunck (Hrsg.), Hermann T1 - Optimierung des Fahrzeugumlaufs im Öffentlichen Nahverkehr T2 - Mathematik Y1 - 1997 SP - 609 EP - 624 PB - Springer ER - TY - GEN A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Weider, Steffen T1 - A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit N2 - This article proposes a Lagrangean relaxation approach to solve integrated duty and vehicle scheduling problems arising in public transport. The approach is based on the proximal bundle method for the solution of concave decomposable functions, which is adapted for the approximate evaluation of the vehicle and duty scheduling components. The primal and dual information generated by the bundle method is used to guide a branch-and-bound type algorithm. Computational results for large-scale real-world integrated vehicle and duty scheduling problems with up to 1,500 timetabled trips are reported. Compared with the results of a classical sequential approach and with reference solutions, integrated scheduling offers remarkable potentials in savings and drivers' satisfaction. T3 - ZIB-Report - 04-14 KW - vehicle scheduling KW - crew scheduling KW - integrated scheduling KW - public transit KW - bundle method Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7898 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas T1 - Duty Scheduling in Public Transit N2 - This article is about \emph{adaptive column generation techniques} for the solution of duty scheduling problems in public transit. The current optimization status is exploited in an adaptive approach to guide the subroutines for duty generation, LP resolution, and schedule construction toward relevant parts of a large problem. Computational results for three European scenarios are reported. T3 - ZIB-Report - 01-02 KW - Duty Scheduling KW - Constraint Shortest Paths Problem KW - Column Generation Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6286 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Weider, Steffen T1 - Integrierte Umlauf- und Dienstplanung im Öffentlichen Nahverkehr N2 - Wir beschreiben einen Ansatz zur integrierten Umlauf- und Dienstplanung im öffentlichen Nahverkehr. Der Ansatz zielt auf die Verbesserung des Gesamtwirkungsgrades dieser beiden Planungsschritte und auf die besondere Planungsproblematik im Regionalverkehr. Wir entwickeln dazu mathematische Optimierungstechniken für den Einsatz in den Planungssystemen MICROBUS II und DIVA. T3 - ZIB-Report - 02-10 KW - Integrierte Umlauf- und Dienstplanung KW - Umlaufplanung KW - Dienstplanung KW - Optimierung KW - Regionalverkehr Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6773 ER - TY - GEN A1 - Grötschel, Martin A1 - Borndörfer, Ralf A1 - Löbel, Andreas ED - Jäger, Willi ED - Krebs, Hans-Joachim T1 - Duty Scheduling in Public Transit T2 - MATHEMATICS – Key Technology for the Future Y1 - 2003 U6 - https://doi.org/10.1007/978-3-642-55753-8_50 SP - 653 EP - 674 PB - Springer ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas ED - Butzer, Paul Leo ED - Jongen, Hubertus ED - Oberschelp, Walter T1 - Alcuin’s Transportation Problems and Integer Programming T2 - Charlemagne and his Heritage. 1200 Years of Civilization and Science in Europe. Karl der Grosse und sein Nachwirken . 1200 Jahre Kultur und Wissenschaft in Europa Y1 - 1998 VL - 2 SP - 379 EP - 409 PB - Brepols Publisher CY - Turnhout ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Weider, Steffen ED - Muñoz, J. C. ED - Voß, S. T1 - Rapid Branching JF - Public Transport N2 - We propose rapid branching (RB) as a general branch-and-bound heuristic for solving large scale optimization problems in traffic and transport. The key idea is to combine a special branching rule and a greedy node selection strategy in order to produce solutions of controlled quality rapidly and efficiently. We report on three successful applications of the method for integrated vehicle and crew scheduling, railway track allocation, and railway vehicle rotation planning. Y1 - 2013 VL - 5 IS - 1 SP - 3 EP - 23 PB - Springer Berlin Heidelberg ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Grötschel, Martin A1 - Löbel, Andreas ED - Aigner, Martin ED - Behrends, Ehrhard T1 - The Quickest Path to the Goal JF - Mathematics Everywhere Y1 - 2010 UR - http://www.ams.org/bookstore-getitem/item=MBK-72 SP - 27 EP - 51 PB - American Mathematical Society CY - Providence, Rhode Iland, USA ER -