Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-3327
Main Title: Network Flow Problems Arising From Evacuation Planning
Translated Title: Netzwerkflussprobleme, welche sich in der Evakuierungsplanung ergeben
Author(s): Dressler, Daniel
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: Wir untersuchen die Einsatzmöglichkeiten der Netzwerkflusstheorie in der Evakuierungsplanung. Wir gehen davon aus, dass uns ein Netzwerk des zu evakuierenden Gebiets zur Verfügung steht. Darin modellieren Quellen die Ausgangspositionen und Senken die sicheren Bereiche für die Personen. Die Kanten haben Kapazitäten, welche die Flussrate in die Kante beschränken, und Durchgangszeiten. In einem dynamischen Fluss erreichen die Flusseinheiten das andere Ende einer Kante, nachdem die Durchgangszeit verstrichen ist. Dadurch modelliert ein dynamischer Fluss, wie sich die Flusseinheiten durch das Netzwerk und durch die Zeit bewegen. In der mathematischen Literatur zu Evakuierungen nehmen sogenannte Earliest Arrival Flows (EAF) einen prominenten Platz ein, siehe z.B. Hoppe oder Hamacher. Ein EAF ist ein dynamischer Fluss, der zugleich für alle Zeitpunkte die Anzahl der Flusseinheiten maximiert, die bis dahin bereits eine Senke erreicht haben. Dadurch repräsentieren sie die bestmögliche Lösung für eine Evakuierung. Wir konzentrieren uns darauf, einen praxistauglichen Algorithmus zur Berechnung eines EAF zu entwickeln. Dieser Algorithmus basiert auf dem Successive-Shortest-Path-Algorithmus, den wir auf die sich wiederholende Struktur des zeitexpandierten Netzwerks und auf typische Instanzen spezialisieren. Eine zentrale Idee ist, während der Suche des kürzesten Wegs Kopien desselben Knotens über mehrere Zeitschichten hinweg zu berücksichtigen. Ebenfalls kommen viele Heuristiken zum Einsatz. Auf den größten Instanzen mit echten Anwendungsdaten erreichen wir insgesamt die Geschwindigkeit der besten konkurrierenden Ansätze. Auf jenen Instanzen, die große Gebäude modellieren, ist unser Algorithmus signifikant schneller als alle andere. Danach betrachten wir Flüsse mit aggregierten Kantenkapazitäten. Dies sind dynamische Flüsse, in denen die Kapazitäten den Fluss in die Kanten innerhalb eines sich verschiebenden Zeitfensters beschränken. Dieses Modell wurde vor kurzem von Melkonian eingeführt. Wir verallgemeinern es, indem wir die Länge der Fenster von den Durchgangszeiten unabhängig machen. Wir diskutieren die Auswirkungen der Flusserhaltung in unserem verallgemeinerten Modell, sowie die Komplexität des zugehörigen Transportproblems unter verschiedenen Bedingungen. Als nächstes entwickeln wir dafür ein voll polynomielles Approximationsschema (FPTAS), welches Lösungen berechnet, die die Kapazitäten und den Zeithorizont um den Approximationsfaktor überschreiten. Die Kantenkosten und die Länge der Zeitfenster werden aber exakt berücksichtigt. Der Korrektheitsbeweis erweitert eine Technik von Fleischer und Skutella. Schließlich untersuchen wir noch das Maximum Confluent Flow Problem (MCFP). Ein Confluent Flow ist ein statischer Fluss, welcher an jedem Knoten nur eine ausgehende Kante verwendet. Kürzlich erschienene Resultate von Chen et al. behandeln die Minimierung der überlastung in einem Confluent Flow, allerdings ohne unterschiedliche Kantenkapazitäten zu berücksichtigen. Bei unseren Betrachtungen hingegen sind beliebige Kantenkapazitäten erlaubt. Wir entwickeln einen polynomiellen Algorithmus zur Berechnung des MCFP auf außenplanaren Graphen mit einer Senke. Dieses dynamische Programm enthält pseudopolynomiell viele Einträge, die wir mittels einer effizienten Darstellung polynomiell verwalten. Basierend auf unserer Komplexitätsanalyse argumentieren wir, dass außenplanare Graphen einen wichtigen nicht-trivialen polynomiellen Fall darstellen. Wir untersuchen auch ein FPTAS für das MCFP mit beliebigen Quellen und Senken auf Graphen mit beschränkter Baumweite.
We study how network flow theory can aid in evacuation planning. We assume we are given a network of the area to be evacuated, with sources describing the locations of evacuees, and sinks describing safe areas. Each arc in the network has a capacity that limits the flow rate into this arc and a transit time describing its length. In a flow over time, the flow units entering an arc reach the other end after the transit time has passed. Thus, a flow over time can model how flow units move through the network and through time. In the mathematical literature on evacuations, Earliest Arrival Flows (EAF) have a prominent place, see Hoppe or Hamacher, for example. They are flows over time that simultaneously maximize the amount of flow units that have already reached the sink at every time step. Thus, they represent the best imaginable solution for an evacuation. We focus on the development of a practical algorithm to compute an EAF. This algorithm is based on the Successive Shortest Path algorithm, specialized to the repeating nature of the time-expanded network and typical instances. One central idea is to consider copies of the same vertex across multiple time layers at once when determining a shortest path. But many heuristic improvements also help. Overall, we match the performance of the best competitors on the largest real-world instances, and significantly outperform them on the subset of instances modeling large buildings. We then consider Flows with Aggregate Arc Capacities, which are flows over time where capacities bound the flow into each arc within a sliding time window. This model was recently introduced by Melkonian. We generalize it by uncoupling the lengths of the sliding windows from the transit times. We discuss the effects of flow conservation for our generalized model, as well as the complexity of the associated transshipment problem under various settings. We then develop a fully polynomial-time approximation scheme (FPTAS), which computes solutions that require a violation of the capacities and the time horizon by the approximation factor. The arc costs and the lengths of the sliding windows are considered exactly, though. The correctness proof extends a technique by Fleischer and Skutella. Finally, we consider the Maximum Confluent Flow problem. Confluent flows are static flows that allow only one outgoing arc to carry flow at each vertex. Recent works by Chen et al. explore minimizing the congestion of a confluent flow, but they admit uniform arc capacities only. In contrast, we allow arbitrary arc capacities. We develop a polynomial algorithm for computing the maximum confluent flow value on outerplanar graphs with a single sink. While presented as a dynamic program, the tables require pseudo-polynomially many entries, for which we find an efficient encoding. Based on the complexity analysis, we argue that outerplanar graphs are an important non-trivial polynomial case. We also detail an FPTAS for maximum confluent flows with arbitrary terminals on graphs with bounded treewidth.
URI: urn:nbn:de:kobv:83-opus-36833
http://depositonce.tu-berlin.de/handle/11303/3624
http://dx.doi.org/10.14279/depositonce-3327
Exam Date: 7-Aug-2012
Issue Date: 24-Sep-2012
Date Available: 24-Sep-2012
DDC Class: 510 Mathematik
Subject(s): Dynamischer Netzwerkfluss
Effizienter Algorithmus
Graph
Optimierung
Dynamic network flow
Efficient algorithm
Graph
Optimization
Creative Commons License: https://creativecommons.org/licenses/by-nc-sa/2.0/
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_50.pdf8,96 MBAdobe PDFThumbnail
View/Open


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