Robust capacity expansion of network flows
Robust capacity expansion of network flows
复制标题
DOI：
10.1002/net.20183
复制
发表时间：
2007-09
期刊：
影响因子：
2.1
通讯作者：
F. Ordóñez;Jiamin Zhao
中科院分区：
文献类型：
--
作者：
F. Ordóñez;Jiamin Zhao
我们考虑在面临需求和行程时间不确定性的网络中扩展弧容量的问题。我们提出一种鲁棒优化方法来获得对这种不确定性不敏感的容量扩展解决方案。我们的结果表明，在网络流应用的合理假设下，这种鲁棒解决方案可以通过求解易处理的锥线性问题来计算。例如，对于多商品流问题，如果每个商品都有单个源和汇，并且需求和行程时间的不确定性由独立的有界多面体集给出，那么通过求解一个线性规划就可以得到鲁棒解决方案。初步计算结果表明，鲁棒解决方案具有吸引力，因为与代表性场景的最优解相比，它可以将最坏情况成本降低20%以上，同时最优性损失为5%。© 2007威利期刊公司，《网络》，第50卷第2期，136 - 145页，2007年
We consider the problem of expanding arc capacities in a network subject to demand and travel time uncertainty. We propose a robust optimization approach to obtain capacity expansion solutions that are insensitive to this uncertainty. Our results show that, under reasonable assumptions for network flow applications, such robust solutions can be computed by solving tractable conic linear problems. For example, the robust solution for a multicommodity flow problem is obtained by solving a linear program if the problem has a single source and sink per commodity and the uncertainty in demand and travel time is given by independent bounded polyhedral sets. Preliminary computational results show that the robust solution is attractive, as it can reduce the worst case cost by more than 20%, while incurring a 5% loss in optimality when compared to the optimal solution of a representative scenario. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(2), 136–145 2007