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 条

[11] HOW EASY IS LOCAL SEARCH [J].