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 条
  • [31] A new genetic algorithm for the asymmetric traveling salesman problem
    Nagata, Yuichi
    Soler, David
    EXPERT SYSTEMS WITH APPLICATIONS, 2012, 39 (10) : 8947 - 8953
  • [32] The Parallel Drone Scheduling Traveling Salesman Problem with Collective Drones
    Nguyen, Minh Anh
    Ha, Minh Hoang
    TRANSPORTATION SCIENCE, 2023, 57 (04) : 866 - 888
  • [33] Matheuristic algorithms for the parallel drone scheduling traveling salesman problem
    Dell'Amico, Mauro
    Montemanni, Roberto
    Novellani, Stefano
    ANNALS OF OPERATIONS RESEARCH, 2020, 289 (02) : 211 - 226
  • [34] The indefinite period traveling salesman problem
    Sun, Lei
    Karwan, Mark H.
    Diaby, Moustapha
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2018, 270 (03) : 1171 - 1181
  • [35] Composite Algorithm Based on Clarke - Wright and Local Search for the Traveling Salesman Problem
    Komarudin
    Parhusip, Sandiego F.
    2019 5TH INTERNATIONAL CONFERENCE ON INDUSTRIAL AND BUSINESS ENGINEERING (ICIBE 2019), 2019, : 87 - 90
  • [36] A swap sequence based Artificial Bee Colony algorithm for Traveling Salesman Problem
    Khan, Indadul
    Maiti, Manas Kumar
    SWARM AND EVOLUTIONARY COMPUTATION, 2019, 44 : 428 - 438
  • [37] Optimization Algorithm Behavior Modeling: A Study on the Traveling Salesman Problem
    Qi, Qi
    Weise, Thomas
    Li, Bin
    PROCEEDINGS OF 2018 TENTH INTERNATIONAL CONFERENCE ON ADVANCED COMPUTATIONAL INTELLIGENCE (ICACI), 2018, : 861 - 866
  • [38] DJAYA: A discrete Jaya algorithm for solving traveling salesman problem
    Gunduz, Mesut
    Aslan, Murat
    APPLIED SOFT COMPUTING, 2021, 105
  • [39] Discrete sparrow search algorithm for symmetric traveling salesman problem
    Zhang, Zhen
    Han, Yang
    APPLIED SOFT COMPUTING, 2022, 118
  • [40] AN IMPROVED APPROXIMATION ALGORITHM FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM\ast
    Traub, Vera
    Vygen, Jens
    SIAM JOURNAL ON COMPUTING, 2022, 51 (01) : 139 - 173
12345