Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Progressive hedging-based meta-heuristics for stochastic network design
AU - Crainic, Teodor G
AU - Fu, Xiaorui
AU - Gendreau, Michel
AU - Rei, Walter
AU - Wallace, Stein W
PY - 2011/9
Y1 - 2011/9
N2 - 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
AB - 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
KW - stochastic network design
KW - metaheuristics
KW - progressive hedging
KW - lagrangean relaxation
U2 - 10.1002/net.20456
DO - 10.1002/net.20456
M3 - Journal article
VL - 58
SP - 114
EP - 124
JO - Networks
JF - Networks
SN - 0028-3045
IS - 2
ER -