Searching for backbones - An efficient parallel algorithm for the traveling salesman problem

被引：45

作者：

Schneider, J ^{[1
]}

Froschhammer, C ^{[1
]}

Morgenstern, I ^{[1
]}

Husslein, T ^{[1
]}

Singer, JM ^{[1
]}

机构：

[1] UNIV ZURICH,INST PHYS,CH-8057 ZURICH,SWITZERLAND

来源：

COMPUTER PHYSICS COMMUNICATIONS | 1996年 / 96卷 / 2-3期

关键词：

optimization; parallel; Monte Carlo; threshold accepting; TSP; backbone; degeneracy;

D O I：

10.1016/0010-4655(96)00062-8

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The Traveling Salesman Problem (TSP) plays an important role in Operations Research, Applied Mathematics and Computational Physics. We investigated it using a stochastic approach. Studying several solutions of a special TSP we found that many parts of a good solution are the same in all other good solutions for this problem. In this paper we discuss an efficient parallel method to reduce the TSP to a smaller one by finding these backbones and eliminating them to get even better solutions in a very short time and a few observables of interest corresponding to this parallel approach.

引用

页码：173 / 188

页数：16

共 24 条

[1]

[Anonymous], 1994, GENETISCHE ALGORITHM

[2]

BINDER K, 1992, MONTE CARLO METHODS

[3] NEW OPTIMIZATION HEURISTICS - THE GREAT DELUGE ALGORITHM AND THE RECORD-TO-RECORD TRAVEL [J].