ISBN 9783843912419

978-3-8439-1241-9, Reihe Mathematik

Kathrin Leiner
Earliest Departure and Cluster Flows: Enhancements of the Dynamic Network Flow Model

193 Seiten, Dissertation Technische Universität Kaiserslautern (2013), Softcover, A5

Zusammenfassung / Abstract

Network flow problems are classical problems in combinatorial optimization. The dynamic network flow model augments conventional network flows by a time aspect. These flows are frequently used in evacuation planning as a macroscopic model of pedestrian movement. The main advantage of using dynamic network flows in this context is that they are capable of providing system optimal evacuation routes. These yield lower bounds on the minimal evacuation time necessary to evacuate a specified number of people. However, some aspects of individual behavior observable in reality were not regarded in the dynamic network flow model so far, which often causes the lower bounds to be rather loose. This thesis is concerned with augmenting the dynamic network flow model with more detail in order to capture reality more closely while retaining the beneficial properties of this model. To this end, two major innovative extensions of the dynamic network flow model are introduced and studied. In the earliest departure flow model, flow units already start to move, whenever this takes them closer to their destination. This might cause congested paths, which is modeled by holdover of flow units at intermediate nodes. This characteristic is uncommon for dynamic network flows, in which holdover is usually not desired. The dynamic cluster flow model incorporates group affiliations among evacuees into the network flow model by considering unsplittable flow units of different sizes. Problems of this kind have never been examined in dynamic network flow literature before. The quickest cluster flow problem yields improved lower bounds on evacuation times. Several approximation algorithms as well as an asymptotic polynomial time approximation scheme are proposed.