License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2019.5
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11417/
Garuba, Francis ;
Goerigk, Marc ;
Jacko, Peter
Robust Network Capacity Expansion with Non-Linear Costs
Abstract
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.
BibTeX - Entry
@InProceedings{garuba_et_al:OASIcs:2019:11417,
author = {Francis Garuba and Marc Goerigk and Peter Jacko},
title = {{Robust Network Capacity Expansion with Non-Linear Costs}},
booktitle = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)},
pages = {5:1--5:13},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-95977-128-3},
ISSN = {2190-6807},
year = {2019},
volume = {75},
editor = {Valentina Cacchiani and Alberto Marchetti-Spaccamela},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11417},
doi = {10.4230/OASIcs.ATMOS.2019.5},
annote = {Keywords: Robust Optimization, Mobile Network, Network Capacity Design & Expansion, Non-linear Cost, Traffic and Transport Routing}
}
|
Keywords: |
|
Robust Optimization, Mobile Network, Network Capacity Design & Expansion, Non-linear Cost, Traffic and Transport Routing |
|
Collection: |
|
19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
15.11.2019 |
