ISBN 9783843928861

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

Bob Grün
Network Aggregation and Flows with Applications to Evacuation Planning

237 Seiten, Dissertation Technische Universität Kaiserslautern (2016), Softcover, A5

Zusammenfassung / Abstract

For the safety of cities and events, the construction of evacuation plans is very important. These mathematical constructed plans often base on graphs. For cities, the available graphs are often too large to be used by known algorithms such that network aggregation methods must be applied.

In the first part of this thesis, we consider two methods to reduce the graph size. The idea of both approaches is to reduce crossovers and roundabouts to a single node. Thus, in the first approach, we contract "small" edges such that the two connected nodes of an edge are merged. In the second approach, "small" edges are removed if there is a reasonable detour of this edge. It is clear that the contraction as well as the removal of an edge can cause an error. In order to get information on the impact of the total error, we measure the quality of the graph aggregation through the average shortest path length change. From the theoretical point of view, we consider worst case graphs and thus show error bounds on the average error. Even if both aggregation methods have worse theoretical error bounds, we have shown that for real world graphs, both methods have good results. Since the motivation of the aggregation rise from street networks, we consider the average aggregation error for 280 real world cities with different graph sizes.

Since the use of shortest paths is not sufficient for evacuation planning, we consider in the second part different known algorithms to construct evacuation plans. After the review of the approaches and their complexity, we consider the quickest transshipment problem in more detail. We compare integer program formulations with a binary search and some heuristics linear program formulations through computation time and by their applicability to real world graphs. For this, we have built 269 real world evacuation scenarios for different cities. On the streets, we used realistic capacities derived from the literature on road construction.

If a large number of people are evacuated, it is natural to assume that the people starting from the same point also behave in the same way (in the optimal case). Therefore, we consider in particular the repetitive use of paths and we were able to show that the minimum cost maximum flow over time problem with cost equal to time has a time range where paths are used repeatedly.