# Library

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
• ddc:000  (14)
Source
Years
Keywords
Language
• 1
Unknown
Publication Date: 2014-02-26
Description: 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.
Keywords: ddc:000
Language: German
Type: reportzib , doc-type:preprint
Format: application/postscript
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 2
Publication Date: 2014-11-02
Description: 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.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/postscript
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 3
Unknown
Publication Date: 2020-08-05
Description: Wir geben eine Einführung in die Mathematik von und mit Wegen. Nicht auf dem kürzesten, aber auf einem hoffentlich kurzweiligen Weg!
Keywords: ddc:000
Language: German
Type: reportzib , doc-type:preprint
Format: application/postscript
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 4
Unknown
Publication Date: 2020-03-09
Description: 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.
Keywords: ddc:000
Language: German
Type: reportzib , doc-type:preprint
Format: text/plain
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 5
Unknown
Publication Date: 2020-08-05
Description: 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.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/postscript
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 6
Publication Date: 2014-11-02
Description: 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.
Keywords: ddc:000
Language: German
Type: reportzib , doc-type:preprint
Format: application/postscript
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 7
Publication Date: 2014-11-02
Description: 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.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/postscript
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 8
Publication Date: 2014-11-02
Description: 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.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/pdf
Format: application/postscript
Format: application/postscript
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 9
Unknown
Publication Date: 2020-03-09
Description: 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.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/postscript
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 10
Publication Date: 2014-11-02
Description: 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.
Keywords: ddc:000
Language: English
Type: reportzib , doc-type:preprint
Format: application/postscript
Format: application/pdf
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
Close ⊗