Generalizations of Flows over Time with Applications in Evacuation Optimization

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.

Studium der Informatik und Mathematik, Promotion an der Technischen Universität Berlin in der Gruppe Kombinatorische Optimierung und Graphenalgorithmen. Hauptsächlich interessiert an der Entwicklung und anschließenden Implementierung effizienter Algorithmen.