Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-2207
Main Title: Dynamic Flows in Time-varying Networks
Translated Title: Dynamische Flüsse in zeitabhängigen Netzwerken
Author(s): Nasrabadi, Ebrahim
Advisor(s): Skutella, Martin
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Dynamische Netzwerkflüsse spielen eine wichtige Rolle in vielen Bereichen wie beispielsweise Transport, Verkehr und Logistik. Ihre zeitliche Dimension ermöglicht die realistische Modellierung von vielen realen Anwendungen. Dynamische Flüsse wurden bislang nur in Szenarien betrachtet, in denen die Eingebeparameter vorgegeben und nicht von der Zeit abhängig sind. Für viele Anwendungen ist dies zu statisch und es wäre wünschenswert, wenn das Netzwerkmodell nicht nur zeitabhängige Flüsse, sondern auch zeitabhängige Netzwerkparameter berücksichten würde. Sich ändernde Netzwerkcharakteristiken wie Kapazitäten, Kosten und Knotenbalancen wurden jedoch in der Literatur bislang nicht ausreichend betrachtet. Der Hauptgrund dafür ist, dass die entstehenden dynamischen Flussprobleme sehr schwierig zu analysieren und zu lösen sind; insbesondere, wenn die Zeit stetig und nicht diskret modelliert wird. In dieser Dissertation behandeln wir eine allgemeine Klasse von dynamischen Flussproblemen mit zeitveränderlichen Kapzitäten, Kosten und Bedarfen und entwickeln Lösungsalgorithmen für diese Probleme. Der Fokus liegt dabei auf kontinuierlichen Modelle, da diese - im Gegensatz zu diskreten Modellen - bisher in der Literatur wenig behandelt wurden. Daher wurde nur geringer Fortschritt darin erzielt, dynamische Flüsse mit zeitveränderlichen Parametern mit einem kontinuierlichen Zeitansatz zu lösen, obwohl ein kontinuierlicher Ansatz in realen Anwendungen unerlässlich ist. Das Ziel dieser Arbeit besteht darin, ein kontinuierliches Analogon zu den grundlegenden Konzepten und Techniken der statischen Netzwerkflüsse zu entwickeln. Wir präsentieren zwei Algorithmen basierend auf einem Diskretisierungansatz, welche gegen eine optimale Loesung konvergieren. Beide Algorithmen erzeugen approximierte nicht extremale Loesungen, obwohl ein Extrempunkt in der Praxis aufgrund seiner klaren und einfachen Struktur zu bevorzugen wäre. Zur Lösung dieses Problems wurde ein sogenannter Purifikationsalgorithmus entwickelt, welcher ausgehend von einer beliebigen zulässigen Loesung einen extremale Lösung erzeugt, ohne den Zielfunktionswert zu verschlechtern. Der Theorie dynamischer Flüsse mit zeitabhängigen Netzwerkparametern fehlen weiterhin grundlegende Aspekte, wie Optimalitätskriterien und Lösungsalgorithmen, welche im statischen Fall vorhanden sind. Dies motiviert die Betrachtung des kontinuierlichen Kürzeste-Wege-Problems. Dieses Problem tritt als Teilproblem bei der Erkennung negativer Kreise im Residualgraphen auf und führt somit zu einem Optimalitätskriterium für dynamische Netzwerkflüsse. Wir formulieren das kontinuierliche Kürzeste-Wege-Problem als lineares Programm im Raum der Maße. Ausgehend von diesem linearen Programm charakterisieren wir die Extrempunkte der zulässigen Region und zeigen, dass sie dynamischen Wegen entsprechen. Wir betrachten ebenfalls ein duales Programm und leiten Zusammenhänge mit dem primalen Programm her. Unter Anderem beweisen wir ein starkes Dualitätstheorem. Ausgehend von der Analyse des kontinuierlichen Kürzeste-Wege-Problems leiten wir drei Optimalitätskriterien für eine sehr allgemeine Klasse dynamischer Flussprobleme her. Diese basieren auf reduzierte Kosten, negative Kreise und starke Dualität. Weiterhin behandeln wir einen generischen Negativen-Kreis-Eliminations-Algorithmus der auf dem entsprechenden Optimalitätskriterium basiert.
Network flow problems form a large area of optimization and are central problems in operations research, computer science, applied mathematics, and many fields of engineering. They arise not only naturally in the analysis and design of large systems, such as communication, transportation, and manufacturing systems, but also in situations that apparently are quite unrelated to networks. Network flow problems have been investigated and expanded by many researchers from various point of views. The time taken to traverse an arc is typically assumed to be zero in network flows. However, time plays a vital role and temporal dynamics is a crucial feature of network flow problems occurring in many practical applications Moreover, important characteristics of real-world networks such as arc costs and capacities, demands and supplies etc. are subject to fluctuations over time. Consequently, also flow on arcs can change over time which leads to so-called dynamic network flows (also sometimes called network flows over time). In general, dynamic network flows have three aspects which distinguish them from the traditional models. Firstly, flow values on arcs change over time, which are called dynamic flows (or flows over time). Secondly, traversal of flow along an arc takes a finite time determined by the so-called transit time. Thirdly, storage is allowed at the nodes of the network for later transshipment. In this thesis we study a general class of dynamic flow problems with time-varying capacities, costs, supplies, and demands and develop algorithms for solving such problems. We mainly concentrate on a continuous time models since - in contrast to the discrete time model - little progress has been made in solving dynamic flow problems with time-varying parameters in a continuous time model despite its importance as a realistic model in real-world applications. Our aim is to mark the transition from static to dynamic network flows by developing the continuous-time analogue of those concepts and techniques which are the cornerstones of static network flows. Specifically, we develop two algorithms based on a discretization approach that compute respectively at least converge to an optimum solution. Both algorithms lead to approximate interior solutions, while one would like to have extreme point solutions. They usually have a considerably simpler structure than arbitrary feasible solutions and are more meaningful in practice. We therefore also present a purification algorithm for our dynamic flow problems, that is, an algorithm which produces an extreme point solution as output without degrading the objective function value when it is given an arbitrary feasible solution as input. The continuous time theory of dynamic network flows still lacks some of the key features such as network related optimality conditions and algorithms that are available in the static case. This is our motivation to study the continuous-time shortest path problem since this problem appears as a subproblem when we want to test, via an algorithm for shortest paths over time, the presence of negative cycles in the residual network and thus to develop network-based optimality conditions for our dynamic network flows. The continuous-time shortest path problem is formulated as a linear program in measure spaces. We characterize extreme point of the feasible region of the linear program and show that they correspond to dynamic paths. We also consider a dual problem and derive some results between the problem and its dual, specifically, a strong duality theorem. We use the results of the continuous-time shortest path problem to establish a reduced cost optimality condition, a negative cycle optimality condition, and a strong duality result for a very general class of dynamic network flows. We also discuss a generic negative cycle-canceling algorithm resulting from the corresponding optimality criterion.
URI: urn:nbn:de:kobv:83-opus-22894
http://depositonce.tu-berlin.de/handle/11303/2504
http://dx.doi.org/10.14279/depositonce-2207
Exam Date: 1-Mar-2009
Issue Date: 22-Jul-2009
Date Available: 22-Jul-2009
DDC Class: 510 Mathematik
Subject(s): Dualitätstheory
Dynamische Netzwerkflüsse
Optimalitätskriterien
Stetige lineare Programmierung
Continuous linear programming
Duality theory
Dynamic network flows
Optimality conditions
Usage rights: Terms of German Copyright Law
Appears in Collections:Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_46.pdf1.13 MBAdobe PDFThumbnail
View/Open


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