Generalizations of flows over time with applications in evacuation optimization
| dc.contributor.advisor | Skutella, Martin | en |
| dc.contributor.author | Kappmeier, Jan-Philipp | en |
| dc.contributor.grantor | Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften | en |
| dc.contributor.referee | Skutella, Martin | en |
| dc.contributor.referee | Köhler, Ekkehard | en |
| dc.contributor.submitter | Kappmeier, Jan-Philipp | en |
| dc.date.accepted | 2014-12-19 | |
| dc.date.accessioned | 2015-11-21T00:17:14Z | |
| dc.date.available | 2015-03-27T12:00:00Z | |
| dc.date.issued | 2015-03-27 | |
| dc.date.submitted | 2015-02-18 | |
| dc.description.abstract | Eines der wichtigsten Konzepte in der kombinatorischen Optimierung sind dynamische Netzwerke, die zusätzlich zu der Graphstruktur Informationen über Fahrzeiten auf den Kanten enthalten. Dynamische Netzwerke können genutzt werden um zahlreiche Transportprobleme zu modellieren. Neben typischen Anwendungen in der Informationsverarbeitung und der Logistik sind Evakuierungen eines der wichtigsten Anwendungsfälle. Beim Lösen dynamischer Probleme spielt die Zeit eine wichtige Rolle. Für ein Evakuierungsszenario wird nicht nur eine Lösung gesucht, die insgesamt möglichst gut (das heißt, die zu Evakuierenden werden schnell an sichere Ziele geleitet) ist, sondern auch zu jedem Zeitpunkt sollen möglichst viele Menschen bereits sicher sein. Solche Lösungen werden als Earliest-Arrival-Flüsse bezeichnet. In der Praxis ist dieses Konzept bisher noch nicht umgesetzt worden; verfügbare Software zur Evakuierungssimulation verwendet hauptsächlich Simulationsmodelle wie zelluläre Automaten. In dieser Arbeit untersuchen wir, ob das Problem in der Praxis zur Optimierung von Evakuierungen eingesetzt werden kann. Weiterhin analysieren wir Szenarien, in denen optimale Lösungen nicht existieren. Neben den unmittelbaren praktischen Anwendungsfällen betrachtet die aktuelle Forschung in der kombinatorischen Optimierung dynamische Varianten von weiteren Problemen. In dieser Arbeit werden mit dynamischen Matchings und dynamischen abstrakten Flüssen zwei klassische statische Probleme in ein dynamisches Szenario übertragen. Im praktischen Teil untersuchen wir, wie mit einer Ausgangsverteilung die Evakuierungszeit optimiert werden kann. Dazu definieren wir mehrere auf (dynamischen) Netzwerkflüssen basierende Verfahren und verglichen ihre Auswirkungen anhand von schwierigen Testfällen. Um die praktische Nutzbarkeit von Earliest-Arrival-Flüssen zu zeigen, entwickeln wir ein Verfahren, das es ermöglicht zelluläre Autmaten automatisch in dynamische Netzwerke umzuwandeln. Um die Anwendbarkeit des Modells zu belegen, vergleichen wir Simulationsergebnisse und Earliest-Arrival-Flüsse mit einer beobachteten Testevakuierung. In Fällen mit Sicherheitsbereichen von beschränkter Kapazität, zum Beispiel in Rettungsbooten, ist es nicht möglich, Earliest-Arrival-Flüsse zu bestimmen. Für diesen Anwendungsfall entwickeln wir Approximationsalgorithmen zur Bestimmung von Lösungen, die garantiert einen Bruchteil der maximal möglichen Anzahl an Personen evakuieren. Die entwickelten Algorithmen arbeiten auf Netzwerken mit mehreren Gütern. Wir komplementieren die Ergebnisse mit einem Algorithmus, der bestmögliche Approximationen für eine Instanz bestimmt. Die Analyse von dynamischen Matchings führt zu einer Erweiterung dynamischer Netzwerkprobleme, die negative Reisezeiten auf Kanten zulässt. Wir zeigen, dass unter dieser Erweiterung bereits das relativ einfache Problem, einen maximalen dynamischen Fluss zu bestimmen, NP-schwer wird. Wir charakterisieren einfache Instanzen und beschreiben einen Approximationsalgorithmus, der die verfügbare Zeit nicht um mehr als einen Faktor von (2 + ε) überschreitet. Abstrakte Flüsse sind eine Erweiterung des klassischen Flussproblems, die mit möglichst wenigen Voraussetzungen das Verhalten von Netzwerkflüssen haben. Wir zeigen, dass abstrakte Earliest-Arrival-Flüsse existieren und durch einen lexikographischen maximalen abstrakten Fluss im zeitexpandierten Netzwerk bestimmt werden können. Außerdem zeigen wir, dass diese Flüsse ebenfalls wie klassische Earliest-Arrival-Flüsse mit einem konstanten Faktor Wert-Approximiert werden können. | de |
| dc.description.abstract | Dynamic networks are one of the most important concepts in the field of combinatorial optimization. Additionally to the graph structure they contain information about travel times of arcs. Such networks can be used to model may transportation problems. Besides typical applications in information science and logistics, evacuations are one of the most important use cases of dynamic networks. In solutions of dynamic problems time plays a crucial role. For evacuation scenarios we are foremost looking for a solution that sends evacuees to safe areas as fast as possible. However, it is also important that at every point in time as much evacuees as possible are safe. Such solutions are referred to as earliest arrival flows. The concept has never been applied in practice; available software tools for evacuation simulation use models such as cellular automata. In this thesis we study how earliest arrival flows can be applied in practice. Furthermore, we analyse scenarios that do not allow for an optimal solution. Besides immediate applications currently, research in combinatorial optimization considers dynamic variants of other classical problems. The thesis covers two extensions of those classical problems, matchings over time and abstract flows over time. In the practice part we study, how we can optimize the egress time in an evacuation by using an exit assignment of the evacuees. Therefore, we propose several types of exit assignments based on network flows (over time). We analyse the approaches and compare their effectiveness by means of test cases that are problematic. To show practical relevance of earliest arrival flows we derive a method to automatically generate dynamic networks for any evacuation scenario based on cellular automata. We prove validity by comparison of measured data from a test evacuation with simulation results and earliest arrival flows in the generated instances. In cases of safe areas with limited capacity, such as life boats, it is not necessarily to compute earliest arrival flows. For this scenario we derive approximation algorithms computing solutions that guarantee to send a fraction of the maximal possible amount of flow in each point in time. The algorithms also work for networks with multiple commodities. We complement the results with an algorithm that computes the best possible approximation factor for each instance. The matching over time problem can be reduced to a flow over time problem if negative travel times on arcs are allowed. We show that even the relatively easy maximum flow over time problem becomes NP-hard in the presence of negative travel times. We characterize easy instances and describe an approximation algorithm that computes a dynamic transshipment and violates the optimal time horizon by at most a factor of (2 + ε). Abstract flows are a generalization of classical flows that model the behaviour of network flows with few assumptions on the structure. We show that, in the dynamic setting, abstract earliest arrival flows can be determined by an lexicographically maximum abstract flow in an abstract time expanded network. Furthermore, we show that abstract earliest arrival flows can be approximated similarly to classical earliest arrival flows. The algorithm computes abstract flows sending a constant factor of the maximum possible flow value at every point in time. | en |
| dc.identifier.isbn | 978-3-7375-3238-9 | |
| dc.identifier.uri | urn:nbn:de:kobv:83-opus4-63232 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/4655 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-4358 | |
| dc.language | English | en |
| dc.language.iso | en | en |
| dc.publisher.name | epubli GmbH | en |
| dc.publisher.place | Berlin | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | Dynamische Flüsse | de |
| dc.subject.other | Dynamische Matchings | de |
| dc.subject.other | Earliest-Arrival-Flüsse | de |
| dc.subject.other | Evakuierung | de |
| dc.subject.other | Netzwerke | de |
| dc.subject.other | Earliest arrival flow | en |
| dc.subject.other | Evacuation | en |
| dc.subject.other | Flow over time | en |
| dc.subject.other | Matching over time | en |
| dc.subject.other | Networks | en |
| dc.title | Generalizations of flows over time with applications in evacuation optimization | en |
| dc.title.translated | Verallgemeinerungen von dynamischen Netzwerkflüssen mit Anwendungen in der Evakuierungsoptimierung | de |
| dc.type | Doctoral Thesis | en |
| dc.type.version | publishedVersion | en |
| tub.accessrights.dnb | free | * |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.identifier.opus4 | 6323 | |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1