Algorithm to solve a chance‐constrained network capacity design problem with stochastic demands and finite support |
| |
| Authors: | Kathryn M. Schumacher Richard Li‐Yang Chen Amy E.M. Cohn Jeremy Castaing |
| |
| Affiliation: | 1. Research and Development, General Motors, Warren, Michigan 48092;2. Quantitative Modeling and Analysis, Sandia National Laboratories, Livermore, California 94551;3. Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109 |
| |
| Abstract: | We consider the problem of determining the capacity to assign to each arc in a given network, subject to uncertainty in the supply and/or demand of each node. This design problem underlies many real‐world applications, such as the design of power transmission and telecommunications networks. We first consider the case where a set of supply/demand scenarios are provided, and we must determine the minimum‐cost set of arc capacities such that a feasible flow exists for each scenario. We briefly review existing theoretical approaches to solving this problem and explore implementation strategies to reduce run times. With this as a foundation, our primary focus is on a chance‐constrained version of the problem in which α% of the scenarios must be feasible under the chosen capacity, where α is a user‐defined parameter and the specific scenarios to be satisfied are not predetermined. We describe an algorithm which utilizes a separation routine for identifying violated cut‐sets which can solve the problem to optimality, and we present computational results. We also present a novel greedy algorithm, our primary contribution, which can be used to solve for a high quality heuristic solution. We present computational analysis to evaluate the performance of our proposed approaches. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 236–246, 2016 |
| |
| Keywords: | network design chance constraints greedy algorithm |
|
|
