• search hit 9 of 24
Back to Result List

Robust Flows over Time: Models and Complexity Results

  • 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.
Metadaten
Author:Corinna Gottschalk, Arie M.C.A. Koster, Frauke Liers, Britta Peis, Daniel Schmand, Andreas Wierz
DOI:https://doi.org/10.1007/s10107-017-1170-3
Document Type:Article
Language:English
Date of Publication (online):2017/06/20
Date of first Publication:2017/06/20
Release Date:2016/09/20
Tag:Dynamic Network Flows; Dynamic Robust Flow; Uncertain Travel Times
Institutes:Friedrich-Alexander-Universität Erlangen-Nürnberg
RWTH Aachen University
Subprojects:B06