Details

Autor(en) / Beteiligte

• Schumacher, Kathryn M.
• Li-Yang Chen, Richard
• Cohn, Amy E.M.
• Castaing, Jeremy

Titel

Algorithm to solve a chance-constrained network capacity design problem with stochastic demands and finite support

Ist Teil von

• Naval research logistics, 2016-04, Vol.63 (3), p.236-246

Ort / Verlag

New York: Blackwell Publishing Ltd

Erscheinungsjahr

2016

Quelle

Wiley Online Library

Beschreibungen/Notizen

• 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