ISBN 9783843907231

978-3-8439-0723-1, Reihe Mathematik

Markus Thiemann
Cross-linking of Robustness, Parameter Computation, and Optimization in Evacuation Modeling

171 Seiten, Dissertation Technische Universität Kaiserslautern (2012), Softcover, A5

Zusammenfassung / Abstract

This thesis is concerned with evacuation modeling by dynamic network flow optimization. New concepts as well as crucial extensions for dynamic network flows are developed to include real-world requirements in these evacuation models.

The first part of this thesis focuses on advanced concepts for quickest path problems. Min-max and min-max regret versions of these problems are introduced and, depending on the complexity status of these robust dynamic network flow problems, exact solution algorithms or fully polynomial-time approximation schemes are proposed.

Reliable and restricted quickest path problems seek for quickest paths with a desired minimum reliability and costs not exceeding a given budget, respectively. As the problems are shown to be NP-hard, the derived pseudo-polynomial solution algorithms and fully polynomial-time approximation schemes are the best achievable, unless P=NP. The k-min capacity quickest path problem is presented as a generalization of the quickest path problem. Furthermore, a sensitivity analysis is performed for the quickest path problem.

In the second part of this thesis, new theoretical concepts in multiple objective optimization and robust optimization are established. Multiple objective combinatorial optimization problems with some bottleneck or k-max objectives are shown to be not much harder to approximate than the multiple objective subproblem without bottleneck or k-max objectives, respectively.

A new concept for robust optimization - set-based robustness - is proposed with application in emergency planning. The basic idea is to provide a robust set of solutions instead of a single robust solution. It is shown that set-based robustness generalizes existing concepts for robust optimization.

The third part of this thesis is concerned with pedestrian evacuation modeling by dynamic network flow optimization. An extension for dynamic network flows which incorporates interdependencies of travel times and capacities is proposed. Dynamic network flows with interdependent parameters are capable of reproducing important features in context of pedestrian dynamics such as velocity-density relations.

Furthermore, dynamic network flow optimization models are coupled with microscopic cellular automaton models for evacuation planning. Output of each model is fed into the other one, thus establishing a control cycle.