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
相关论文
共 50 条
  • [41] A Solution to Traveling Salesman Problem Using Hybrid Genetic Algorithm
    Wang, Jian-cheng
    Yang, Yan-jie
    Lu, Ya-ping
    Lu, Ya-ping
    2013 INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND ARTIFICIAL INTELLIGENCE (ICCSAI 2013), 2013, : 235 - 240
  • [42] The performances of a general optimization algorithm in solving traveling salesman problem
    Ancau, M.
    Annals of DAAAM for 2005 & Proceedings of the 16th International DAAAM Symposium: INTELLIGENT MANUFACTURING & AUTOMATION: FOCUS ON YOUNG RESEARCHES AND SCIENTISTS, 2005, : 5 - 6
  • [43] Traveling salesman problem based on improved ant colony algorithm
    Zhang Hui
    Wang Xi-huai
    Xiao Jian-mei
    Proceedings of the 2007 Chinese Control and Decision Conference, 2007, : 492 - +
  • [44] A 3/4 Differential Approximation Algorithm for Traveling Salesman Problem
    Amano, Yuki
    Makino, Kazuhisa
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2022, 2022, 13571 : 237 - 248
  • [45] A three-phase algorithm for the pollution traveling Salesman problem
    Garcia-Vasquez, Karen
    Linfati, Rodrigo
    Escobar, John Willmer
    HELIYON, 2024, 10 (09)
  • [46] Discrete Social Spider Algorithm for Solving Traveling Salesman Problem
    Khosravanian, Asieh
    Rahmanimanesh, Mohammad
    Keshavarzi, Parviz
    INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE AND APPLICATIONS, 2021, 20 (03)
  • [47] A multiple heuristic search algorithm for solving traveling salesman problem
    Gang, P
    Iimura, I
    Nakayama, S
    PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES, PDCAT'2003, PROCEEDINGS, 2003, : 779 - 783
  • [48] An Adaptive Ant Colony Algorithm for Dynamic Traveling Salesman Problem
    Ma, An-Xiang
    Zhang, Xiao-Hong
    Zhang, Chang-Sheng
    Zhang, Bin
    Gao, Yan
    JOURNAL OF INFORMATION SCIENCE AND ENGINEERING, 2019, 35 (06) : 1263 - 1277
  • [49] Parallel Nest-Site Selection Algorithm for Traveling Salesman Problems
    Taetragool, Unchalisa
    Sirinaovakul, Booncharoen
    Achalakul, Tiranee
    PROCEEDINGS OF THE 2018 1ST IEEE INTERNATIONAL CONFERENCE ON KNOWLEDGE INNOVATION AND INVENTION (ICKII 2018), 2018, : 240 - 243
  • [50] Linearity in the traveling salesman problem
    Colletti, BW
    Barnes, JW
    APPLIED MATHEMATICS LETTERS, 2000, 13 (03) : 27 - 32
12345