An Exact Parallel Algorithm for Traveling Salesman Problem

被引：0
作者：
Burkhovetskiy, V. [1 ]
Steinberg, B. [1 ]
机构：
[1] Southern Fed Univ, Inst Math Mech & Comp Sci, Milchakova St 8, Rostov Na Donu 344090, Russia
来源：
CEE-SECR'17: PROCEEDINGS OF THE 13TH CENTRAL & EASTERN EUROPEAN SOFTWARE ENGINEERING CONFERENCE IN RUSSIA | 2017年
关键词：
parallel computing; tree traversal; branch-and-bound; traveling salesman problem;
D O I：
10.1145/3166094.3166108
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We describe an exact algorithm for traveling salesman problem based on simplified branch-and-bound algorithm developed by E. Balas and N. Christofides, parallelized with OpenMP on a multi-core processor. It has shown better performance than algorithms in preceding articles and works. Our article is intended for people who use parallel programming technologies, deal with mathematical optimization problems, have interest in perspective algorithms for bioinformatics or NP-hard problems.
引用
收藏
页数：5
相关论文
共 50 条
  • [41] PARALLEL GENETIC ALGORITHMS APPLIED TO THE TRAVELING SALESMAN PROBLEM
    Jog, Prasanna
    Suh, Jung Y.
    Van Gucht, Dirk
    SIAM JOURNAL ON OPTIMIZATION, 1991, 1 (04) : 515 - 529
  • [42] New parallel randomized algorithms for the traveling salesman problem
    Shi, LY
    Olafsson, S
    Sun, N
    COMPUTERS & OPERATIONS RESEARCH, 1999, 26 (04) : 371 - 394
  • [43] An efficient branch-and-cut algorithm for the parallel drone scheduling traveling salesman problem
    Minh Anh Nguyen
    Hai Long Luong
    Minh Hoang Ha
    Ha-Bang Ban
    4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2023, 21 (04): : 609 - 637
  • [44] A Hybrid Exact Algorithm for the Asymmetric Traveling Salesman Problem: Construction and a Statistical Study of Computational Efficiency
    Zhukova, G. N.
    Ul'yanov, M., V
    Fomichev, M., I
    AUTOMATION AND REMOTE CONTROL, 2019, 80 (11) : 2054 - 2067
  • [45] Exact Solutions for the Carrier-Vehicle Traveling Salesman Problem
    Gambella, Claudio
    Lodi, Andrea
    Vigo, Daniele
    TRANSPORTATION SCIENCE, 2018, 52 (02) : 320 - 330
  • [46] A New Genetic Algorithm for solving Traveling Salesman Problem
    Bai Xiaojuan
    Zhou Liang
    PROCEEDINGS OF THE 8TH WSEAS INTERNATIONAL CONFERENCE ON APPLIED COMPUTER AND APPLIED COMPUTATIONAL SCIENCE: APPLIED COMPUTER AND APPLIED COMPUTATIONAL SCIENCE, 2009, : 451 - +
  • [47] A collaborative neurodynamic optimization algorithm to traveling salesman problem
    Zhong, Jing
    Feng, Yuelei
    Tang, Shuyu
    Xiong, Jiang
    Dai, Xiangguang
    Zhang, Nian
    COMPLEX & INTELLIGENT SYSTEMS, 2023, 9 (02) : 1809 - 1821
  • [48] An efficient hybrid genetic algorithm for the traveling salesman problem
    Katayama, K
    Narihisa, H
    ELECTRONICS AND COMMUNICATIONS IN JAPAN PART III-FUNDAMENTAL ELECTRONIC SCIENCE, 2001, 84 (02): : 76 - 83
  • [49] A polynomial time evolution algorithm for the traveling salesman problem
    Dang, JW
    Zhang, ZH
    PROCEEDINGS OF THE 2005 INTERNATIONAL CONFERENCE ON NEURAL NETWORKS AND BRAIN, VOLS 1-3, 2005, : 47 - 49
  • [50] Discrete social spider algorithm for the traveling salesman problem
    BAS, Emine
    Ulker, Erkan
    ARTIFICIAL INTELLIGENCE REVIEW, 2021, 54 (02) : 1063 - 1085
12345