A Comparison of Heuristics for the Discrete Cost Multicommodity Network Optimization Problem

被引：0

作者：

Virginie Gabrel

Arnaud Knippel

Michel Minoux

机构：

[1] University Paris 9,

[2] LAMSADE,undefined

[3] University Paris 6,undefined

[4] LIP6,undefined

[5] University Paris 6,undefined

[6] LIP6,undefined

来源：

Journal of Heuristics | 2003年 / 9卷

关键词：

multicommodity flow; heuristic; Benders decomposition;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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

页数：16

共 28 条

[1]

Barahona F.(1996)Network Design Using Cut Inequalities SIAM Journal on Optimization 6 823-837

[2]

Bienstock D.(1998)Minimum Cost Capacity Installation for Multicommodity Network Flows Mathematical Programming 81 177-199

[3]

Chopra S.(1996)Algorithms and Extended Formulations for One and Two Facility Network Design LNCS 1084 44-57

[4]

Gunluk O.(1998)A Cutting Plane Algorithm for Multicommodity Survivable Network Design Problems INFORMS Journal on Computing 10 1-11

[5]

Tsai C.(1999)Exact Solution of Multicommodity Network Optimization Problems with General Step Cost Functions Operations Research Letters 25 15-23

[6]

Chopra S.(1997)LP Relaxations Better than Convexification for Multicommodity Network Optimization Problems with Step Increasing Cost Functions Acta Mathematica Vietnamica 22 123-145

[7]

Gilboa I.(1999)A Branch-and-Cut Algorithm for Capacitated Network Design Problems Math. Prog. Ser A. 86 17-39

[8]

Sastry S.(1970)An Efficient Heuristic Procedure for Partitioning Graphs Bell. Systems Tech Journal 49 291-307

[9]

Dahl G.(1993)Shortest Paths, Single Origin-Destination Network Design and Associated Polyhedra Networks 33 103-121

[10]

Stoer M.(1995)Modeling and Solving the Two-Facility Capacited Network Loading Problem Operations Research 43 142-157

← 1 2 3 →