文章基本信息

标题：Robust Network Capacity Expansion with Non-Linear Costs
本地全文：下载
作者：Francis Garuba ; Marc Goerigk ; Peter Jacko 等
期刊名称：OASIcs : OpenAccess Series in Informatics
电子版ISSN：2190-6807
出版年度：2019
卷号：75
页码：1-13
DOI：10.4230/OASIcs.ATMOS.2019.5
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The network capacity expansion problem is a key network optimization problem practitioners regularly face. There is an uncertainty associated with the future traffic demand, which we address using a scenario-based robust optimization approach. In most literature on network design, the costs are assumed to be linear functions of the added capacity, which is not true in practice. To address this, two non-linear cost functions are investigated: (i) a linear cost with a fixed charge that is triggered if any arc capacity is modified, and (ii) its generalization to piecewise-linear costs. The resulting mixed-integer programming model is developed with the objective of minimizing the costs. Numerical experiments were carried out for networks taken from the SNDlib database. We show that networks of realistic sizes can be designed using non-linear cost functions on a standard computer in a practical amount of time within negligible suboptimality. Although solution times increase in comparison to a linear-cost or to a non-robust model, we find solutions to be beneficial in practice. We further illustrate that including additional scenarios follows the law of diminishing returns, indicating that little is gained by considering more than a handful of scenarios. Finally, we show that the results of a robust optimization model compare favourably to the traditional deterministic model optimized for the best-case, expected, or worst-case traffic demand, suggesting that it should be used whenever computationally feasible.
关键词：Robust Optimization; Mobile Network; Network Capacity Design & Expansion; Non-linear Cost; Traffic and Transport Routing