[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Robust flows over time: models and complexity results

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

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 edge. In our setting, we account for uncertain travel times of flow. We investigate maximum flows over time under the assumption that at most \(\varGamma \) 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 \(\varOmega (\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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Aneja, Y.P., Chandrasekaran, R., Nair, K.: Maximizing residual flow under an arc destruction. Networks 38(4), 194–198 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  2. Aronson, J.E.: A survey of dynamic network flows. Ann. Oper. Res. 20(1), 1–66 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  3. Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)

    Book  MATH  Google Scholar 

  4. Bertsimas, D., Nasrabadi, E., Stiller, S.: Robust and adaptive network flows. Oper. Res. 61(5), 1218–1242 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  5. Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program. Ser. B 98, 49–71 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  6. Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math. 51, 161–166 (1950)

    Article  MathSciNet  MATH  Google Scholar 

  7. Disser, Y., Matuschke, J.: The complexity of computing a robust flow (2017). arXiv:1704.08241

  8. Du, D., Chandrasekaran, R.: The maximum residual flow problem: NP-hardness with two-arc destruction. Networks 50(3), 181–182 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  9. Ford Jr., L.R., Fulkerson, D.R.: Constructing maximal dynamic flows from static flows. Oper. Res. 6(3), 419–433 (1958)

    Article  MathSciNet  Google Scholar 

  10. Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theoret. Comput. Sci. 10(2), 111–121 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  11. Grötschel, M., Lovász, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169–197 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gupta, U.I., Lee, D.T., Leung, J.T.: Efficient algorithms for interval graphs and circular-arc graphs. Networks 12(4), 459–467 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  13. Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Springer, Berlin (1972)

  14. Koch, R., Nasrabadi, E., Skutella, M.: Continuous and discrete flows over time. A general model based on measure theory. Math. Methods Oper. Res. 73(3), 301–337 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  15. Koch, T., Hiller, B., Pfetsch, M.E., Schewe, L.: Evaluating Gas Network Capacities. SIAM, Philadelphia (2015)

    Book  MATH  Google Scholar 

  16. Köhler, E., Skutella, M.: Flows over time with load-dependent transit times. SIAM J. Optim. 15(4), 1185–1202 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  17. Matuschke, J., McCormick, T.S., Oriolo, G., Peis, B., Skutella, M.: http://materials.dagstuhl.de/files/15/15412/15412.JannikMatuschke.ExtendedAbstract.pdf (2015)

  18. Skutella, M.: An introduction to network flows over time. In: Cook, W.J., Lovász, L., Vygen, J. (eds.) Research Trends in Combinatorial Optimization, pp. 451–482. Springer, Berlin (2009)

    Chapter  Google Scholar 

  19. Wood, R.K.: Deterministic network interdiction. Math. Comput. Model. 17(2), 1–18 (1993)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We thank the reviewers for their very careful reading of the manuscript and their valuable comments. We thank the DFG for their support within Project B06 in CRC TRR 154.

Author information

Authors and Affiliations

  1. School of Business and Economics, RWTH Aachen University, Aachen, Germany

    Corinna Gottschalk, Britta Peis, Daniel Schmand & Andreas Wierz

  2. Lehrstuhl II für Mathematik, RWTH Aachen University, Aachen, Germany

    Arie M. C. A. Koster

  3. Lehrstuhl Wirtschaftsmathematik, FAU Erlangen-Nürnberg, Erlangen, Germany

    Frauke Liers

Authors
  1. Corinna Gottschalk
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Arie M. C. A. Koster
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Frauke Liers
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Britta Peis
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Daniel Schmand
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Andreas Wierz
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andreas Wierz.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gottschalk, C., Koster, A.M.C.A., Liers, F. et al. Robust flows over time: models and complexity results. Math. Program. 171, 55–85 (2018). https://doi.org/10.1007/s10107-017-1170-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-017-1170-3

Mathematics Subject Classification