Progressive Hedging-Based Metaheuristics for Stochastic Network Design
Progressive Hedging-Based Metaheuristics for Stochastic Network Design
复制标题
DOI：
10.1002/net.20456
复制
发表时间：
2011-09-01
期刊：
影响因子：
2.1
通讯作者：
Wallace, Stein W.
中科院分区：
文献类型：
--
作者：
Crainic, Teodor Gabriel;Fu, Xiaorui;Wallace, Stein W.
研究了具有不确定需求的随机固定费用容量约束多商品网络设计（S-CMND）问题。我们提出了一个两阶段的随机规划公式，其中设计决策组成的第一阶段，而追索权的决定是在第二阶段，根据观察到的需求分配的商品。总体目标是优化第一阶段设计决策的成本加上第二阶段产生的总预期分销成本。为了解决这个问题，我们提出了一个启发式的框架启发的渐进对冲算法的Rockafellar和Wets。根据这一策略，情景分解被用来分离随机问题的可能结果，情景，随机事件。然后，每个场景子问题成为待解决的确定性CMND问题，其可以通过有效的专门方法来解决。我们还提出并比较了不同的策略，逐步引导场景子问题，以达成一致的设计弧的状态，并以一个良好的全球设计为目标。这些策略被嵌入到一个并行的解决方案的方法，这是数值计算效率，并产生高质量的解决方案，根据各种问题的特点和需求的相关性。(C)2011 Wiley Periodicals，Inc. NETWORKS，第58（2）卷，114-124 2011年。
We consider the stochastic fixed-charge capacitated multicommodity network design (S-CMND) problem with uncertain demand. We propose a two-stage stochastic programming formulation, where design decisions make up the first stage, while recourse decisions are made in the second stage to distribute the commodities according to observed demands. The overall objective is to optimize the cost of the first-stage design decisions plus the total expected distribution cost incurred in the second stage. To solve this formulation, we propose a metaheuristic framework inspired by the progressive hedging algorithm of Rockafellar and Wets. Following this strategy, scenario decomposition is used to separate the stochastic problem following the possible outcomes, scenarios, of the random event. Each scenario subproblem then becomes a deterministic CMND problem to be solved, which may be addressed by efficient specialized methods. We also propose and compare different strategies to gradually guide scenario subproblems to agree on the status of design arcs and aim for a good global design. These strategies are embedded into a parallel solution method, which is numerically shown to be computationally efficient and to yield high-quality solutions under various problem characteristics and demand correlations. (C) 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 58(2), 114-124 2011.