Robust Optimization and Evacuation Planning with Bridges

Evacuation planning is of major importance and helps saving lives when hurricanes, earthquakes, flooding or other hazards affect inhabited areas. Therefore, mathematical models have proved to be helpful for calculating evacuation routes. Depending on the considered model, there exist algorithms which compute solutions identifying evacuation routes, which should be used in an evacuation scenario. In this thesis, we consider some of those mathematical models. In particular, we focus on network flows and the shortest paths to model evacuation routes. However, we do not only consider evacuation problems, but we assume that those problems are affected by uncertainty. In reality, it is most unlikely that all data is known exactly. Therefore, we model evacuation problems with the help of robust optimization and incorporate uncertainty into our models. To this end, we develop a new robust concept based on ranking procedures and which computes a solution which performs well with respect to its ranking in all considered scenarios. This new concept we call ranking robustness. Furthermore, we present a detailed overview on the complexity results of the strict robust integer minimum cost flow problem and show for some special case that this problem can be transformed to a strict robust shortest path problem and vice versa. We use the integer minimum cost flow problem to apply ranking robustness on temporally repeated flows and give an alternative to deal with uncertain evacuation problems. Besides uncertainty, we focus on another aspect which often has been omitted when it comes to evacuation planning. In general, mathematical models do not distinguish between street segments and bridges, and both are modeled by the same type of arc. However, for bridges the load capacity limits the number of vehicles that can be on a bridge at the same time, whereas for street segments usually the type of capacity known from general dynamic network flows is used, i. e., it limits the number of vehicles that can enter the given street segment per time step. Thus, the interpretation of those capacities is different. Since for evacuation planning the maximal load a bridge can carry might be affected, we also focus on this special structure. In particular, we model bridge arcs differently and consider networks where an arc either represents a bridge or a street segment.