Refine
Year of publication
- 2005 (11) (remove)
Document Type
- ZIB-Report (6)
- Article (3)
- Book chapter (2)
Is part of the Bibliography
- no (11)
Keywords
- Combinatorial Auctions (1)
- Internet services (1)
- Komplexität (1)
- Komplexitätstheorie (1)
- Public transport (1)
- RDF (1)
- Railway Slot Allocation (1)
- Rundreisen (1)
- TSP (1)
- Train Dispatching (1)
- Travelling-Salesman-Problem (1)
- XML (1)
- column generation (1)
- distributed systems (1)
- duty scheduling (1)
- line planning (1)
- optimale Tour (1)
- vehicle scheduling (1)
Institute
We present an approach to implement an auction of railway slots. Railway network, train driving characteristics, and safety requirements are described by a simplified, but still complex macroscopic model. In this environment, slots are modelled as combinations of scheduled track segments. The auction design builds on the iterative combinatorial auction. However, combinatorial bids are restricted to some types of slot bundles that realize positive synergies between slots. We present a bidding language that allows bidding for these slot bundles. An integer programming approach is proposed to solve the winner determination problem of our auction. Computational results for auction simulations in the Hannover-Fulda-Kassel area of the German railway network give evidence that auction approaches can induce a more efficient use of railway capacity.
The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize operating costs, the passengers want to minimize travel times. We propose a n ew multi-commodity flow model for line planning. Its main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically. We discuss properties of this model and investigate its complexity. Results with data for the city of Potsdam, Germany, are reported.
Can OR methods help the public transport industry to break even? The article gives evidence that there exist significant potentials in this direction, which can be harnessed by a combination of modern mathematical methods and local planning knowledge. Many of the planning steps in public transport are classical combinatorial problems, which can be solved in unprecedented size and quality due the rapid progress in large-scale optimization. Three examples on vehicle scheduling, duty scheduling, and integrated vehicle and duty scheduling illustrate the level that has been reached and the improvements that can be achieved today. Extensions of such methods to further questions of strategic, online, and market-oriented planning are currently investigated. In this way, OR can make a significant contribution to answer the basic but extremely difficult question ``What is a good public transport network?.
Die Anwendung mathematischer Methoden und Verfahren wird immer mehr zur Voraussetzung innovativer Produkte und Dienstleistungen. Um neue Produkte und Dienstleistungen zu entwickeln, müssen die Produktions- und technologischen Prozesse mathematisch modelliert, beschrieben und optimiert werden. Diesen Umstand Rechnung tragend, hat das Bundesministerium für Bildung und Forschung (BMBF) 1993 begonnen, den Einsatz mathematischer Verfahren und Methoden in der Mathematik über ein spezielles Mathematikprogramm zu fördern. Inzwischen hat die vierte Förderperiode des Mathematikprogramms begonnen. \par Das Medium Internet und insbesondere das WWW sind für die Sichtbarkeit und Transparenz wissenschaftlicher Resultate in den letzten zehn Jahren immer wichtiger geworden. Wer nicht im Web "'sichtbar"' ist, läuft Gefahr, nicht wahrgenommen zu werden. Intention und Ziel des durchgeführten Projekts war es, ein Konzept für eine qualitativ hochwertige und umfassende Darstellung des BMBF Mathematikprogramms, insbesondere der in den Projekten erzielten Ergebnisse, zu entwickeln und zu realisieren und damit den Stellenwert und die Akzeptanz mathematischer Forschung in der Gesellschaft zu festigen und den Wissenstransfer zwischen mathematischer Forschung sowie Forschung und Entwicklung in der Wirtschaft und dem Dienstleistungsbereich zu fördern.
Was Komplexität ist, weiß niemand so richtig. In vielen Wissenschaftsgebieten wird der Begriff Komplexität verwendet, überall mit etwas anderer Bedeutung. Mathematik und Informatik hab en eine eigene Theorie hierzu entwickelt: die Komplexitätstheorie. Sie stellt zwar grundlegende Begriffe bereit, aber leider sind die meisten wichtigen Fragestellungen noch ungelöst. Diese kurze Einführung konzentriert sich auf einen speziellen, aber bedeutenden Aspekt der Theorie: Lösbarkeit von Problemen in deterministischer und nichtdeterministischer polynomialer Zeit. Hinter der für Uneingeweihte etwas kryptischen Frage "P = NP?" verbirgt sich das derzeit wichtigste Problem der Komplexitätstheorie. Anhand dieser Fragestellung werden einige Aspekte der Theorie erläutert und formell erklärt, was "P = NP?" bedeutet. Es geht nicht nur um komplizierte algorithmische Mathematik und Informatik, sondern um grundsätzliche Fragen unserer Lebensumwelt. Kann man vielleicht beweisen, dass es für viele Probleme unseres Alltags keine effizienten Lösungsmethoden gibt?
Das Travelling-Salesman-Problem (TSP) ist das am intensivsten untersuchte kombinatorische Optimierungsproblem. In diesem Abschnitt wird eine Einführung in das TSP gegeben. Es werden Problemstellungen erläutert, Anwendungen skizziert und einige Schwierigkeiten bei der korrekten Modellierung der Zielfunktion dargelegt. Es ist gar nicht so klar, was in einem konkreten Problem die wirkliche Entfernung ist. Exakte und approximative Lösungsverfahren werden an Beispielen skizziert, und es wird angedeutet, dass man, obwohl TSPs zu den theoretisch schweren Problemen zählen, in der Praxis TSPs von atemberaubender Größe lösen kann.
Matheon
(2005)