TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Krolikowski, Jonatan A1 - Pulaj, Jonad T1 - A Fast Hybrid Primal Heuristic for Multiband Robust Capacitated Network Design with Multiple Time Periods N2 - 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. T3 - ZIB-Report - 14-40 KW - Capacitated Network Design KW - Multiperiod Design KW - Multiband Robust Optimization KW - Traffic Uncertainty KW - Metaheuristic KW - Ant Colony Optimization KW - Exact Large Neighborhood Search Y1 - 2014 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/5286 UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-52862 SN - 1438-0064 ER -