Schneider, Johannes and Froschhammer, Christine and Morgenstern, Ingo and Husslein, Thomas and Singer, Johannes Maria
Searching for backbones — an efficient parallel algorithm for the traveling salesman problem.
Computer physics communications: an international journal devoted to computational physics and computer programs in physics 96 (2-3), pp. 173-188.
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.
|Date:||1 August 1996|
|Institutions:|| Physics > Institute of Theroretical Physics > Professor Morgenstern|
|02.50.-r; 02.50.Ga; 02.70.Lq; 89.20.+a; 89.80.+h; 89.90.+n||PACS|
|Keywords:||Optimization; Parallel; Monte Carlo; Threshold accepting; TSP; Backbone; Degeneracy|
|Subjects:||500 Science > 530 Physics|
|Created at the University of Regensburg:||Unknown|
|Deposited On:||09 Aug 2010 12:12|
|Last Modified:||20 Jul 2011 22:34|