Uncertain Dynamic Network Flow Problems
Tóm tắt
In this paper, uncertain dynamic network flow problems (UDNFPs) are formulated, and an algorithm is proposed to solve them by noting that arc capacities are uncertain (may vary with time or not), and flow varies over time in each arc. Here, uncertainty refers to nondeterministic states, in which some factors are uncertain and cannot be determined by the probability theory. Since the uncertainty theory seems to be well applicable in these cases, thus, it is applied for the UDNFPs in this paper. Although some papers have studied uncertain network flow problems in the static case, but in the best of our knowledge, this paper is the first one about the UDNFPs.
Tài liệu tham khảo
Ahuja, RK, Magnanti, TL, Orlin, JB: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood (1993).
Bertsimas, D, et al.: Theory and applications of robust optimization. SIAM Rev. 53(3), 464–501 (2011).
Chanas, S, Kołodziejczyk, W: Maximum flow in a network with fuzzy arc capacities. Fuzzy Sets Syst. 8(2), 165–173 (1982).
Chanas, S, Kołodziejczyk, W: Integer flows in network with fuzzy capacity constraints. Networks. 16, 17–31 (1996).
Chen, X, Liu, B: Existence and uniqueness theorem for uncertain differential equations. Fuzzy Optim. Decis. Making. 9(1), 69–81 (2010).
Chen, XW, Ralescu, DA: B-spline method of uncertain statistics with applications to estimate travel distance. J. Uncertain Syst. 6(4), 256–262 (2012).
Chen, X, Kar, S, Ralescu, DA: Cross-entropy measure of uncertain variables. Inform. Sci. 201, 53–80 (2012).
Dantzig, GB: Linear programming under uncertainty. Mgmt. Sci. 1(3–4), 197–206 (1955).
Ding, S: Uncertain minimum cost multicommodity flow problem. Soft Comput. 21(1), 223–231 (2017).
Ding, S: The α-maximum flow model with uncertain capacities. Appl. Math. Modelling. 39(7), 2056–2063 (2015).
Fishman, GS: The distribution of maximum flow with applications to multistate reliability systems. Oper. Res. 35(4), 607–618 (1987).
Fleischer, L, Skutella, M: Quickest flows over time. SIAM J. Comput. 36(6), 1600–1630 (2007).
Fleischer, L, Tardos, E: Efficient continuous-time dynamic network flow algorithms. Oper. Res. Lett. 23, 71–80 (1998).
Ford, LR, Fulkerson, DR: Flows in networks. Princeton University Press, Princeton (1962).
Gao, Y: Shortest path problem with uncertain arc lengths. Comput. Math. Appl. 62(6), 2591–2600 (2011).
Gao, Y: Uncertain models for single facility location problems on networks. Appl. Math. Model. 36(6), 2592–2599 (2012).
Goldberg, AV, Tarjan, RE: A new approach to the maximum flow problem. J. Assoc. Comput. Mach. 35(4), 921–940 (1988).
Han, S, et al.: The maximum flow problem of uncertain network. Inform. Sci. 265, 167–175 (2014).
James, JB, Leonard, JJ: Fuzzy max-flow problem. Stud. Fuzz. Soft Comput. 222, 195–198 (2008).
Ji, X, Yang, L, Shao, Z: Chance constrained maximum flow problem with fuzzy arc capacities. Lect. Notes Artif. Intell. 4114, 11–19 (2006).
Kolmogorov, A: Grundbegriffe der Wahrscheinlichkeitsrechnung (in German). Julius Springer, Berlin (1933).
Liu, B: Fuzzy process, hybrid process and uncertain process. J. Uncertain Syst. 2(1), 3–16 (2008).
Liu, B: Some research problems in uncertainty theory. J. Uncertain Syst. 3(1), 3–10 (2009).
Liu, B: Theory and practice of uncertain programming. second ed. Springer-Verlag, Berlin (2009).
Liu, B: Uncertainty theory, 2nd edn. Springer-Verlag, Berlin (2007).
Liu, B: Uncertainty theory, 5th ed. Springer-Verlag, Berlin (2015).
Liu, B: Uncertainty theory: a branch of mathematics for modeling human uncertainty. Springer-Verlag, Berlin (2010).
Liu, B: Uncertain risk analysis and uncertain reliability analysis. J. Uncertain Syst. 4(3), 163–170 (2010).
Liu, B: Uncertain logic for modeling human language. J. Uncertain Syst. 5(1), 3–20 (2011).
Liu, Y: Uncertain random variables: a mixture of uncertainty and randomness. Soft Comput. 17(4), 625–634 (2013).
Minoux, M: On robust maximum flow with polyhedral uncertainty sets. Optimization Lett. 3(3), 367–376 (2009).
Minoux, M: Robust network optimization under polyhedral demand uncertainty is NP-hard. Discrete Appl. Math. 158(5), 597–603 (2010).
Nasrabadi, E: Dynamic flows in time-varying networks, Ph.D. dissertation, Berlin (2009).
Nawathe, SP, Rao, BV: Maximum flow in probabilistic communication networks. Int. J. Circ. Theory Appl. 8, 167–177 (1980).
Ordonez, F, Zhao, J: Robust capacity expansion of network flows. Networks. 50(2), 136–145 (2007).
Peng, J, et al.: Towards uncertain network optimization. J. Uncertainty Anal. Appl. 3(4), 3–16 (2015).
Skutella, M: An introduction to network flows over time. In: Cook, W, Lovász, L, Vygen, J (eds.)Research Trends in Combinatorial Optimization, pp. 451–482. Springer, Heidelberg (2009).
Tang, Z, Tang, B: The maximum flow problem with fuzzy constraints. Fuzzy Syst. Math. 15(4), 77–80 (2001).
Wang, XS, Gao, ZC, Guo, HY: Uncertain hypothesis testing for two experts’ empirical data. Math. Comput. Model. 55(3–4), 1478–1482 (2012).
Yao, K: No-Arbitrage determinant theorems on mean-reverting stock model in uncertain market. Knowl.-Based Syst. 35, 259–263 (2012).
Yao, K, Li, X: Uncertain alternating renewal process and its application. IEEE Trans. Fuzzy Syst. 20(6), 1154–1160 (2012).
Yao, K, Gao, J, Gao, Y: Some stability theorems of uncertain differential equation. Fuzzy Optim. Decis. Making. 12(1), 3–13 (2013).
Zadeh, LA: Fuzzy sets. Inform. Control. 8, 338–353 (1965).
Zhou, J, Yang, F, Wang, K: An inverse shortest path problem on an uncertain graph. J. Netw. 9(9), 23–53 (2014).