Hostname: page-component-78c5997874-xbtfd Total loading time: 0 Render date: 2024-11-09T13:06:35.515Z Has data issue: false hasContentIssue false
  • English
  • Français

Capacity Expansion in Stochastic Flow Networks

Published online by Cambridge University Press:  27 July 2009

Christos Alexopoulos  and
George S. Fishman
Christos Alexopoulos
Affiliation:
Department of Operations Research University of North Carolina, Chapel Hill, North Carolina 27599
George S. Fishman
Affiliation:
Department of Operations Research University of North Carolina, Chapel Hill, North Carolina 27599
Get access Rights & Permissions [Opens in a new window]

Abstract

Sensitivity analysis represents an important aspect of network flow design problems. For example, what is the incremental increase in system flow of increasing the diameters of specified pipes in a water distribution network? Although methods exist for solving this problem in the deterministic case, no comparable methodology has been available when the network's arc capacities are subject to random variation. This paper provides this methodology by describing a Monte Carlo sampling plan that allows one to conduct a sensitivity analysis for a variable upper bound on the flow capacity of a specified arc. The proposed plan has two notable features. It permits estimation of the probabilities of a feasible flow for many values of the upper bound on the arc capacity from a single data set generated by the Monte Carlo method at a single value of this upper bound. Also, the resulting estimators have considerably smaller variancesthan crude Monte Carlo sampling would produce in the same setting. The success of the technique follows from the use of lower and upper bounds on each probability of interest where the bounds are generated from an established method of decomposing the capacity state space.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 6 , Issue 1 , January 1992 , pp. 99 - 118
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alexopoulos, C. & Fishman, G.S. (1988). Sensitivity analysis in stochastic flow networks using the Monte Carlo method. Technical Report No. UNC/OR/TR-88/5, Department of Operations Research, University of North Carolina at Chapel Hill (revised 1991).Google Scholar
Alexopoulos, C. & Fishman, G.S. (1991). Characterizing stochastic flow networks using the Monte Carlo method. Networks 21: 775–798.CrossRefGoogle Scholar
Doulliez, P. & Jamoulle, E. (1972). Transportation networks with random arc capacities. Revue Francaise d'Automatique, Inform atique et Recherche Operationneile 3: 45–60.Google Scholar
Fishman, G.S. (1986). A Monte Carlo sampling plan for estimating network reliability. Operations Research 34: 581–594.Google Scholar
Fishman, G.S. (1989). Monte Carlo estimation of the maximal flow distribution with discrete stochastic arc capacity levels. Naval Logistics Research Quarterly 36: 829–849.3.0.CO;2-4>CrossRefGoogle Scholar
Fishman, G.S. (1991). Confidence intervals for the mean in the bounded case. Statistics and Probability Letters 12: 223–227.CrossRefGoogle Scholar
Fishman, G.S. & Moore, L.R. (1984). Sampling from a discrete distribution while preserving monotonicity. The American Statistician 38: 219–223.Google Scholar
Fishman, G.S. & Shaw, T.Y. (1989). Evaluating reliability of stochastic flow networks. Probability in the Engineering and Informational Sciences 3: 493–509.CrossRefGoogle Scholar
Ford, L.R. & Fulkerson, D.R. (1962). Flows in networks. Princeton, NJ: Princeton University Press.Google Scholar
Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. American Statistical Association Journal 58: 13–29.Google Scholar
Itai, A. & Shiloach, Y. (1979). Maximum flow in planar networks. SIAM Journal of Computing 8: 135–150.CrossRefGoogle Scholar
Kumamoto, H., Tanaka, K., & Inoue, K. (1977). Efficient evaluation of system reliability by Monte Carlo method. IEEE Transactions on Reliability 26: 311–315.CrossRefGoogle Scholar
Papadimitriou, C.H. & Steiglitz, K. (1982). Combinatorial optimization. Englewood Cliffs, NJ: Prentice-Hall.Google Scholar
Shogan, A.W. (1982). Modular decomposition and reliability computation in stochastic transportation networks having cutnodes. Networks 12: 24 1–253.CrossRefGoogle Scholar
Walker, A.J. (1977). An efficient method for generating discrete random variables with general distributions. ACM Transactions on Mathematical Software 3: 253–256.CrossRefGoogle Scholar