A Fast Hybrid Primal Heuristic for Multiband Robust Capacitated Network Design with Multiple Time Periods
Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-52862
- We investigate the Robust Multiperiod Network Design Problem, a generalization of the Capacitated Network Design Problem (CNDP) that, besides establishing flow routing and network capacity installation as in a canonical CNDP, also considers a planning horizon made up of multiple time periods and protection against fluctuations in traffic volumes. As a remedy against traffic volume uncertainty, we propose a Robust Optimization model based on Multiband Robustness (Büsing and D'Andreagiovanni, 2012), a refinement of classical Gamma-Robustness by Bertsimas and Sim (2004) that uses a system of multiple deviation bands. Since the resulting optimization problem may prove very challenging even for instances of moderate size solved by a state-of-the-art optimization solver, we propose a hybrid primal heuristic that combines a randomized fixing strategy inspired by ant colony optimization and an exact large neighbourhood search. Computational experiments on a set of realistic instances from the SNDlib (2010) show that our original heuristic can run fast and produce solutions of extremely high quality associated with low optimality gaps.
Verfasserangaben: | Fabio D'Andreagiovanni, Jonatan Krolikowski, Jonad Pulaj |
---|---|
Dokumentart: | ZIB-Report |
Freies Schlagwort / Tag: | Ant Colony Optimization; Capacitated Network Design; Exact Large Neighborhood Search; Metaheuristic; Multiband Robust Optimization; Multiperiod Design; Traffic Uncertainty |
Datum der Erstveröffentlichung: | 21.10.2014 |
Schriftenreihe (Bandnummer): | ZIB-Report (14-40) |
ISSN: | 1438-0064 |
Verlagspublikation: | A rev. vers. appeared in: Applied Soft Computing, 26 (2015) pp. 497-507 |
DOI: | https://doi.org/10.1016/j.asoc.2014.10.016 |
Lizenz (Deutsch): | Creative Commons - Namensnennung |