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 条
  • [1] Parallelizing an exact algorithm for the traveling salesman problem
    Burkhovetskiy, Victor Vitalyevich
    Steinberg, Boris Yakovlevich
    6TH INTERNATIONAL YOUNG SCIENTIST CONFERENCE ON COMPUTATIONAL SCIENCE, YSC 2017, 2017, 119 : 97 - 102
  • [2] Exact Heuristic Algorithm for Traveling Salesman Problem
    Lin, Dongmei
    Wu, Xiangbin
    Wang, Dong
    PROCEEDINGS OF THE 9TH INTERNATIONAL CONFERENCE FOR YOUNG COMPUTER SCIENTISTS, VOLS 1-5, 2008, : 9 - +
  • [3] An exact algorithm for the traveling salesman problem with deliveries and collections
    Baldacci, R
    Hadjiconstantinou, E
    Mingozzi, A
    NETWORKS, 2003, 42 (01) : 26 - 41
  • [4] Parallel Genetic Algorithm with OpenCL for Traveling Salesman Problem
    Zhang, Kai
    Yang, Siman
    Li, Li
    Qiu, Ming
    BIO-INSPIRED COMPUTING - THEORIES AND APPLICATIONS, BIC-TA 2014, 2014, 472 : 585 - 590
  • [5] Parallel genetic algorithm with openCL for traveling salesman problem
    Zhang, Kai
    Yang, Siman
    Li, Li
    Qiu, Ming
    Communications in Computer and Information Science, 2014, 472 : 585 - 590
  • [6] Exact algorithms for the Equitable Traveling Salesman Problem
    Kinable, Joris
    Smeulders, Bart
    Delcour, Eline
    Spieksma, Frits C. R.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2017, 261 (02) : 475 - 485
  • [7] 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
  • [8] Parallel Cuckoo Search Algorithm on OpenMP for Traveling Salesman Problem
    Ng Tzy-Luen
    Keat, Yeow Teck
    Abdullah, Rosni
    2016 3RD INTERNATIONAL CONFERENCE ON COMPUTER AND INFORMATION SCIENCES (ICCOINS), 2016, : 380 - 385
  • [9] PARALLEL TEMPERING FOR THE TRAVELING SALESMAN PROBLEM
    Wang, Chiaming
    Hyman, Jeffrey D.
    Percus, Allon
    Caflisch, Russel
    INTERNATIONAL JOURNAL OF MODERN PHYSICS C, 2009, 20 (04): : 539 - 556
  • [10] A PARALLEL 2-OPT ALGORITHM FOR THE TRAVELING-SALESMAN PROBLEM
    VERHOEVEN, MGA
    AARTS, EHL
    SWINKELS, PCJ
    FUTURE GENERATION COMPUTER SYSTEMS, 1995, 11 (02) : 175 - 182
12345