Flows Over Time with Flow-Dependent Transit Times
Creators: name: Langkau, Katharina
Publisher: name: Technische Universität Berlin
Year: 2003
Subjects: subject: 510 Mathematik
subject: Approximationsalgorithmen
subject: Dynamische Flüsse
subject: Kombinatorische Optimierung
subject: Netzwerkflüsse
subject: Transportprobleme
subject: Verkehrsmodelle
subject: Combinatorial Optimization
subject: Dynamic Flows
subject: Flows Over Time
subject: Network Flows
subject: Routing
subject: Traffic Models

description: Transportprobleme werden in der Kombinatorischen Optimierung üblicherweise mit Hilfe von Netzwerkflüssen modelliert. Das klassische Flussmodell ist jedoch statisch und reflektiert daher nur unzureichend die zeitliche Komponente eines Transportproblems. Ein spezielles Transportproblem entsteht bei der Straßenverkehrslenkung. Neue Technologien, wie z.B. Navigationssysteme, haben ein verstärktes Interesse an einer akkuraten Modellierung und Optimierung von Verkehrsflüssen geweckt. In der vorliegenden Arbeit werden Flussmodelle betrachtet, welche die typischen Eigenschaften von Straßenverkehr widerspiegeln. Hierbei wird auf folgende grundlegende Eigenschaften abgezielt: Im Straßenverkehr verändert sich die Netzbelastung über die Zeit hinweg. Während zur Hauptverkehrszeit eine hohe Netzbelastung herrscht, kann bereits wenige Zeit später eine entspannte Verkehrssituation vorliegen. Ein weiteres Phänomen ist die Abhängigkeit der Fahrzeiten vom Verkehrsfluss. Ein hohes Verkehrsaufkommen zieht lange Fahrzeiten und Verzögerungen nach sich. Schwerpunkt der vorliegenden Arbeit ist ein Flussmodell, das den beiden genannten Eigenschaften genügt und damit ein vereinfachtes Abbild des realen Straßenverkehrs darstellt. Die zugrundeliegende Modellannahme ist die Abhängigkeit der Fahrzeit einer Kante von der Zuflussrate auf der Kante. Innerhalb dieses Modells werden klassische Fragestellungen der Netzwerkflusstheorie behandelt. Beim "Quickest Flow Problem" ist ein Netzwerkfluss gesucht, der in minimaler Zeit eine gegebene Flussmenge von einem Startknoten zu einem Zielknoten transportiert. Dieses Problem ist bereits NP-schwer, und folglich existiert vermutlich kein polynomialer Lösungsalgorithmus. Jedoch lassen sich in polynomialer Zeit approximative Lösungen, d.h.zulässige Lösungen beweisbarer Güte, berechnen. Ein wesentlicher Bestandteil der vorliegenden Arbeit ist die Herleitung solcher Approximationsalgorithmen. In einem ersten Schritt wird eine polynomial lösbare Relaxierung des Modells vorgestellt. Diese beruht auf einer Expansion des ursprünglichen Netzwerks zu einem Netzwerk, in dem Fahrzeiten nicht mehr flussabhängig sind sondern konstant. Jede ursprüngliche Kante wird im expandierten Netzwerk mehrfach kopiert. Jede Kopie repräsentiert eine andere konstante Fahrzeit auf der Kante. Durch geschickte Wahl der Kapazitäten sind die auftretenden Fahrzeiten nur noch indirekt flussabhängig. Basierend auf dieser Relaxierung werden Approximationsalgorithmen entwickelt. Insbesondere wird das Mehrgüterflussproblem behandelt. Hierbei sind mehrere Quelle-Senke Paare gegeben und gesucht ist ein Fluss, der den Bedarf sämtlicher Quelle-Senke Paare deckt. Für das Problem wird ein voll polynomiales Approximationsschema entwickelt, d.h. ein Lösungsverfahren, das Lösungen berechnet, die eine optimale Lösung beliebig genau annähern. Da das "Quickest Flow Problem" NP-schwer ist, ist das Ergebnis aus komplexitätstheoretischer Sicht vermutlich nicht verbesserbar.