Algorithms for the quickest time distribution of dynamic stochastic-flow networks

Jane, Chin-Chia; Laih, Yih-Wenn

RAIRO - Operations Research - Recherche Opérationnelle, Tome 51 (2017) no. 4, pp. 1317-1330.

Quickest time, which is the least possible time necessary to transmit a fixed amount of data from a source node to a destination node, has been widely explored in the past few years. A quickest path transmits data via a single path, whereas a quickest flow transmits data via all possible paths. In a dynamic stochastic-flow network in which each arc capacity is a discrete random variable having several possible integer values, the quickest time is not a fixed value. Existing literature computes the reliability that the specified amount of flow can be sent simultaneously from the source to the destination through multiple $k$ disjoint minimal paths within a given time horizon. This article presents a decomposition algorithm to compute the probability distribution of the quickest time of a dynamic stochastic-flow network from the viewpoint of flow (all disjoint and non-disjoint minimal paths simultaneously) rather than of $k$ disjoint minimal paths only. The distribution of quickest time is important for the design and analysis of evacuation systems, as they are generally analyzed and optimized via the quickest flow models. As a result, the expected quickest time and the probability that the quickest time is no larger than a specified time threshold can be determined directly. The proposed algorithm can be easily modified to approximate the probability distribution by trading off accuracy for execution time when the network system is large. Computational experiments are conducted to illustrate the proposed algorithms.

Classification : 05C21, 90B15, 90B25
Mots clés : Dynamic stochastic-flow network, quickest time distribution, decomposition algorithm, reliability

K.K. Aggarwal, A fast algorithm for the performance index of a telecommunication network. IEEE Trans. Reliab. 37 (1988) 65–69. | DOI | Zbl

R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows. Prentice Hall, New Jersey (1988). | MR

J.E. Aronson, A survey of dynamic network flows. Ann. Oper. Res. 20 (1989) 1–66. | DOI | MR | Zbl

Y.-C. Bang, H. Choo and Y. Mun, Reliability problem on all pairs quickest paths. In ICCS 2003 – Computational Science. Springer Berlin Heidelberg (2003) 518–523. | MR

R.E. Burkard, K. Dlaska and B. Klinz, The quickest flow problem. Z. Oper. Res. 37 (1993) 31–58. | MR | Zbl

C. Gen-Huey and H. Yung-Chen, Algorithms for the constrained quickest path problem and the enumeration of quickest paths. Comput. Oper. Res. 21 (1994) 113–118. | DOI | Zbl

Y.L. Chen and Y.H. Chin, The quickest path problem. Comput. Oper. Res. 17 (1990) 153–161. | DOI | MR | Zbl

Y.L. Chen, Finding the k quickest simple paths in a network. Inf. Proc. Lett. 50 (1994) 89–92. | DOI | MR | Zbl

L. Fleischer and M. Skutella, The quickest multicommodity flow problem. In Integer Programming and Combinatorial Optimization. Springer, Berlin, Heidelberg (2002) 36–53. | MR | Zbl

L.R. Ford and D.R. Fulkerson, Flows in networks. Princeton University Press: Princeton (1962). | MR | Zbl

B. Hoppe and É. Tardos, The quickest transshipment problem. Math. Oper. Res. 25 (2000) 36–62. | DOI | MR | Zbl

C.C. Jane and Y.-W. Laih, Algorithms to determine the threshold reliability of flow networks. IIE Trans. 36 (2004) 469–479. | DOI

C.C. Jane and Y.-W. Laih, A practical algorithm for computing multi-state two-terminal reliability. IEEE Trans. Reliab. 57 (2008) 295–302. | DOI

C.C. Jane and Y.-W. Laih, A dynamic bounding algorithm for approximating multi-state two-terminal reliability. Eur. J. Oper. Res. 205 (2010) 625–637. | DOI | MR | Zbl

C.C. Jane and J. Yuan, A sum of disjoint products algorithm for reliability evaluation of flow networks. Eur. J. Oper. Res. 131 (2001) 664–675. | DOI | MR | Zbl

D.T. Lee and E. Papadopoulou, The all-pairs quickest path problem. Inf. Process. Lett. 45 (1993) 261–267. | DOI | MR | Zbl

S.H. Lee, Reliability evaluation of a flow network. IEEE Trans. Reliab. 29 (1980) 24–26. | DOI | Zbl

M. Lin and P. Jaillet, On the quickest flow problem in dynamic networks: a parametric min-cost flow approach. In Proc. of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM (2015) 1343–1356. | MR

Y.K. Lin, Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network. Comput. Oper. Res. 30 (2003) 567–575. | DOI | Zbl

Y.K. Lin, Transmission reliability of k minimal paths within time threshold. Comput. Ind. Eng. 61 (2011) 1160–1165. | DOI

M.H. Moore, On the fastest route for convoy-type traffic in flow rate constrained networks. Trans. Sci. 10 (1976) 113–124. | DOI | MR

S. Rai and S. Soh, A computer approach for reliability evaluation of telecommunication networks with heterogeneous link-capacities. IEEE Trans. Reliab. 40 (1991) 441–451. | DOI | Zbl

J.B. Rosen, S.Z. Sun and G.L. Xue, Algorithms for the quickest path problem and the enumeration of quickest paths. Comput. Oper. Res. 18 (1991) 579–584. | DOI | MR | Zbl

W.J. Rueger, Reliability analysis of networks with capacity-constraints and failures at branches & nodes. IEEE Trans. Reliab. 35 (1986) 523–528. | DOI | Zbl

S. Ruzika and M. Thiemann, Reliable and Restricted Quickest Path Problems. In INOC 2011. In vol. 6701 of Lecture Notes Comput. Sci. (2011) 309–314. | Zbl

W.L. Wilkinson, An algorithm for universal maximal dynamic flows in a network. Oper. Res. 19 (1971) 1602–1612. | DOI | MR | Zbl

G. Xue, End-to-End data paths: Quickest or most reliable? IEEE Trans. Commun. Lett. 2 (1998) 156–158. | DOI

W.C. Yeh, A Fast Algorithm for Quickest Path Reliability Evaluations in Multi-State Flow Networks. IEEE Trans. Reliab. 64 (2015) 1175–1184. | DOI