PARALLEL COOPERATIVE SAVINGS BASED ANT COLONY OPTIMIZATION - MULTIPLE SEARCH AND DECOMPOSITION APPROACHES

被引：24

作者：

Doerner, Karl F. ^{[1
]}

Hartl, Richard F. ^{[2
]}

Benkner, Siefried ^{[3
]}

Lucka, Maria ^{[4
]}

机构：

[1] Univ Vienna, Dept Management Sci, Bruenner Str 72, A-1040 Vienna, Austria

[2] Univ Vienna, Dept Management Sci, A-1210 Vienna, Austria

[3] Univ Vienna, Inst Sci Comp, A-1090 Vienna, Austria

[4] Univ Vienna, Inst Sci Comp, A-1210 Vienna, Austria

来源：

PARALLEL PROCESSING LETTERS | 2006年 / 16卷 / 03期

关键词：

Ant Colony Optimization; Decomposition Approach; Parallel Metaheuristic; Vehicle Routing Problem;

D O I：

10.1142/S0129626406002691

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this paper we study different parallel implementations of the Savings based Ant System algorithm developed for solving the Vehicle Routing Problem. We analyze the effects of low-level parallelization, multiple search strategies and domain decomposition approaches. For the different strategies speedup and efficiency as well as solution quality are reported. Different information exchanges are analyzed within the multiple search strategies.

引用

页码：351 / 369

页数：19

共 29 条

[21] Fast Ant Colony Optimization on Runtime Reconfigurable Processor Arrays [J].

Daniel Merkle ;

Martin Middendorf .

Genetic Programming and Evolvable Machines, 2002, 3 (4) :345-361

[22] Multi colony ant algorithms [J].

Middendorf, M ;

Reischle, F ;

Schmeck, H .

JOURNAL OF HEURISTICS, 2002, 8 (03) :305-320

[23] Parallel branch and cut for capacitated vehicle routing [J].

Ralphs, TK .

PARALLEL COMPUTING, 2003, 29 (05) :607-629

[24] D-Ants: Savings Based Ants divide and conquer the vehicle routing problem [J].

Reimann, M ;

Doerner, K ;

Hartl, RF .

COMPUTERS & OPERATIONS RESEARCH, 2004, 31 (04) :563-591

[25]

REIMANN M, 2002, P GEN EV COMP C NEW, P1317

[26]

Strauss C., 1998, HIGH PERFORMANCE ALG, P87

[27]

Stutzle T, 1998, LECT NOTES COMPUT SC, V1498, P722, DOI 10.1007/BFb0056914

[28] PARALLEL ITERATIVE SEARCH METHODS FOR VEHICLE-ROUTING PROBLEMS [J].

TAILLARD, E .

NETWORKS, 1993, 23 (08) :661-673

[29] Parallel Ant Colonies for the quadratic assignment problem [J].

Talbi, EG ;

Roux, O ;

Fonlupt, C ;

Robillard, D .

FUTURE GENERATION COMPUTER SYSTEMS, 2001, 17 (04) :441-449

← 1 2 3 →