Single-Commodity Stochastic Network Design Under Demand and Topological Uncertainties with Insufficient Data

Stochastic network design is fundamental to transportation and logistic problems in practice, yet faces new modeling and computational challenges resulted from heterogeneous sources of uncertainties and their unknown distributions given limited data. In this article, we design arcs in a network to optimize the cost of single-commodity flows under random demand and arc disruptions. We minimize the network design cost plus cost associated with network performance under uncertainty evaluated by two schemes. The first scheme restricts demand and arc capacities in budgeted uncertainty sets and minimizes the worst-case cost of supply generation and network flows for any possible realizations. The second scheme generates a finite set of samples from statistical information (e.g., moments) of data and minimizes the expected cost of supplies and flows, for which we bound the worst-case cost using budgeted uncertainty sets. We develop cutting-plane algorithms for solving the mixed-integer nonlinear programming reformulations of the problem under the two schemes. We compare the computational efficacy of different approaches and analyze the results by testing diverse instances of random and real-world networks. (c) 2017 Wiley Periodicals, Inc.