Robust flows over time: models and complexity results

• 成果类型: Article
• 署名作者: Gottschalk, Corinna; Koster, Arie M. C. A.; Liers, Frauke; Peis, Britta; Schmand, Daniel; Wierz, Andreas
• 署名单位: RWTH Aachen University; RWTH Aachen University; University of Erlangen Nuremberg
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1170-3
• 发表日期: 2018
• 页码: 55-85
• 关键词: network flows; residual flow; optimization; destruction

摘要

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 edge. 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 (that is, 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 the optimality gap is at most O(eta k log T) , where eta and k are newly introduced instance characteristics and provide a matching lower bound instance with optimality gap Omega (log T) and eta = k = 1. The results obtained in this paper yield a first step towards understanding robust dynamic flow problems with uncertain travel times.