Refine
Year of publication
Document Type
- ZIB-Report (17)
- In Proceedings (6)
- Article (3)
- Book chapter (2)
- In Collection (2)
- Doctoral Thesis (1)
- Other (1)
Is part of the Bibliography
- no (32)
Keywords
Institute
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.
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.
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.
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.
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ür Informatik, Verkehrs- und Umweltplanung mbH (IVU), Berlin.
Rapid Branching
(2012)
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.