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 条
  • [1] Traveling Salesman Problem Optimization with Parallel Genetic Algorithm
    Cakir, Murat
    Yilmaz, Guray
    2015 23RD SIGNAL PROCESSING AND COMMUNICATIONS APPLICATIONS CONFERENCE (SIU), 2015, : 2557 - 2560
  • [2] An Efficient and Scalable Algorithm for the Traveling Salesman Problem
    Ye, Chen
    Yang, Zhongcheng
    Yan, Tianxing
    2014 5TH IEEE INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING AND SERVICE SCIENCE (ICSESS), 2014, : 335 - 339
  • [3] A hybridized parallel bats algorithm for combinatorial problem of traveling salesman
    Trong-The Nguyen
    Qiao, Yu
    Pan, Jeng-Shyang
    Chu, Shu-Chuan
    Chang, Kuo-Chi
    Xue, Xingsi
    Thi-Kien Dao
    JOURNAL OF INTELLIGENT & FUZZY SYSTEMS, 2020, 38 (05) : 5811 - 5820
  • [4] Parallel Artificial Bee Colony Algorithm for the Traveling Salesman Problem
    Xu, Kun
    Jiang, Mingyan
    Yuan, Dongfeng
    PROCEEDINGS OF THE 2ND INTERNATIONAL CONFERENCE ON COMPUTER AND INFORMATION APPLICATIONS (ICCIA 2012), 2012, : 663 - 667
  • [5] An efficient genetic algorithm for the traveling salesman problem with precedence constraints
    Moon, C
    Kim, J
    Choi, G
    Seo, Y
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 140 (03) : 606 - 617
  • [6] An effective parallel hybrid GA for Traveling Salesman Problem
    Liu, Yanbin
    Huang, Jun
    PROCEEDINGS OF THE INTERNATIONAL CONFERENCE INFORMATION COMPUTING AND AUTOMATION, VOLS 1-3, 2008, : 695 - 698
  • [7] Large scale parallel Iterated Local Search algorithm for solving Traveling Salesman Problem
    Rocki, Kamil
    Suda, Reiji
    HIGH PERFORMANCE COMPUTING SYMPOSIUM 2012 (HPC 2012), 2012, 44 (06): : 26 - 33
  • [8] Research On Traveling Salesman Problem Algorithm
    Yun, Xiaoyan
    MANUFACTURING PROCESS AND EQUIPMENT, PTS 1-4, 2013, 694-697 : 2901 - 2904
  • [9] Efficient GPU Implementation of Genetic Algorithm to Solve the Traveling Salesman Problem
    Kidwell, Adam
    Fillmore, Alex
    Alawneh, Shadi
    SOUTHEASTCON 2024, 2024, : 44 - 49
  • [10] Artificial Fish Algorithm to solve Traveling Salesman Problem
    Wang, Jian-Ping
    Liu, Yan-Pei
    Huang, Yong
    FRONTIERS OF MANUFACTURING AND DESIGN SCIENCE II, PTS 1-6, 2012, 121-126 : 4410 - 4414
12345