@misc{BorndoerferLoebelWeider, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {Integrierte Umlauf- und Dienstplanung im {\"O}ffentlichen Nahverkehr}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6773}, number = {02-10}, abstract = {Wir beschreiben einen Ansatz zur integrierten Umlauf- und Dienstplanung im {\"o}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{\"u}r den Einsatz in den Planungssystemen MICROBUS II und DIVA.}, language = {de} } @misc{BorndoerferLoebelWeider, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7898}, number = {04-14}, abstract = {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.}, language = {en} } @misc{BorndoerferLoebelStrubbeetal., author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Strubbe, Uwe and V{\"o}lker, Manfred}, title = {Zielorientierte Dienstplanoptimierung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3847}, number = {SC-98-41}, abstract = {Dieser Artikel behandelt einen Ansatz zur zielorientierten Optimierung der Dienstplanung im {\"O}PNV. Der Ansatz zielt auf die vollst{\"a}ndige Ausnutzung aller planerischen Freiheitsgrade unter korrekter Ber{\"u}cksichtigung von gesetzlichen, tariflichen, technischen und betrieblichen Rahmenbedingungen. Er basiert auf mathematischen Optimierungstechniken, die wir gegenw{\"a}rtig in einem vom Bundesministerium f{\"u}r Bildung und Forschung ({\tt bmb+f}) gef{\"o}rderten Verbundprojekt in einer Kooperation zwischen der HanseCom GmbH, der IVU GmbH und dem Konrad-Zuse-Zentrum f{\"u}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 {\"u}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 {\"u}ber den Stand der Entwicklung.}, language = {de} } @misc{KokottLoebel, author = {Kokott, Andreas and L{\"o}bel, Andreas}, title = {Lagrangean Relaxations and Subgradient Methods for Multiple-Depot Vehicle Scheduling Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2330}, number = {SC-96-22}, abstract = {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.}, language = {en} } @misc{Loebel, author = {L{\"o}bel, Andreas}, title = {Vehicle Scheduling in Public Transit and Lagrangean Pricing}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2375}, number = {SC-96-26}, abstract = {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.}, language = {en} } @misc{Loebel, author = {L{\"o}bel, Andreas}, title = {Solving Large-Scale Real-World Minimum-Cost Flow Problems by a Network Simplex Method}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2184}, number = {SC-96-07}, abstract = {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.}, language = {en} } @misc{GroetschelLoebelVoelker, author = {Gr{\"o}tschel, Martin and L{\"o}bel, Andreas and V{\"o}lker, Manfred}, title = {Optimierung des Fahrzeugumlaufs im {\"O}ffentlichen Nahverkehr}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2195}, number = {SC-96-08}, abstract = {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.}, language = {de} } @misc{BorndoerferGroetschelLoebel, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Der Schnellste Weg zum Ziel}, doi = {10.1007/978-3-322-96366-6_5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4209}, number = {SC-99-32}, abstract = {Wir geben eine Einf{\"u}hrung in die Mathematik von und mit Wegen. Nicht auf dem k{\"u}rzesten, aber auf einem hoffentlich kurzweiligen Weg!}, language = {de} } @misc{Loebel, author = {L{\"o}bel, Andreas}, title = {Experiments with a Dantzig-Wolfe Decomposition for Multiple-Depot Vehicle Scheduling Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2852}, number = {SC-97-16}, abstract = {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.}, language = {en} } @misc{Loebel, author = {L{\"o}bel, Andreas}, title = {Solving Large-Scale Multiple-Depot Vehicle Scheduling Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2866}, number = {SC-97-17}, abstract = {This paper presents an integer linear programming approach with delayed column generation for the {\em NP} Multiple-Depot Vehicle Scheduling Problem (MDVSP) in public mass transit. We describe in detail all basic ingredients of our approach that are indispensable to solve truly large-scale real-world instances to optimality, and we report on computational investigations that are based on real-world instances from the city of Berlin, the city of Hamburg, and the region around Hamburg. These real-world instances have up to 25 thousand timetabled trips and 70 million dead-head trips. Computational tests using the data of the Hamburger Hochbahn AG indicate savings of several vehicles and a cost reduction of about 10\\% compared with the solution provided by HOT II, the vehicle scheduling tool of the HanseCom GmbH, Hamburg. Parts of our algorithms are already integrated in the BERTA system of the Berliner Verkehrsbetriebe (BVG) and will soon be integrated in the MICROBUS system of the Gesellschaft f{\"u}r Informatik, Verkehrs- und Umweltplanung mbH (IVU), Berlin.}, language = {en} } @misc{BorndoerferGroetschelLoebel, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Alcuin's Transportation Problems and Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1932}, number = {SC-95-27}, abstract = {The need to solve {\it transportation problems\/} was and still is one of the driving forces behind the development of the mathematical disciplines of graph theory, optimization, and operations research. Transportation problems seem to occur for the first time in the literature in the form of the four ''River Crossing Problems'' in the book Propositiones ad acuendos iuvenes. The {\it Propositiones\/} ---the oldest collection of mathematical problems written in Latin--- date back to the \$8\$th century A.D. and are attributed to Alcuin of York, one of the leading scholars of his time, a royal advisor to Charlemagne at his Frankish court. Alcuin's river crossing problems had no impact on the development of mathematics. However, they already display all the characteristics of today's large-scale real transportation problems. From our point of view, they could have been the starting point of combinatorics, optimization, and operations research. We show the potential of Alcuin's problems in this respect by investigating his problem~18 about a wolf, a goat and a bunch of cabbages with current mathematical methods. This way, we also provide the reader with a leisurely introduction into the modern theory of integer programming.}, language = {en} } @misc{LoebelStrubbe, author = {L{\"o}bel, Andreas and Strubbe, Uwe}, title = {Wagenumlaufoptimierung - Methodischer Ansatz und praktische Anwendung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2047}, number = {SC-95-38}, abstract = {Im Rahmen des EDV-gest{\"u}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 {\"u}ber die betrieblichen Anforderungen und Nebenbedingungen an eine mathematische Optimierung und erl{\"a}utern unsere Konzepte zur Realisierung eines exakten mathematischen Verfahrens.}, language = {de} } @misc{BorndoerferGroetschelLoebel, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Optimization of Transportation Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3529}, number = {SC-98-09}, abstract = {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.}, language = {en} } @misc{BorndoerferGroetschelLoebel, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Duty Scheduling in Public Transit}, doi = {10.1007/978-3-642-55753-8_50}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6286}, number = {01-02}, abstract = {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.}, language = {en} } @misc{BorndoerferLangenhanLoebeletal., author = {Bornd{\"o}rfer, Ralf and Langenhan, Andreas and L{\"o}bel, Andreas and Schulz, Christof and Weider, Steffen}, title = {Duty Scheduling Templates}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14699}, number = {12-09}, abstract = {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.}, language = {en} } @misc{BorndoerferLoebelReutheretal., author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {Rapid Branching}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14728}, number = {12-10}, abstract = {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.}, language = {en} } @misc{BorndoerferGroetschelLoebel, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {The Quickest Path to the Goal}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11840}, number = {10-21}, abstract = {We provide an introduction into the mathematics of and with paths. Not on the shortest, but hopefully on an entertaining path!}, language = {en} } @incollection{GroetschelLoebelVoelker1997, author = {Gr{\"o}tschel, Martin and L{\"o}bel, Andreas and V{\"o}lker, Manfred}, title = {Optimierung des Fahrzeugumlaufs im {\"O}ffentlichen Nahverkehr}, series = {Mathematik}, booktitle = {Mathematik}, editor = {Hoffmann, Karl-Heinz and J{\"a}ger, Willi and Lohmann, Thomas and Schunck (Hrsg.), Hermann}, publisher = {Springer}, pages = {609 -- 624}, year = {1997}, language = {en} } @incollection{BorndoerferGroetschelLoebel1998, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Alcuin's Transportation Problems and Integer Programming}, series = {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}, volume = {2}, booktitle = {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}, editor = {Butzer, Paul Leo and Jongen, Hubertus and Oberschelp, Walter}, publisher = {Brepols Publisher}, address = {Turnhout}, pages = {379 -- 409}, year = {1998}, language = {en} } @misc{GroetschelBorndoerferLoebel2003, author = {Gr{\"o}tschel, Martin and Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas}, title = {Duty Scheduling in Public Transit}, series = {MATHEMATICS - Key Technology for the Future}, journal = {MATHEMATICS - Key Technology for the Future}, editor = {J{\"a}ger, Willi and Krebs, Hans-Joachim}, publisher = {Springer}, doi = {10.1007/978-3-642-55753-8_50}, pages = {653 -- 674}, year = {2003}, language = {en} } @article{LangenhanBorndoerferLoebeletal., author = {Langenhan, Andreas and Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Schulz, Christof and Weider, Steffen}, title = {Duty Scheduling Templates}, series = {Proceedings of Conference on Advanced Systems for Public Transport 2012 (CASPT12)}, journal = {Proceedings of Conference on Advanced Systems for Public Transport 2012 (CASPT12)}, editor = {Mu{\~n}oz, J. C. and Voß, S.}, abstract = {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.}, language = {en} } @article{BorndoerferLoebelReutheretal.2013, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {Rapid Branching}, series = {Public Transport}, volume = {5}, journal = {Public Transport}, number = {1}, editor = {Mu{\~n}oz, J. C. and Voß, S.}, publisher = {Springer Berlin Heidelberg}, pages = {3 -- 23}, year = {2013}, abstract = {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.}, language = {en} } @article{BorndoerferGroetschelLoebel2010, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {The Quickest Path to the Goal}, series = {Mathematics Everywhere}, journal = {Mathematics Everywhere}, editor = {Aigner, Martin and Behrends, Ehrhard}, publisher = {American Mathematical Society}, address = {Providence, Rhode Iland, USA}, pages = {27 -- 51}, year = {2010}, language = {en} } @inproceedings{BorndoerferLoebelWeider2008, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit}, series = {Computer-aided Systems in Public Transport}, volume = {600}, booktitle = {Computer-aided Systems in Public Transport}, editor = {Hickman, Mark and Mirchandani, Pitu and Voß, Stefan}, publisher = {Springer-Verlag}, pages = {3 -- 24}, year = {2008}, language = {en} } @inproceedings{BorndoerferLoebelStrubbeetal.1999, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Strubbe, Uwe and V{\"o}lker, Manfred}, title = {Zielorientierte Dienstplanoptimierung}, series = {Heureka '99}, booktitle = {Heureka '99}, publisher = {Forschungsgesellschaft f{\"u}r Strassen- und Verkehrswesen}, address = {K{\"o}ln}, pages = {171 -- 194}, year = {1999}, language = {en} } @inproceedings{BorndoerferGroetschelLoebel1994, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Umlaufplanung im {\"o}ffentlichen Nahverkehr}, series = {Anwendungsorientierte Verbundprojekte auf dem Gebiet der Mathematik}, booktitle = {Anwendungsorientierte Verbundprojekte auf dem Gebiet der Mathematik}, year = {1994}, language = {en} } @inproceedings{BorndoerferGroetschelLoebel1997, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Dienstplanung im {\"o}ffentlichen Nahverkehr}, series = {Mathematische Verfahren zur L{\"o}sung von Problemstellungen in Industrie und Wirtschaft}, booktitle = {Mathematische Verfahren zur L{\"o}sung von Problemstellungen in Industrie und Wirtschaft}, year = {1997}, language = {en} } @inproceedings{BorndoerferGroetschelLoebeletal.2001, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas and Weider, Steffen}, title = {Integrierte Umlauf- und Dienstplanung im {\"o}ffentlichen Nahverkehr}, series = {Neue Mathematische Verfahren in Industrie und Dienstleistungen}, booktitle = {Neue Mathematische Verfahren in Industrie und Dienstleistungen}, year = {2001}, language = {en} } @misc{BorndoerferLoebel2000, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas}, title = {Dienstplanoptimierung im {\"O}PNV}, year = {2000}, language = {en} } @misc{BorndoerferGroetschelLoebel2000, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Der schnellste Weg zum Ziel}, series = {Alles Mathematik}, journal = {Alles Mathematik}, editor = {Aigner, Martin and Behrends, Ehrhard}, publisher = {Vieweg Verlag}, address = {Braunschweig/Wiesbaden}, doi = {10.1007/978-3-322-96366-6_5}, pages = {45 -- 76}, year = {2000}, language = {en} } @inproceedings{BorndoerferLoebelWeider2002, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {Integrierte Umlauf- und Dienstplanung im {\"O}ffentlichen Verkehr}, series = {Heureka '02}, booktitle = {Heureka '02}, publisher = {Forschungsgesellschaft f{\"u}r Straßen- und Verkehrswesen}, address = {K{\"o}ln}, pages = {77 -- 98}, year = {2002}, language = {en} } @phdthesis{Loebel, author = {L{\"o}bel, Andreas}, title = {Optimal Vehicle Scheduling in Public Transit}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10169}, abstract = {Die vorliegende Dissertation besch{\"a}ftigt sich mit der Optimierung der Fahrzeugeinsatzplanung im {\"o}ffentlichen Personennahverkehr. Dieses Problem ist f{\"u}r die meisten praxisrelevanten F{\"a}lle schwierig (Ar'P-schwer). In dieser Arbeit pr{\"a}sentieren wir Methoden der ganzzahligen linearen Programmierung zur L{\"o}sung dieses Planungsproblems. "Vern{\"u}nftige" mathematische Formulierungen des Fahrzeugeinsatzplanungsproblems basieren auf Netzwerkfluß-Modellen und ent sprechenden ganzzahligen linearen Programmen (LP). Dies sind sogenannte bogenorientierte Mehrg{\"u}terfluß-Modelle bzw. pfadorientierte SetPartitioning-Modelle. Wir besch{\"a}ftigen uns mit beiden Ans{\"a}tzen, der Schwerpunkt liegt aber auf dem bogenorientierte Mehrg{\"u}terfluß-Modell Mathematisch bearbeiten wir diese Modelle mit Branch-und-Cut- bzw. Branch-und-Cutund-Price-Methoden. Reale Anwendungen f{\"u}hren zu riesigen LPs mit einigen Millionen ganzzahligen Variablen. Die Behandlung solcher LPs erfordert Spalten-Erzeugungs- Verfahren (auch Column-Generation-Verfahren genannt). Basierend auf Lagrange-Relaxationen entwickeln wir hierzu neue Verfahren zur Auswahl der zu erzeugenden Spalten, die wir Lagrange-Pricing nennen. Lagrange-Pricing-Techniken haben es erstmalig erm{\"o}glicht, LPs dieser Art mit rund 70 Millionen Variablen zu l{\"o}sen. F{\"u}r den bogenorientierten (Mehrg{\"u}ter)Fluß-Zugang beschreiben wir ausf{\"u}hrlich, wie Lagrange-Relaxationen sowie die LP-Relaxation effizient gel{\"o}st werden. Zus{\"a}tzlich schlagen wir eine Heuristik vor, die schnell gute L{\"o}sungen erzeugt. Diese Heuristik beruht auf einem sog. Schedule-FirstClusterSecond-Ansatz. Eine zentrale Aufgabe bei der L{\"o}sung dieser primalen und dualen Probleme ist dabei die effiziente Behandlung von Problemen mit einem Depot. Wir zeigen, daß das bogenorientierte Mehrg{\"u}terfluß-Modell durch eine geeignete Anwendung der Dantzig-Wolfe-Dekomposition in ein pfadorientiertes SetPartitioning-Modell {\"u}berf{\"u}hrt werden kann. Der zweite Teil dieser Arbeit pr{\"a}sentiert die Rechenergebnisse zu den von uns entwickelten und implementierten Verfahren. Diese Untersuchungen basieren auf realen Testdaten von drei großen deutschen Nahverkehrsunternehmen. Die implementierten Codes arbeiten zuverl{\"a}ssig und stabil. Die mit diesen Verfahren durchgef{\"u}hrten Testl{\"a}ufe lieferten hervorragende Ergebnisse: Bis auf ein Problem k{\"o}nnen alle Beispiele optimal gel{\"o}st werden. Die L{\"o}sungen des Branch-and-Cut-Verfahrens wurden auch mit den Planungsergebnissen der in der Praxis gegenw{\"a}rtig eingesetzten Verfahren verglichen: Wir konnten zus{\"a}tzlich mehrere Fahrzeuge einsparen sowie eine Kostenreduktion von bis zu 10 \% aufzeigen. Der m{\"o}gliche Nutzen dieser Methoden ist enorm. Beispielsweise rechnet die BVG damit, den Planungsprozeß mit den von uns entwickelten Softwaretools deutlich straffen und j{\"a}hrlich Einsparungen in H{\"o}he von rund 100 Millionen Mark erzielen zu k{\"o}nnen, siehe den Artikel Auf Sparkurs zum Ziel im Rheinischer Merkur, Nummer 39, von Schmidt [1997] Teile der vorgestellten Methoden wurden bereits in die Planungssysteme BERTA (der Berliner Verkehrsbetriebe (BVG)) und MICROBUS II (der IVU Gesellschaft f{\"u}r Informatik, Verkehrs und Umweltplanung mbH, Berlin) integriert. Dar{\"u}ber hinaus hat auch die Forschungsabteilung der SIEMENS AG in M{\"u}nchen dieses System erworben.}, language = {en} }