Loading…
Netzwerke sind ein allgegenwärtiges Element unserer heutigen Welt -- von Straßen und Schienen über Strom-, Gas- und Wasserleitungen bis hin zu Anwendungen in Biologie, Chemie, Wirtschaft und anderen Bereichen gibt es viele Strukturen, die sich als Netzwerke modellieren lassen. Die Problematik, Dinge durch ein Netzwerk zu transportieren, führte zum Forschungsgebiet der Netzwerkflüsse. Ein Teilgebiet der Netzwerkflüsse sind Netzwerkflüsse über Zeit (oder dynamische Netzwerkflüsse), die auch zeitliche Aspekte von Transportvorgängen modellieren können.
In der vorliegenden Arbeit werden solche Netzwerkflüsse über Zeit studiert. Dazu werden einerseits algorithmische Techniken zu ihrer Lösung, aber auch komplexitätstheoretische Resultate beschrieben, die uns Grenzen für die Effizienz von Algorithmen aufzeigen. Algorithmen zur Lösung von dynamischen Netzwerkflussproblemen beruhen in der Regel entweder auf Zeitexpansion, einer Reduktion, welche die zeitliche Dimension durch ein stark vergrößertes Netzwerk ersetzt, oder auf einer Ausnutzung einer zeitlich wiederholten Struktur der Probleme.
Wenn die Vergrößerung durch Zeitexpansion in effizient beherrschbaren Grenzen gehalten werden soll, ist eine Variante von Zeitexpansion nötig, die Zeitkondensierung genannt wird. Diese Technik liefert Approximationsalgorithmen für viele dynamische Netzwerkflussprobleme. In dieser Arbeit wird sowohl Zeitexpansion als auch Zeitkondensierung in einer sehr generellen Form beschrieben, die eine Anwendung auf viele Probleme erlaubt. Klassische Zeitkondensierung ist jedoch einigen Beschränkungen unterworfen -- zum Beispiel funktioniert sie nicht für Probleme, in denen Fluss unterwegs nicht warten darf. Wir beschreiben eine Verallgemeinerung von Zeitkondensierung, die den Anwendungsbereich der Technik auf diese Probleme ausdehnt. Diese Technik wird als Sequenzkondensierung bezeichnet und beruht darauf, dass nicht einzelne Kanten eines Netzwerks als Grundlage der Kondensierung benutzt werden, sondern Sequenzen von Kanten mit bestimmten Gesamtlängen. Dies führt zu einer LP-Formulierung, deren duales LP eine Separierungsproblem besitzt, welches effiziente Approximierungsschemata (FPTAS) erlaubt. Diese führt zu FPTASen für Probleme, in denen Warten verboten ist, was die bis dahin bekannten 2-Approximationen deutlich verbessert. Ferner untersuchen wir, wie sich die Möglichkeit zu Warten auf den Wert von Optimallösungen auswirkt. Wir zeigen, dass Warten den Wert einer Optimallösung um einen Faktor von 2 verbessern kann.
Des Weiteren untersuchen wir verallgemeinerte Flüsse über Zeit, in den sich die Flussmenge während des Transports verändern kann. Diese Flüsse können mittels Zeitexpansion und -kondensierung behandelt werden. Wir zeigen, dass diese Flüsse selbst in Spezialfällen NP-schwer sind und beschreiben Approximationsschemata zu ihrer Lösung. Diese beruhen einerseits auf Zeitkondensierung, und andererseits auf einer Ausnutzung von zeitlich wiederholten Strukturen.
Eine wichtige Anwendung von Netzwerkflüssen über Zeit sind Evakuierungen. Hier ist es für eine gute Planung wichtig, dass möglichst viele Menschen gerettet werden, unabhängig von der zur Verfügung stehenden Zeit. Dies von Earliest Arrival Flüssen gewährleistet. Wir beschreiben in dieser Arbeit, wie Zeitexpansion und -kondensierung für die Berechnung fast optimaler Earliest Arrival Flüsse genutzt werden kann.
Im Falle von Evakuierungen besteht oft nicht nur die Möglichkeit, die Fluchtrouten zu bestimmen, sondern auch das Straßennetzwerk zu modifizieren in dem die Richtung von Spuren angepasst wird. In dieser Arbeit betrachten wir ein einfaches Modell, in dem die Richtung von Spuren zu Beginn der Evakuierung festgelegt wird und dann bestehen bleibt. Für dieses Modell analysieren wir den Preis der Orientierung, der den Unterschied im Wert der Optimallösung zwischen einer Orientierung und einer perfekten Nutzung des ungerichteten Straßennetzes angibt. Wir geben scharfe Schranken für den Preis der Orientierung und beschreiben Algorithmen, die diese Schranken erreichen.
Networks are omnipresent in our current world -- ranging from streets, railroads, gas and water pipelines, power cables or applications in biology, chemistry or economy there are many structures which can be modeled as networks. The problem of transporting (possibly abstract) commodities through a network gave rise to the research field of network flows. A special class of network flows are network flows over time (or dynamic network flows) which are capable of modelling temporal aspects of transportation processes.
In this thesis we study such network flows over time. We will develop algorithmic techniques for their computation, as well as complexity theoretic results showing us bounds for the efficiency of algorithms. Algorithmic techniques for network flow over time problems are usually either based on time expansion, a reduction which replaces the temporal dimension by a huge increase in network size, or on exploiting temporally repeated structures in the problem.
If the increase in network size caused by time expansion is to be contained in efficiently solvable bounds, we have to employ a variant of time expansion called time condensation. This technique allows us to design approximation algorithms for many network flow over time problems. In this thesis, we will describe time expansion and condensation in a very general form which allows an application to many problems. Classic time condensation is subject to some restrictions, however -- for example, it does not work for problems where flow is not allowed to wait. We design a generalization of time condensation which can be applied to such problems. This generalization is called sequence condensation and is based on the idea of using sequences of the network's arcs as a base for the condensation, instead of the individual arcs. This leads to an LP formulation whose dual LP has a separation problem which allows for a fully polynomial-time approximation scheme (FPTAS). This allows us to create FPTASes for problems in which waiting is forbidden, which improves on the previously known 2-approximation. Furthermore, we study how the possibility of waiting affects the value of optimal solutions and show that waiting can improve the value by a factor of 2.
We also study generalized flows over time which allow for gains and losses during the transportation. These flows can be handled by time expansion and condensation. We show that the corresponding flow problems are NP-hard even in special cases and describe FPTASes for their solution. These are based on time condensation and exploiting temporally repeated structures.
An important application of network flows over time are evacuations. Here it is important that as many people as possible are saved, independent of the available time which might not be known beforehand. This can be achieved by earliest arrival flows. We describe in this thesis how time expansion and condensation can be used for the computation of nearly optimal earliest arrival flows.
In the case of evacuations it is often not only possible to choose the escape routes, but also to modify the street network by changing the orientation of lanes. We study a simple model where lanes can be oriented once before the evacuation begins. For this model, we study the price of orientation, which specifies the difference between the value of an optimal solution in an orientation and a perfect usage of the undirected road network. We give tight bounds for the price of orientation and describe algorithms for obtaining these bounds.
