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 条
  • [21] A PARALLEL BRANCH AND BOUND ALGORITHM FOR SOLVING LARGE ASYMMETRIC TRAVELING SALESMAN PROBLEMS
    PEKNY, JF
    MILLER, DL
    MATHEMATICAL PROGRAMMING, 1992, 55 (01) : 17 - 33
  • [22] THE TRAVELING SALESMAN PROBLEM - AN OVERVIEW OF EXACT AND APPROXIMATE ALGORITHMS
    LAPORTE, G
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1992, 59 (02) : 231 - 247
  • [23] Exact algorithms and heuristics for the Quadratic Traveling Salesman Problem with an application in bioinformatics
    Fischer, A.
    Fischer, F.
    Jaeger, G.
    Keilwagen, J.
    Molitor, P.
    Grosse, I.
    DISCRETE APPLIED MATHEMATICS, 2014, 166 : 97 - 114
  • [24] Biogeography Migration Algorithm for Traveling Salesman Problem
    Mo, Hongwei
    Xu, Lifang
    ADVANCES IN SWARM INTELLIGENCE, PT 1, PROCEEDINGS, 2010, 6145 : 405 - +
  • [25] State transition algorithm for traveling salesman problem
    Yang Chunhua
    Tang Xiaolin
    Zhou Xiaojun
    Gui Weihua
    PROCEEDINGS OF THE 31ST CHINESE CONTROL CONFERENCE, 2012, : 2481 - 2485
  • [26] A Quantum Heuristic Algorithm for the Traveling Salesman Problem
    Bang, Jeongho
    Ryu, Junghee
    Lee, Changhyoup
    Yoo, Seokwon
    Lim, James
    Lee, Jinhyoung
    JOURNAL OF THE KOREAN PHYSICAL SOCIETY, 2012, 61 (12) : 1944 - 1949
  • [27] Biogeography migration algorithm for traveling salesman problem
    Mo, Hongwei
    Xu, Lifang
    INTERNATIONAL JOURNAL OF INTELLIGENT COMPUTING AND CYBERNETICS, 2011, 4 (03) : 311 - 330
  • [28] An Efficient Heuristic Algorithm for the Traveling Salesman Problem
    Azimi, Parham
    Daneshvar, Peyman
    ADVANCED MANUFACTURING AND SUSTAINABLE LOGISTICS, PROCEEDINGS, 2010, 46 : 384 - +
  • [29] A polynomial algorithm for a constrained traveling salesman problem
    Rubinstein, JH
    Thomas, DA
    Wormald, NC
    NETWORKS, 2001, 38 (02) : 68 - 75
  • [30] An improved genetic algorithm for the traveling salesman problem
    Li, Lijie
    Zhang, Ying
    ADVANCED INTELLIGENT COMPUTING THEORIES AND APPLICATIONS: WITH ASPECTS OF CONTEMPORARY INTELLIGENT COMPUTING TECHNIQUES, 2007, 2 : 208 - +
12345