Capacity expansion and reliability evaluation on the networks flows with continuous stochastic functional capacity. (English) Zbl 1442.90026

Summary: In many systems such as computer network, fuel distribution, and transportation system, it is necessary to change the capacity of some arcs in order to increase maximum flow value from source \(s\) to sink \(t\), while the capacity change incurs minimum cost. In real-time networks, some factors cause loss of arc’s flow. For example, in some flow distribution systems, evaporation, erosion or sediment in pipes waste the flow. Here we define a real capacity, or the so-called functional capacity, which is the operational capacity of an arc. In other words, the functional capacity of an arc equals the possible maximum flow that may pass through the arc. Increasing the functional arcs capacities incurs some cost. There is a certain resource available to cover the costs. First, we construct a mathematical model to minimize the total cost of expanding the functional capacities to the required levels. Then, we consider the loss of flow on each arc as a stochastic variable and compute the system reliability.


90B10 Deterministic network models in operations research
Full Text: DOI


[1] Ford, L.; Fulkerson, D., Maximal flow through a network, Canadian Journal of Mathematics, 8, 3, 399-404 (1956) · Zbl 0073.40203
[2] Karzanov, A. V., Determining the maximal flow in a network by the method of pre-flows, Soviet Mathematics Doklady, 15, 434-437 (1974) · Zbl 0303.90014
[3] Ahuja, R. K.; Orlin, J., A capacity scaling algorithm for the constrained maximum flow problem, Networks, 25, 2, 89-98 (1995) · Zbl 0821.90041
[4] Alon, N., Generating pseudo-random permutations and maximum flow algorithms, Information Processing Letters, 35, 4, 201-204 (1990) · Zbl 0702.68087
[5] Ahuja, R. K.; Orlin, J. B., A fast and simple algorithm for the maximum flow problem, Operations Research, 37, 5, 748-759 (1989) · Zbl 0691.90024
[6] Elalouf, A.; Adany, R.; Ceder, A., Flow expansion on transportation networks with budget constraints, Social and Behavioral Sciences, 54, 1168-1175 (2012)
[7] Eiselt, H.; von Frajer, H., On the budget-restricted max flow problem, OR Spektrum, 3, 4, 225-231 (1982) · Zbl 0473.90032
[8] Ahuja, R. K.; Batra, J. L.; Gupta, S. K.; Punnen, A. P., Optimal expansion of capacitated transshipment networks, European Journal of Operational Research, 89, 1-2, 176-184 (1996) · Zbl 0908.90116
[9] Yeh, W. C., A simple approach to search for all \(d\)-MCs of a limited-flow network, Reliability Engineering & System Safety, 71, 1, 15-19 (2001)
[10] Xiao, J.; Zu, G.-Q.; Gong, X.-X.; Wang, C.-S., Model and topological characteristics of power distribution system security region, Journal of Applied Mathematics, 2014 (2014)
[11] Salehi Fathabadi, H.; Forghani-elahabadi, M., A note on “A simple approach to search for all d-MCs of a limited-flow network”, Reliability Engineering and System Safety, 94, 11, 1878-1880 (2009)
[12] Yeh, W. C., A new approach to evaluate reliability of multistate networks under the cost constraint, Omega, 33, 3, 203-209 (2005)
[13] Salehi Fathabadi, H.; Khodaei, M., Reliability evaluation of network flows with stochastic capacity and cost constraint, International Journal of Mathematics in Operational Research, 4, 4, 439-452 (2012) · Zbl 1390.90106
[14] Lin, Y. K.; Yeh, C. T., Maximal network reliability with optimal transmission line assignment for stochastic electric power networks via genetic algorithms, Applied Soft Computing Journal, 11, 2, 2714-2724 (2011)
[15] Lin, Y. K., Using minimal cuts to study the system capacity for a stochastic-flow network in two-commodity case, Computers & Operations Research, 30, 11, 1595-1607 (2003) · Zbl 1039.90006
[16] Lin, J. S., Reliability evaluation of capacitated-flow networks with budget constraints, IIE Transactions, 30, 12, 1175-1180 (1998)
[17] Aven, T., Some considerations on reliability theory and its applications, Reliability Engineering and System Safety, 21, 3, 215-223 (1988)
[18] Ball, M. O., Computational complexity of network reliability analysis: an overview, IEEE Transaction on Reliability, 35, 3, 230-239 (1986) · Zbl 0602.90061
[19] Ahuja, R. K.; Magnanti, T. L., Network Flows, Theory, Algorithms, and Applications (1993), Englewood Cliffs, NJ, USA: Prentice Hall, Englewood Cliffs, NJ, USA · Zbl 1201.90001
[20] Banks, J.; Carson, J., Discrete-Event System Simulation (1984), New York, NY, USA: Prentice Hall, New York, NY, USA · Zbl 0525.68071
[21] Mood, A. M.; Graybill, F. M.; Boes, D. C., Introduction to Theory of Statistics (1974), McGraw Hill · Zbl 0277.62002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.