A comparison of heuristics for the discrete cost multicommodity network optimization problem

被引：31

作者：

Gabrel, V

Knippel, A

Minoux, M

机构：

[1] Univ Paris 09, LAMSADE, F-75775 Paris 16, France

[2] Univ Paris 06, LIP6, F-75015 Paris, France

[3] Univ Paris 06, LIP6, F-75015 Paris 05, France

来源：

JOURNAL OF HEURISTICS | 2003年 / 9卷 / 05期

关键词：

multicommodity flow; heuristic; Benders decomposition;

D O I：

10.1023/B:HEUR.0000004812.23590.a2

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In this paper, approximate solutions algorithms for discrete cost multicommodity network optimization problems are presented and compared. Firstly, extensions of classical greedy heuristics, based on link-rerouting and flow-rerouting heuristics, are presented in details. Secondly, a new approximate solution algorithm, which basically consists of a heuristic implementation of the exact Benders-type cutting plane generation method, is proposed. All these algorithms are extensively compared on randomly generated graphs up to 50 nodes and 90 links. It clearly appears that this new Benders-type approach is very promising since it produces the best heuristic solutions.

引用

页码：429 / 445

页数：17

共 18 条

[1] Network design using cut inequalities [J].