The β-Reliable Median on a Network with Discrete Probabilistic Demand Weights

This study extends the classical network median problem by considering the stochastic nature of demand. Assuming that the demand weights associated with nodes are independent discrete random variables, we introduce a chance-constrained programming model to define a β-reliable median of the network. It is shown that the β-reliable median problem is NP-hard. Exact solution procedures and a normal approximation algorithm are developed to search for the β-reliable median. Their performance is evaluated by computational experiments.