A hybrid primal heuristic for Robust Multiperiod Network Design
This work addresses a challenging optimization problem for network design under uncertainty, but it is incremental as it builds on existing methods to improve computational performance.
The authors tackled the Robust Multiperiod Network Design Problem, a complex generalization of network design with multiple periods and traffic uncertainty, by proposing a hybrid primal heuristic combining ant colony optimization and exact large neighborhood search, which achieved extremely good quality solutions with low optimality gap on realistic instances from SNDlib.
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.