Article ID: | iaor20123207 |
Volume: | 220 |
Issue: | 2 |
Start Page Number: | 394 |
End Page Number: | 403 |
Publication Date: | Jul 2012 |
Journal: | European Journal of Operational Research |
Authors: | Crainic Teodor Gabriel, Wallace Stein W, Kaut Michal, Thapalia Biju K |
Keywords: | design, stochastic processes, heuristics, combinatorial optimization |
This paper examines the single‐commodity network design problem with stochastic edge capacities. We characterize the structures of the optimal designs and compare with the deterministic counterparts. We do this partly to understand what constitutes robust network designs, but also to construct a heuristic for the stochastic problem, leading to optimality gaps of about 10%. In our view, that is a rather good result for problems that otherwise cannot be solved at all.