Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-745
Main Title: Flows Over Time with Flow-Dependent Transit Times
Author(s): Langkau, Katharina
Advisor(s): Möhring, Rolf H.
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: 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.
URI: urn:nbn:de:kobv:83-opus-6468
http://depositonce.tu-berlin.de/handle/11303/1042
http://dx.doi.org/10.14279/depositonce-745
Exam Date: 10-Sep-2003
Issue Date: 29-Sep-2003
Date Available: 29-Sep-2003
DDC Class: 510 Mathematik
Subject(s): Approximationsalgorithmen
Dynamische Flüsse
Kombinatorische Optimierung
Netzwerkflüsse
Transportprobleme
Verkehrsmodelle
Combinatorial Optimization
Dynamic Flows
Flows Over Time
Network Flows
Routing
Traffic Models
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Publications

Files in This Item:
File Description SizeFormat 
Dokument_2.pdf1.4 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.