A PARALLEL 2-OPT ALGORITHM FOR THE TRAVELING-SALESMAN PROBLEM

被引：31

作者：

VERHOEVEN, MGA ^{[1
]}

AARTS, EHL ^{[1
]}

SWINKELS, PCJ ^{[1
]}

机构：

[1] PHILIPS RES LABS,5600 JA EINDHOVEN,NETHERLANDS

来源：

FUTURE GENERATION COMPUTER SYSTEMS | 1995年 / 11卷 / 02期

关键词：

LOCAL SEARCH; TRAVELING SALESMAN PROBLEM; DATA PARALLELISM;

D O I：

10.1016/0167-739X(94)00059-N

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a scalable parallel local search algorithm based on data parallelism. The concept of distributed neighborhood structures is introduced, and applied to the Traveling Salesman Problem (TSP). Our parallel local search algorithm finds the same quality solutions as the classical 2-opt algorithm and has a good speed-up. The algorithm is implemented on a Parsytec GCel, consisting of 512 transputers. Its performance is empirically analyzed for TSP instances with several thousands of cities.

引用

页码：175 / 182

页数：8

共 23 条

[1]

AARTS E, 1993, 934 EINDH U TECHN CO

[2] A DISTRIBUTED IMPLEMENTATION OF SIMULATED ANNEALING FOR THE TRAVELING SALESMAN PROBLEM [J].

ALLWRIGHT, JRA ;

CARPENTER, DB .

PARALLEL COMPUTING, 1989, 10 (03) :335-338

[3]

BACHEM A, 1992, 92119 U KOLN REP

[4]

Barr R. S., 1993, ORSA Journal on Computing, V5, P2, DOI 10.1287/ijoc.5.1.2

[5]

BLAND R, 1989, OPER RES LETT, V8, P123

[6]

Felten E., 1985, Proceedings of the 1985 International Conference on Parallel Processing (Cat. No.85CH2140-2), P6

[7]

FIECHTER C, 1990, ORWP901 DMA EC POL F

[8]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

[9]

Glover F., 1990, ORSA Journal on Computing, V2, P4, DOI [10.1287/ijoc.1.3.190, 10.1287/ijoc.2.1.4]

[10]

JOHNSON D, 1990, LNCS, V447, P446

← 1 2 3 →