Title: A hybrid primal heuristic for Robust Multiperiod Network Design,
Abstract: We investigate the Robust Multiperiod Network Design Problem, a
generalization of the classical Capacitated Network Design Problem that
additionally considers multiple design periods and provides solutions protected
against traffic uncertainty. Given the intrinsic difficulty of the problem,
which proves challenging even for state-of-the art commercial solvers, we
propose a hybrid primal heuristic based on the combination of ant colony
optimization and an exact large neighborhood search. Computational experiments
on a set of realistic instances from the SNDlib show that our heuristic can
find solutions of extremely good quality with low optimality gap.