A hybrid simulated annealing and column generation approach for capacitated multicommodity network design
A hybrid simulated annealing and column generation approach for capacitated multicommodity network design
复制标题
用于容量多商品网络设计的混合模拟退火和列生成方法
DOI：
10.1057/jors.2012.114
复制
发表时间：
2013
影响因子：
3.6
通讯作者：
M. Karimi
中科院分区：
文献类型：
--
作者：
M. Yaghini;M. Rahbar;M. Karimi
提出了一种基于路径的容量约束多商品网络设计(PCMND)问题的混合模拟退火法(SA)和列生成法(CG)。在该方法中，SA元启发式算法管理开弧和闭弧。提出了几种添加和删除圆弧的策略，并对其进行了评估。对于给定的设计向量，PCMND问题转化为有能力的多商品最小费用流(CMCF)问题。CMCF问题的精确评估是使用CG算法执行的。采用实验设计的方法进行参数整定。通过求解多个基准测试实例，对该算法的性能进行了评估。在不同的时间限制下，将该算法的结果与CPLEX求解器的解和文献中最著名的方法的解进行了比较。统计分析表明，该算法能够获得较好的解。
This paper presents a hybrid simulated annealing (SA) and column generation (CG) algorithm for the path-based formulation of the capacitated multicommodity network design (PCMND) problem. In the proposed method, the SA metaheuristic algorithm manages open and closed arcs. Several strategies for adding and dropping arcs are suggested and evaluated. For a given design vector in the proposed hybrid approach, the PCMND problem becomes a capacitated multicommodity minimum cost flow (CMCF) problem. The exact evaluation of the CMCF problem is performed using the CG algorithm. The parameter tuning is done by means of design of experiments approach. The performance of the proposed algorithm is evaluated by solving several benchmark instances. The results of the proposed algorithm are compared with the solutions of CPLEX solver and the best-known method in the literature under different time limits. Statistical analysis proves that the proposed algorithm is able to obtain better solutions.