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 条
  • [21] Animation of the Traveling Salesman Problem
    ElAarag, Hala
    Romano, Sam
    2012 PROCEEDINGS OF IEEE SOUTHEASTCON, 2012,
  • [22] Traveling Salesman Problem with Clustering
    Schneider, Johannes J.
    Bukur, Thomas
    Krause, Antje
    JOURNAL OF STATISTICAL PHYSICS, 2010, 141 (05) : 767 - 784
  • [23] Animation of the Traveling Salesman Problem
    ElAarag, Hala
    Romano, Sam
    2013 PROCEEDINGS OF IEEE SOUTHEASTCON, 2013,
  • [24] A Novel Sparrow Search Algorithm for the Traveling Salesman Problem
    Wu, Changyou
    Fu, Xisong
    Pei, Junke
    Dong, Zhigui
    IEEE ACCESS, 2021, 9 : 153456 - 153471
  • [25] Artificial Bee Colony Algorithm For Traveling Salesman Problem
    Li, Weihua
    Li, Weijia
    Yang, Yuan
    Liao, Haiqiang
    Li, Jilong
    Zheng, Xipeng
    ADVANCED MANUFACTURING TECHNOLOGY, PTS 1-3, 2011, 314-316 : 2191 - 2196
  • [26] Discrete social spider algorithm for the traveling salesman problem
    BAS, Emine
    Ulker, Erkan
    ARTIFICIAL INTELLIGENCE REVIEW, 2021, 54 (02) : 1063 - 1085
  • [27] An Improved Genetic Algorithm for Solving the Traveling Salesman Problem
    Chen, Peng
    2013 NINTH INTERNATIONAL CONFERENCE ON NATURAL COMPUTATION (ICNC), 2013, : 397 - 401
  • [28] The Quantum Approximate Algorithm for Solving Traveling Salesman Problem
    Ruan, Yue
    Marsh, Samuel
    Xue, Xilin
    Liu, Zhihao
    Wang, Jingbo
    CMC-COMPUTERS MATERIALS & CONTINUA, 2020, 63 (03): : 1237 - 1247
  • [29] An Improved Discrete Firefly Algorithm for the Traveling Salesman Problem
    Zhou, Lingyun
    Ding, Lixin
    Qiang, Xiaoli
    Luo, Yihan
    JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE, 2015, 12 (07) : 1184 - 1189
  • [30] A hybrid genetic algorithm for the traveling salesman problem with drone
    Quang Minh Ha
    Deville, Yves
    Quang Dung Pham
    Minh Hoang Ha
    JOURNAL OF HEURISTICS, 2020, 26 (02) : 219 - 247
12345