A Hybrid Primal Heuristic for Robust Multiperiod Network Design
A Hybrid Primal Heuristic for Robust Multiperiod Network Design
复制标题
DOI：
10.1007/978-3-662-45523-4_2
复制
发表时间：
2014-04
期刊：
影响因子：
--
通讯作者：
Fabio D’Andreagiovanni;J. Krolikowski;Jonad Pulaj
中科院分区：
文献类型：
--
作者：
Fabio D’Andreagiovanni;J. Krolikowski;Jonad Pulaj
我们研究了鲁棒多周期网络设计问题，这是经典的容量限制网络设计问题的推广，它还考虑了多个设计周期，并提供了针对流量不确定性的解决方案。鉴于固有的困难的问题，这证明具有挑战性，即使是最先进的商业求解器，我们提出了一个混合原始启发式的基础上结合蚁群优化和一个确切的大邻域搜索。一组现实的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.