首页 | 本学科首页   官方微博 | 高级检索  
     


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
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号