@article{GottschalkKosterLiersetal.2017, author = {Gottschalk, Corinna and Koster, Arie M.C.A. and Liers, Frauke and Peis, Britta and Schmand, Daniel and Wierz, Andreas}, title = {Robust Flows over Time: Models and Complexity Results}, doi = {10.1007/s10107-017-1170-3}, year = {2017}, abstract = {We study dynamic network flows with uncertain input data under a robust optimization perspective. In the dynamic maximum flow problem, the goal is to maximize the flow reaching the sink within a given time horizon T, while flow requires a certain travel time to traverse an arc. In our setting, we account for uncertain travel times of flow. We investigate maximum flows over time under the assumption that at most Γ travel times may be prolonged simultaneously due to delay. We develop and study a mathematical model for this problem. As the dynamic robust flow problem generalizes the static version, it is NP-hard to compute an optimal flow. However, our dynamic version is considerably more complex than the static version. We show that it is NP-hard to verify feasibility of a given candidate solution. Furthermore, we investigate temporally repeated flows and show that in contrast to the non-robust case (i.e., without uncertainties) they no longer provide optimal solutions for the robust problem, but rather yield a worst case optimality gap of at least T. We finally show that for infinite delays, the optimality gap is at most O(k log T), where k is a newly introduced instance characteristic. The results obtained in this paper yield a first step towards understanding robust dynamic flow problems with uncertain travel times.}, language = {en} }